Difference between pages "Chapter 1" and "Chapter 10"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
Line 1: Line 1:
=Introduction to Algorithms=
+
=Dynamic Programming=
  
===Finding Counter Examples===
+
===Elementary Recurrences===
  
:[[1.1]]. Show that <math>a + b</math> can be less than <math>\min(a,b)</math>.
+
:[[10.1]]. Up to <math>k</math> steps in a single bound! A child is running up a staircase with <math>n</math> steps and can hop between 1 and <math>k</math> steps at a time. Design an algorithm to count how many possible ways the child can run up the stairs, as a function of <math>n</math> and <math>k</math>. What is the running time of your algorithm?
 +
[[10.1|Solution]]
  
  
:1.2. Show that <math>a \times b</math> can be less than <math>\min(a,b)</math>.
+
:10.2. Imagine you are a professional thief who plans to rob houses along a street of <math>n</math> homes. You know the loot at house <math>i</math> is worth <math>m_i</math>, for <math>1 \le i \le n</math>, but you cannot rob neighboring houses because their connected security systems will automatically contact the police if two adjacent houses are broken into. Give an efficient algorithm to determine the maximum amount of money you can steal without alerting the police.
  
  
:[[1.3]]. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the fastest route between <math>a</math> and <math>b</math> is not the shortest route.
+
:[[10.3]]. Basketball games are a sequence of 2-point shots, 3-point shots, and 1-point free throws. Give an algorithm that computes how many possible mixes (1s,2s,3s) of scoring add up to a given <math>n</math>. For <math>n</math> = 5 there are four possible solutions: (5, 0, 0), (2, 0, 1), (1, 2, 0), and (0, 1, 1).
 +
[[10.3|Solution]]
  
  
:1.4. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the shortest route between <math>a</math> and <math>b</math> is not the route with the fewest turns.
+
:10.4. Basketball games are a sequence of 2-point shots, 3-point shots, and 1-point free throws. Give an algorithm that computes how many possible scoring sequences add up to a given <math>n</math>. For <math>n</math> = 5 there are thirteen possible sequences, including 1-2-1-1, 3-2, and 1-1-1-1-1.
  
  
:[[1.5]]. The ''knapsack problem'' is as follows: given a set of integers <math>S = \{s_1, s_2, \ldots, s_n\}</math>, and a target number <math>T</math>, find a subset of <math>S</math> which adds up exactly to <math>T</math>. For example, there exists a subset within <math>S = \{1, 2, 5, 9, 10\}</math> that adds up to <math>T=22</math> but not <math>T=23</math>.
+
:[[10.5]]. Given an <math>s * t</math> grid filled with non-negative numbers, find a path from top left to bottom right that minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.
:Find counterexamples to each of the following algorithms for the knapsack problem. That is, giving an <math>S</math> and <math>T</math> such that the subset is selected using the algorithm does not leave the knapsack completely full, even though such a solution exists.
+
::(a) Give a solution based on Dijkstra’s algorithm. What is its time complexity as a function of <math>s</math> and <math>t</math>?
#Put the elements of <math>S</math> in the knapsack in left to right order if they fit, i.e. the first-fit algorithm.
+
::(b) Give a solution based on dynamic programming. What is its time complexity as a function of <math>s</math> and <math>t</math>?
#Put the elements of <math>S</math> in the knapsack from smallest to largest, i.e. the best-fit algorithm.
+
[[10.5|Solution]]
#Put the elements of <math>S</math> in the knapsack from largest to smallest.
 
  
 +
===Edit Distance===
  
:1.6. The ''set cover problem'' is as follows: given a set <math>S</math> of subsets <math> S_1, ..., S_m</math> of the universal set <math>U = \{1,...,n\}</math>, find the smallest subset of subsets <math>T \subset S</math> such that <math>\cup_{t_i \in T} t_i = U</math>.For example, there are the following subsets, <math>S_1 = \{1, 3, 5\}</math>, <math>S_2 = \{2,4\}</math>, <math>S_3 = \{1,4\}</math>, and <math>S_4 = \{2,5\}</math> The set cover would then be <math>S_1</math> and <math>S_2</math>.
+
:10.6. Typists often make transposition errors exchanging neighboring characters, such as typing “setve” for “steve.” This requires two substitutions to fix under the conventional definition of edit distance.
 +
