Difference between revisions of "Chapter 3"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 31: Line 31:
 
===Elementary Data Structures===
 
===Elementary Data Structures===
  
3.8
+
:3.8. Tic-tac-toe is a game played on an <math>n * n</math> board (typically <math>n = 3</math>) where two players take consecutive turns placing “O” and “X” marks onto the board cells. The game is won if n consecutive “O” or ‘X” marks are placed in a row, column, or diagonal. Create a data structure with <math>O(n)</math> space that accepts a sequence of moves, and reports in constant time whether the last move won the game.
  
  
[[3.9]]
+
:[[3.9]]. Write a function which, given a sequence of digits 2–9 and a dictionary of <math>n</math> words, reports all words described by this sequence when typed in on a standard telephone keypad. For the sequence 269 you should return any, box, boy, and cow, among other words.
 +
[[3.9|Solution]]
  
  
3.10
+
:3.10. Two strings <math>X</math> and <math>Y</math> are anagrams if the letters of <math>X</math> can be rearranged to form <math>Y</math> . For example, silent/listen, and incest/insect are anagrams. Give an efficient algorithm to determine whether strings <math>X</math> and <math>Y</math> are anagrams.
  
 
===Trees and Other Dictionary Structures===
 
===Trees and Other Dictionary Structures===

Revision as of 20:42, 14 September 2020

Data Structure

Stacks, Queues, and Lists

3.1. A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string [math]\displaystyle{ ((())())() }[/math] contains properly nested pairs of parentheses, which the strings [math]\displaystyle{ )()( }[/math] and [math]\displaystyle{ ()) }[/math] do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

Solution


3.2. Give an algorithm that takes a string [math]\displaystyle{ S }[/math] consisting of opening and closing parentheses, say )()(())()()))())))(, and finds the length of the longest balanced parentheses in [math]\displaystyle{ S }[/math], which is 12 in the example above. (Hint: The solution is not necessarily a contiguous run of parenthesis from [math]\displaystyle{ S }[/math].)


3.3. Give an algorithm to reverse the direction of a given singly linked list. In other words, after the reversal all pointers should now point backwards. Your algorithm should take linear time.

Solution


3.4. Design a stack [math]\displaystyle{ S }[/math] that supports S.push(x), S.pop(), and S.findmin(), which returns the minimum element of [math]\displaystyle{ S }[/math]. All operations should run in constant time.


3.5. We have seen how dynamic arrays enable arrays to grow while still achieving constant-time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink on demand.
(a) Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.
(b) Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.

Solution


3.6. Suppose you seek to maintain the contents of a refrigerator so as to minimize food spoilage. What data structure should you use, and how should you use it?


3.7. Work out the details of supporting constant-time deletion from a singly linked list as per the footnote from page 79, ideally to an actual implementation. Support the other operations as efficiently as possible.

Solution

Elementary Data Structures

3.8. Tic-tac-toe is a game played on an [math]\displaystyle{ n * n }[/math] board (typically [math]\displaystyle{ n = 3 }[/math]) where two players take consecutive turns placing “O” and “X” marks onto the board cells. The game is won if n consecutive “O” or ‘X” marks are placed in a row, column, or diagonal. Create a data structure with [math]\displaystyle{ O(n) }[/math] space that accepts a sequence of moves, and reports in constant time whether the last move won the game.


3.9. Write a function which, given a sequence of digits 2–9 and a dictionary of [math]\displaystyle{ n }[/math] words, reports all words described by this sequence when typed in on a standard telephone keypad. For the sequence 269 you should return any, box, boy, and cow, among other words.

Solution


3.10. Two strings [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are anagrams if the letters of [math]\displaystyle{ X }[/math] can be rearranged to form [math]\displaystyle{ Y }[/math] . For example, silent/listen, and incest/insect are anagrams. Give an efficient algorithm to determine whether strings [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] are anagrams.

Trees and Other Dictionary Structures

3.11


3.12


3.13


3.14


3.15


3.16


3.17


3.18


3.19


3.20


3.21

Applications of Tree Structures

3.22


3.23


3.24


3.25


3.26


3.27


3.28


3.29


3.30


3.31

Implementation Projects

3.32


3.33

Interview Problems

3.34


3.35


3.36


3.37


3.38


3.39


3.40


3.41


3.42


3.43


3.44


3.45


Back to Chapter List