The Algorithm Design Manual Exercises

Chapter 1: Introduction

1-1

a = -1 and b = -1 produces -2. This is less than min(a, b).

1-3

Roads have different speed limits! We just need a long road that allows fast travel.

1-5

A. S = {1, 2, 3}, T = 5 B. S = {1, 2, 3}, T = 5 C. S = {1, 3, 5}, T = 6

1-7

Suppose that c = 2. We know that multiply(x, 0) is always 0. Based on the pseudocode, multiply(x, y) is equal to

  • multiply(2 * x, floor(y / 2)) + x * (y mod 2)
  • (2 * x) * floor(y / 2) + x * (y mod 2)
  • x * (2floor(y / 2) + y mod 2)
  • x * y

When we assume that multiply(2 * x, floor(y / 2)) = 2x * floor(y / 2).

1-9

Base Case: len(A) = 1. This list is sorted.

Inductive Case: Assume that bubblesort([1…n]) is sorts the list. To prove that bubblesort([1…n + 1]) also sorts the list, we just need to show that the main loop will correctly place the last element in the list. This naturally follows from the "bubbling" to the correct position.

QED.

1-11

Base Case: Suppose n = 1.

  • \(\sum_{i=1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6}\)
  • \((1)^2 = \frac{(1)((1) + 1)(2(1) + 1)}{6}\)
  • \(1 = \frac{(1)(2)(3)}{6}\)
  • \(1 = 1\)

Inductive Case: Assume that \(\sum_{i=1}^{n} i^2 = \frac{n(n + 1)(2n + 1)}{6}\). Now let's prove that n + 1 also works. \(\sum_{i=1}^{n + 1} i^2 = \sum_{i=1}^{n} i^2 + (n + 1)^2\). We can show mathematically that \(\frac{n(n + 1)(2n + 1)}{6} + (n + 1)^2 = \frac{(n + 1)((n + 1) + 1)(2(n + 1) + 1)}{6}\).

QED.

1-19

The average number of pages in my books is around 300. I have 18 small shelves of books. Each shelf has around 15 books. I estimate that all the books I own have 300 * 18 * 15 = 81,000 pages. This is far less than one million pages!

My school library has three floors. Each floor has around 50 rows of books. Each row has around 30 large shelves of books. Each shelf has around 50 books. I estimate that the number of pages in my school library is 300 * 3 * 50 * 30 * 50 = 67,500,000 pages.

Chapter 2: Algorithm Analysis

2-1

The worst case is \(O(n^3)\).

2-3

The worst case is \(O(n^4)\).

2-5

  1. \(2n\) multiplications in the worst case. \(n\) additions.
  2. \(2n\) multiplications on average.

2-7

  1. Yes! \(2^{n + 1} = 2*2^n\) and we can drop the constant.
  2. No!

2-9

  1. \(g(n) = O(f(n))\)
  2. \(f(n) = O(g(n))\)
  3. \(f(n) = O(g(n))\)
  4. \(g(n) = O(f(n))\)
  5. \(g(n) = O(f(n))\)
  6. \(f(n) = O(g(n))\)

2-11

For all \(n > 3\), \(n^2 <= 2^n\) with a constant of 1. Therefore, \(n^2 = O(2^n)\).

2-12

  1. \(1\)
  2. \(2\)
  3. \(2\)

Chapter 3: Data Structures

3-1

def is_balanced(expression):
    stack = []
    for char in expression:
        if char == '(':
            stack.append(char)
        else:  # char == ')'
            if not stack:
                return False
            stack.pop()
    return not stack

3-3

  1. Let's say that we have an array of size 10 that contains 6 elements. Delete two, insert two, repeat.
  2. 1/3 instead of half.

3-5

  1. 1/4
  2. 1/2

3-7

We maintain the current max and min. Insert should compare the given value to the max and the min (and potentially substitute). Delete should check and see if the value to be deleted is the max/min, if it is set max/min to the predecessor/successor.

3-9

Find and delete the smallest key in \(S_2\) (this takes \(O(h)\)). Set this key as a new root. The left subtree should be \(S_1\), the right subtree should be \(S_2\).

3-11

Precalculate the answers! Store in a dictionary: key = i + j, value = \(min(x_i...x_j)\).

3-21

def equal(tree1, tree2):
    if not tree1:
        return not tree2
    if not tree2:
        return not tree1
    return (tree1.key == tree2.key and
            equal(tree1.left, tree2.left) and
            equal(tree1.right, tree2.right))

3-23

def reverse(linked_list):
    if not linked_list or not linked_list.next:
        return linked_list
    rest = reverse(linked_list.next)
    linked_list.next.next = linked_list
    linked_list.next = None
    return rest

3-25

Check Counter(magazine) against search string.

3-27

With extra space:

def has_loop(linked_list, seen=set()):
    if not linked_list:
        return False
    elif linked_list.key in seen:
        return True
    else:
        seen.add(linked_list.key)
        return has_loop(linked_list.next, seen)

3-29