:Incorporate a swap operation into our edit distance function, so that such neigh-
 +
boring transposition errors can be fixed at the cost of one operation.
  
:Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.
 
  
 +
:[[10.7]]. Suppose you are given three strings of characters: <math>X</math>, <math>Y</math>, and <math>Z</math>, where <math>|X| = n</math>, <math>|Y| = m</math>, and <math>|Z| = n + m</math>. <math>Z</math> is said to be a shuffle of <math>X</math> and <math>Y</math> iff <math>Z</math> can be formed by interleaving the characters from <math>X</math> and <math>Y</math> in a way that maintains the left-to-right ordering of the characters from each string.
 +
:(a) Show that cchocohilaptes is a shuffle of chocolate and chips, but chocochilatspe is not.
 +
:(b) Give an efficient dynamic programming algorithm that determines whether <math>Z</math> is a shuffle of <math>X</math> and <math>Y</math>. (Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric.)
 +
[[10.7|Solution]]
  
:[[1.7]]. The ''maximum clique problem'' in a graph <math>G = (V, E)</math> asks for the largest subset <math>C</math> of vertices <math>V</math> such that there is an edge in <math>E</math> between every pair of vertices in <math>C</math>. Find a counterexample for the following algorithm: Sort the vertices of <math>G</math> from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered.
 
  
===Proofs of Correctness===
+
:10.8. The longest common substring (not subsequence) of two strings <math>X</math> and <math>Y</math> is the longest string that appears as a run of consecutive letters in both strings. For example, the longest common substring of photograph and tomography is ograph.
 +
:(a) Let <math>n = |X|</math> and <math>m = |Y|</math>. Give a <math>\Theta (nm)</math> dynamic programming algorithm for longest common substring based on the longest common subsequence/edit distance algorithm.
 +
:(b) Give a simpler <math>\Theta (nm)</math> algorithm that does not rely on dynamic programming.
  
:1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants <math> c \geq 2</math>.
 
  multiply(<math>y,z</math>)
 
  #Return the product <math>yz</math>.
 
      ''if'' <math>z=0</math> ''then'' return(0) ''else''
 
        return(multiply(<math>cy,\lfloor z/c \rfloor)+y \cdot (z\,\bmod\,c</math>))
 
  
 +
:[[10.9]]. The ''longest common subsequence (LCS)'' of two sequences <math>T</math> and <math>P</math> is the longest sequence <math>L</math> such that <math>L</math> is a subsequence of both <math>T</math> and <math>P</math>. The ''shortest common supersequence (SCS)'' of <math>T</math> and <math>P</math> is the smallest sequence <math>L</math> such that both <math>T</math> and <math>P</math> are a subsequence of <math>L</math>.
 +
:(a) Give efficient algorithms to find the LCS and SCS of two given sequences.
 +
:(b) Let <math>d(T, P)</math> be the minimum edit distance between <math>T</math> and <math>P</math> when no substitutions are allowed (i.e., the only changes are character insertion and deletion). Prove that <math>d(T, P) = |SCS(T, P)| - |LCS(T, P)|</math> where <math>|SCS(T, P)| (|LCS(T, P)|)</math> is the size of the shortest SCS (longest LCS) of <math>T</math> and <math>P</math>.
 +
[[10.9|Solution]]
  
  
:[[1.9]]. Prove the correctness of the following algorithm for evaluating a polynomial. P(x) = <math>a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0</math>
+
:10.10. Suppose you are given <math>n</math> poker chips stacked in two stacks, where the edges of all chips can be seen. Each chip is one of three colors. A turn consists of choosing a color and removing all chips of that color from the tops of the stacks. The goal is to minimize the number of turns until the chips are gone.
    horner(<math>A,x</math>)
+
:For example, consider the stacks <math>(RRGG, GBBB)</math>. Playing red, green, and then blue suffices to clear the stacks in three moves. Give an <math>O(n^2)</math> dynamic programming algorithm to find the best strategy for a given pair of chip piles.
      <math>p = A_n</math>
 
      for <math>i</math> from <math>n-1</math> to <math>0</math>
 
              <math>p = p*x+A_i</math>
 
      return <math>p</math>
 
  
:1.10. Prove the correctness of the following sorting algorithm.
+
===Greedy Algorithms===
    bubblesort (<math>A</math> : list[<math>1 \dots n</math>])
 
      for <math>i</math> from <math>n</math> to <math>1</math>
 
          for <math>j</math> from <math>1</math> to <math>i-1</math>
 
              if (<math>A[j] > A[j+1]</math>)
 
                  swap the values of <math>A[j]</math> and <math>A[j+1]</math>
 
  
 +
:[[10.11]]
  
:[[1.11]]. The ''greatest common divisor of positive'' integers <math>x</math> and <math>y</math> is the largest integer <math>d</math> such that <math>d</math> divides <math>x</math> and <math>d</math> divides <math>y</math>. Euclid’s algorithm to compute <math>gcd(x, y)</math> where <math>x > y</math> reduces the task to a smaller problem:
 
  
:::::<math>gcd(x, y) = gcd(y, x mod y)</math>
+
:10.12
  
:Prove that Euclid’s algorithm is correct.
 
  
===Induction===
+
:[[10.13]]
  
:1.12. Prove that <math>\sum_{i=1}^n i</math>=<math>n(n+1)/2</math> for <math>n \geq 0</math>, by induction.
 
  
 +
:10.14
  
:[[1.13]]. Prove that <math>\sum_{i=1}^n i^2</math>=<math>n(n+1)(2n+1)/6</math> for <math>n \geq\ 0</math>, by induction.
 
  
 +
===Number Problems===
  
:1.14. Prove that <math>\sum_{i=1}^n i^3</math>=<math>n^2(n+1)^2/4</math> for <math>n \geq 0</math>, by induction.
+
:[[10.15]]
  
  
:[[1.15]]. Prove that <math> \sum_{i=1}^n i(i+1)(i+2)=n(n+1)(n+2)(n+3)/4 </math>
+
:10.16
  
  
:1.16. Prove by induction on <math>n \geq 1</math> that for every <math>a \neq 1</math>, <math> \sum_{i=0}^n a^i =\frac{a^{n+1}-1}{a-1}</math>}
+
:[[10.17]]
  
  
:[[1.17]]. Prove by induction that for <math>n \geq 1</math>, <math> \sum_{i=1}^n \frac{1}{i(i+1)} = \frac{n}{n+1} </math>
+
:10.18
  
  
:1.18. Prove by induction that <math>n^3+2n</math> is divisible by <math>3</math> for all <math>n \geq 0</math>.
+
:[[10.19]]
  
  
:[[1.19]]. Prove by induction that a tree with <math>n</math> vertices has exactly <math>n-1</math> edges.
+
:10.20
  
  
:1.20. Prove by mathematical induction that the sum of the cubes of the first <math>n</math> positive integers is equal to the square of the sum of these integers, i.e. <math> \sum_{i=1}^n i^3 = (  \sum_{i=1}^n i )^2 </math>
+
:[[10.21]]
  
===Estimation===
 
  
:[[1.21]]. Do all the books you own total at least one million pages? How many total pages are stored in your school library?
+
:10.22
  
  
:1.22. How many words are there in this textbook?
+
:[[10.23]]
  
  
:[[1.23]]. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head.
+
:10.24
  
  
:1.24. Estimate how many cities and towns there are in the United States.
+
:[[10.25]]
  
  
:[[1.25]]. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer.
+
:10.26
  
  
:1.26. How many Starbucks or McDonald’s locations are there in your country?
+
===Graphing Problem===
  
 +
:[[10.27]]
  