We can do this in linear time with some extra space. Maintain a dictionary from word pair to count. Traverse the word pair, finding the counts. Then look for the pair with the highest count.

Chapter 4: Sorting and Searching

4-1

Sort the list of players by rating (\(O(n \log n)\)). Then put the lowest rated in one group and the highest rated in another group.

4-3

Sort the sequence of real numbers. Then, pair the largest number with the smallest, the second largest with the second smallest, and so on.

4-5

Add the elements to a hash table. The keys of the hash table should be the number, the value should be the frequency (i.e. first time the key is added, set the value to 1, every other time, increment the key). Then find the largest key. This algorithm is linear.

Another, slower algorithm, is as follows:

  1. Sort the list
  2. Traverse the list, for each item count the occurrences using binary search.
  3. Return the item with the largest number of occurrences.

Steps 1 and 2 are \(O(n \log n)\).

4-7

Use hashing to make all of these linear (so use a computer)!

4-9

Note that both of these problems can be done linearly with hash tables!

  1. Sort A. Iterate over B, for each item, check if it exist in A using binary search. Maintain then return the items that exist in A. This algorithm is \(O(n \log n)\).
  2. Maintain a set to return. Traverse sets A and B the same time. If the two items match, add this element to the return set. If the two items don't match, increment the index of A or B with the smaller element. This is similar to the merge of mergesort.

4-11

Use hash table counting.

4-13

  1. Doesn't matter, both constant.
  2. The heap is better. It's \(O(\log n)\) to delete rather than \(O(n)\) for deleting from a sorted list.
  3. The heap is better, creation is linear if implemented well.
  4. The sorted list is much better, constant rather than linear.

Chapter 5: Graph Traversal

Chapter 6: Weighted Graph Algorithms

6-1

A.

+---+   +---+     +---+
| A |   | B |     | C |
+---+   +---+     +---+
   \   /    \    /     \
   +---+     +---+     +---+
   | D |     | E |     | F |
   +---+     +---+     +---+
       \
         +---+     +---+
         | G |-----| H |
         +---+     +---+
        /
  +---+   +---+
  | I |---| J |
  +---+   +---+
+---+   +---+   +---+   +---+
| A |---| B |   | C |   | D |
+---+   +---+   +---+   +---+
  |       |       |       |
+---+   +---+   +---+   +---+
| E |   | F |   | G |   | H |
+---+   +---+   +---+   +---+
  |       |       |       |
+---+   +---+   +---+   +---+
| I |   | J |---| K |   | L |
+---+   +---+   +---+   +---+
  |                       |
+---+   +---+   +---+   +---+
| M |---| N |---| O |---| P |
+---+   +---+   +---+   +---+

B.

+---+   +---+     +---+
| A |   | B |     | C |
+---+   +---+     +---+
   \   /    \    /     \
   +---+     +---+     +---+
   | D |     | E |     | F |
   +---+     +---+     +---+
       \
         +---+     +---+
         | G |-----| H |
         +---+     +---+
        /
  +---+   +---+
  | I |---| J |
  +---+   +---+
+---+   +---+   +---+   +---+
| A |---| B |   | C |   | D |
+---+   +---+   +---+   +---+
  |       |       |       |
+---+   +---+   +---+   +---+
| E |   | F |   | G |   | H |
+---+   +---+   +---+   +---+
  |       |       |       |
+---+   +---+   +---+   +---+
| I |   | J |---| K |   | L |
+---+   +---+   +---+   +---+
  |                       |
+---+   +---+   +---+   +---+
| M |---| N |---| O |---| P |
+---+   +---+   +---+   +---+

C.

+---+   +---+     +---+
| A |---| B |-----| C |
+---+   +---+     +---+
 | \        \          \
 | +---+     +---+     +---+
 | | D |     | E |     | F |
 | +---+     +---+     +---+
 |     \
 |       +---+     +---+
 |       | G |-----| H |
 |       +---+     +---+
  \
  +---+   +---+
  | I |---| J |
  +---+   +---+
+---+   +---+   +---+   +---+
| A |---| B |   | C |---| D |
+---+   +---+   +---+   +---+
  |       |       |       |
+---+   +---+   +---+   +---+
| E |   | F |---| G |   | H |
+---+   +---+   +---+   +---+
  |       |
+---+   +---+   +---+   +---+
| I |   | J |---| K |---| L |
+---+   +---+   +---+   +---+
  |
+---+   +---+   +---+   +---+
| M |---| N |---| O |---| P |
+---+   +---+   +---+   +---+

Chapter 7: Combinatorial Search and Heuristic Methods

7-1

def backtrack(vector, n):
    if is_solution(vector, n):
        report(vector)
    else:
        for candidate in candidates(vector, n):
            backtrack(vector + [candidate], n)

def is_solution(vector, n):
    return len(vector) == n

def report(vector):
    pass

def candidates(vector, n):
    proper_item = len(vector) + 1
    return set(range(1, n + 1)) - {proper_item}

7-3