:[[1.27]]. How long would it take to empty a bathtub with a drinking straw?
 
  
 +
:10.28
  
:1.28. Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds (millionths of a second)? Does your RAM memory access a word in more or less than a microsecond? How many instructions can your CPU execute in one year if the machine is left running all the time?
 
  
 +
:[[10.29]]
  
:[[1.29]]. A sorting algorithm takes 1 second to sort 1,000 items on your machine. How long will it take to sort 10,000 items. . .
 
::(a) if you believe that the algorithm takes time proportional to n2, and
 
::(b) if you believe that the algorithm takes time roughly proportional to n log n?
 
  
 +
===Design Problems===
  
===Implementation Projects===
+
:10.30
  
:1.30. Implement the two TSP heuristics of Section 1.1 (page 5). Which of them gives better solutions in practice? Can you devise a heuristic that works better than both of them?
 
  
 +
:[[10.31]]
  
:[[1.31]]. Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.8 (page 22). Write a program to find good ticket sets.
 
  
 +
:10.32
  
===Interview Problems===
 
  
:1.32. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.
+
:[[10.33]]
 +
 
 +
 
 +
:10.34
 +
 
 +
 
 +
:[[10.35]]
 +
 
  
 +
:10.36
  
:[[1.33]]. There are twenty-five horses. At most, five horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.
 
  
 +
:[[10.37]]
  
:1.34. How many piano tuners are there in the entire world?
 
  
 +
:10.38
  
:[[1.35]]. How many gas stations are there in the United States?
 
  
 +
===Interview Problems===
  
:1.36. How much does the ice in a hockey rink weigh?
+
:[[10.39]]
  
  
:[[1.37]]. How many miles of road are there in the United States?
+
:10.40
  
  
:1.38. On average, how many times would you have to flip open the Manhattan phone book at random in order to find a specific name?
+
:[[10.41]]
  
  
  
 
Back to [[Chapter List]]
 
Back to [[Chapter List]]

Revision as of 19:28, 13 September 2020

Dynamic Programming

Elementary Recurrences

10.1. Up to [math]\displaystyle{ k }[/math] steps in a single bound! A child is running up a staircase with [math]\displaystyle{ n }[/math] steps and can hop between 1 and [math]\displaystyle{ k }[/math] steps at a time. Design an algorithm to count how many possible ways the child can run up the stairs, as a function of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math]. What is the running time of your algorithm?

Solution


10.2. Imagine you are a professional thief who plans to rob houses along a street of [math]\displaystyle{ n }[/math] homes. You know the loot at house [math]\displaystyle{ i }[/math] is worth [math]\displaystyle{ m_i }[/math], for [math]\displaystyle{ 1 \le i \le n }[/math], but you cannot rob neighboring houses because their connected security systems will automatically contact the police if two adjacent houses are broken into. Give an efficient algorithm to determine the maximum amount of money you can steal without alerting the police.


10.3. Basketball games are a sequence of 2-point shots, 3-point shots, and 1-point free throws. Give an algorithm that computes how many possible mixes (1s,2s,3s) of scoring add up to a given [math]\displaystyle{ n }[/math]. For [math]\displaystyle{ n }[/math] = 5 there are four possible solutions: (5, 0, 0), (2, 0, 1), (1, 2, 0), and (0, 1, 1).

Solution


10.4. Basketball games are a sequence of 2-point shots, 3-point shots, and 1-point free throws. Give an algorithm that computes how many possible scoring sequences add up to a given [math]\displaystyle{ n }[/math]. For [math]\displaystyle{ n }[/math] = 5 there are thirteen possible sequences, including 1-2-1-1, 3-2, and 1-1-1-1-1.


10.5. Given an [math]\displaystyle{ s * t }[/math] grid filled with non-negative numbers, find a path from top left to bottom right that minimizes the sum of all numbers along its path. You can only move either down or right at any point in time.
(a) Give a solution based on Dijkstra’s algorithm. What is its time complexity as a function of [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math]?
(b) Give a solution based on dynamic programming. What is its time complexity as a function of [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math]?

Solution

Edit Distance

10.6. Typists often make transposition errors exchanging neighboring characters, such as typing “setve” for “steve.” This requires two substitutions to fix under the conventional definition of edit distance.
Incorporate a swap operation into our edit distance function, so that such neigh-

boring transposition errors can be fixed at the cost of one operation.


10.7. Suppose you are given three strings of characters: [math]\displaystyle{ X }[/math], [math]\displaystyle{ Y }[/math], and [math]\displaystyle{ Z }[/math], where [math]\displaystyle{ |X| = n }[/math], [math]\displaystyle{ |Y| = m }[/math], and [math]\displaystyle{ |Z| = n + m }[/math]. [math]\displaystyle{ Z }[/math] is said to be a shuffle of [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] iff [math]\displaystyle{ Z }[/math] can be formed by interleaving the characters from [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] in a way that maintains the left-to-right ordering of the characters from each string.
(a) Show that cchocohilaptes is a shuffle of chocolate and chips, but chocochilatspe is not.
(b) Give an efficient dynamic programming algorithm that determines whether [math]\displaystyle{ Z }[/math] is a shuffle of [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math]. (Hint: the values of the dynamic programming matrix you construct should be Boolean, not numeric.)

Solution


10.8. The longest common substring (not subsequence) of two strings [math]\displaystyle{ X }[/math] and [math]\displaystyle{ Y }[/math] is the longest string that appears as a run of consecutive letters in both strings. For example, the longest common substring of photograph and tomography is ograph.
(a) Let [math]\displaystyle{ n = |X| }[/math] and [math]\displaystyle{ m = |Y| }[/math]. Give a [math]\displaystyle{ \Theta (nm) }[/math] dynamic programming algorithm for longest common substring based on the longest common subsequence/edit distance algorithm.
(b) Give a simpler [math]\displaystyle{ \Theta (nm) }[/math] algorithm that does not rely on dynamic programming.


10.9. The longest common subsequence (LCS) of two sequences [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math] is the longest sequence [math]\displaystyle{ L }[/math] such that [math]\displaystyle{ L }[/math] is a subsequence of both [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math]. The shortest common supersequence (SCS) of [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math] is the smallest sequence [math]\displaystyle{ L }[/math] such that both [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math] are a subsequence of [math]\displaystyle{ L }[/math].
(a) Give efficient algorithms to find the LCS and SCS of two given sequences.
(b) Let [math]\displaystyle{ d(T, P) }[/math] be the minimum edit distance between [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math] when no substitutions are allowed (i.e., the only changes are character insertion and deletion). Prove that [math]\displaystyle{ d(T, P) = |SCS(T, P)| - |LCS(T, P)| }[/math] where [math]\displaystyle{ |SCS(T, P)| (|LCS(T, P)|) }[/math] is the size of the shortest SCS (longest LCS) of [math]\displaystyle{ T }[/math] and [math]\displaystyle{ P }[/math].

Solution


10.10. Suppose you are given [math]\displaystyle{ n }[/math] poker chips stacked in two stacks, where the edges of all chips can be seen. Each chip is one of three colors. A turn consists of choosing a color and removing all chips of that color from the tops of the stacks. The goal is to minimize the number of turns until the chips are gone.
For example, consider the stacks [math]\displaystyle{ (RRGG, GBBB) }[/math]. Playing red, green, and then blue suffices to clear the stacks in three moves. Give an [math]\displaystyle{ O(n^2) }[/math] dynamic programming algorithm to find the best strategy for a given pair of chip piles.

Greedy Algorithms

10.11


10.12


10.13


10.14


Number Problems

10.15


10.16


10.17


10.18


10.19


10.20


10.21


10.22


10.23


10.24


10.25


10.26


Graphing Problem

10.27


10.28


10.29


Design Problems

10.30


10.31


10.32


10.33


10.34


10.35


10.36


10.37


10.38


Interview Problems

10.39


10.40


10.41


Back to Chapter List