Difference between pages "Chapter 6" and "Chapter 5"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
Line 1: Line 1:
−
=Hashing and Randomized Algorithms=
+
=Divide and Conquer=
  
−
===Probability===
+
===Binary Search===
  
−
:[[6.1]]. You are given <math>n</math> unbiased coins, and perform the following process to generate all heads. Toss all <math>n</math> coins independently at random onto a table. Each round consists of picking up all the tails-up coins and tossing them onto the table again. You repeat until all coins are heads.
+
:[[5.1]]. Suppose you are given a sorted array <math>A</math> of size n that has been circularly shifted <math>k</math> positions to the right. For example, [35, 42, 5, 15, 27, 29] is a sorted array that has been circularly shifted <math>k = 2</math> positions, while [27, 29, 35, 42, 5, 15] has been shifted <math>k = 4</math> positions.
−
:(a) What is the expected number of rounds performed by the process?
+
:• Suppose you know what <math>k</math> is. Give an <math>O(1)</math> algorithm to find the largest number in <math>A</math>.
−
:(b) What is the expected number of coin tosses performed by the process?
+
:• Suppose you do not know what <math>k</math> is. Give an <math>O(lg n)</math> algorithm to find the largest number in <math>A</math>. For partial credit, you may give an <math>O(n)</math> algorithm.
−
[[6.1|Solution]]
+
[[5.1|Solution]]
  
  
−
:6.2. Suppose we flip <math>n</math> coins each of known bias, such that <math>p_i</math> is the probability of the <math>i</math>th coin being a head. Present an efficient algorithm to determine the exact probability of getting exactly <math>k</math> heads given <math>p_1, . . . , p_n \in [0, 1]</math>.
+
:5.2. A sorted array of size n contains distinct integers between <math>1</math> and <math>n + 1</math> , with one element missing. Give an <math>O(log n)</math> algorithm to find the missing integer, without using any extra space.
  
  
−
:[[6.3]]. An inversion of a permutation is a pair of elements that are out of order.
+
:[[5.3]] Consider the numerical Twenty Questions game. In this game, the first player thinks of a number in the range 1 to <math>n</math>. The second player has to figure out this number by asking the fewest number of true/false questions. Assume that nobody cheats.
−
:(a) Show that a permutation of <math>n</math> items has at most <math>n(n - 1)/2</math> inversions. Which permutation(s) have exactly n(n - 1)/2 inversions?
+
:(a) What is an optimal strategy if <math>n</math> in known?
−
:(b) Let P be a permutation and <math>P^r</math> be the reversal of this permutation. Show that <math>P</math> and <math>P^r</math> have a total of exactly <math>n(n - 1)/2</math> inversions.
+
:(b) What is a good strategy if <math>n</math> is not known?
−
:(c) Use the previous result to argue that the expected number of inversions in a random permutation is <math>n(n - 1)/4</math>.
+
[[5.3|Solution]]
−
[[6.3|Solution]]
 
  
  
−
:6.4. A derangement is a permutation <math>p</math> of <math>{1, . . . , n}</math> such that no item is in its proper position, that is, <math>p_i \neq i</math> for all <math>1 \leq i \leq n</math>. What is the probability that a random permutation is a derangement?
+
:5.4. You are given a unimodal array of <math>n</math> distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element of a unimodal array that runs in <math>O(log n)</math> time.
  
−
===Hashing===
 
  
−
:[[6.5]]
+
:[[5.5]]. Suppose that you are given a sorted sequence of distinct integers <math>[a_1, a_2, . . . , a_n]</math>. Give an <math>O(lg n)</math> algorithm to determine whether there exists an index <math>i</math> such that <math>a_i = i</math>. For example, in [-10, -3, 3, 5, 7], <math>a_3 = 3</math>. In [2, 3, 4, 5, 6, 7], there is no such <math>i</math>.
 +
[[5.5|Solution]]
  
  
−
:6.6
+
:5.6. Suppose that you are given a sorted sequence of distinct integers <math>a = [a_1, a_2, . . . , a_n]</math>, drawn from 1 to <math>m</math> where <math>n < m</math>. Give an <math>O(lg n)</math> algorithm to find an integer <math>\leq m</math> that is not present in <math>a</math>. For full credit, find the smallest such integer <math>x</math> such that <math>1 \leq x \leq m</math>.
  
  
−
:[[6.7]]
+
:[[5.7]]. Let <math>M</math> be an <math>n * m</math> integer matrix in which the entries of each row are sorted in increasing order (from left to right) and the entries in each column are in increasing order (from top to bottom). Give an efficient algorithm to find the position of an integer <math>x</math> in <math>M</math>, or to determine that <math>x</math> is not there. How many comparisons of <math>x</math> with matrix entries does your algorithm use in worst case?
 +
[[5.7|Solution]]
  
 +
===Divide and Conquer Algorithms===
  
−
===Randomized Algorithms===
+
:5.8. Given two sorted arrays <math>A</math> and <math>B</math> of size <math>n</math> and <math>m</math> respectively, find the median of the <math>n + m</math> elements. The overall run time complexity should be <math>O(log(m + n))</math>.
  
−
:6.8
 
  
 +
:[[5.9]]. The largest subrange problem, discussed in Section 5.6, takes an array <math>A</math> of <math>n</math> numbers, and asks for the index pair <math>i</math> and <math>j</math> that maximizes <math>S = \sum_{k=1}^j A[k]</math>. Give an <math>O(n)</math> algorithm for largest subrange.
 +
[[5.9|Solution]]
  
−
:[[6.9]]
 
  
 +
:5.10. We are given <math>n</math> wooden sticks, each of integer length, where the <math>i</math>th piece has length <math>L[i]</math>. We seek to cut them so that we end up with <math>k</math> pieces of exactly the same length, in addition to other fragments. Furthermore, we want these <math>k</math> pieces to be as large as possible.
 +
:(a) Given four wood sticks, of lengths <math>L = {10, 6, 5, 3}</math>, what are the largest sized pieces you can get for <math>k = 4</math>? (Hint: the answer is not 3).
 +
:(b) Give a correct and efficient algorithm that, for a given <math>L</math> and <math>k</math>, returns the maximum possible length of the <math>k</math> equal pieces cut from the initial <math>n</math> sticks.
  
−
:6.10
 
  
 +
:[[5.11]]. Extend the convolution-based string-matching algorithm described in the text to the case of pattern matching with wildcard characters “*”, which match any character. For example, “sh*t” should match both “shot” and “shut”.
 +
[[5.11|Solution]]
  
−
:[[6.11]]
+
===Recurrence Relations===
  
 +
:5.12. In Section 5.3, it is asserted that any polynomial can be represented by a recurrence. Find a recurrence relation that represents the polynomial <math>a_n = n^2</math>.
  
−
:6.12
 
  
 +
:[[5.13]]. Suppose you are choosing between the following three algorithms:
 +
:• Algorithm <math>A</math> solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
 +
:• Algorithm <math>B</math> solves problems of size <math>n</math> by recursively solving two subproblems of size <math>n - 1</math> and then combining the solutions in constant time.
 +
:• Algorithm <math>C</math> solves problems of size <math>n</math> by dividing them into nine subproblems of size <math>n/3</math>, recursively solving each subproblem, and then combining the solutions in <math>\Theta(n^2)</math> time.
 +
:What are the running times of each of these algorithms (in big O notation), and which would you choose?
 +
[[5.13|Solution]]
 +
 +
 +
:5.14. Solve the following recurrence relations and give a <math>\Theta</math> bound for each of them:
 +
:(a) <math>T(n) = 2T(n/3) + 1</math>
 +
:(b) <math>T(n) = 5T(n/4) + n</math>
 +
:(c) <math>T(n) = 7T(n/7) + n</math>
 +
:(d) <math>T(n) = 9T(n/3) + n^2</math>
 +
 +
 +
:[[5.15]]. Use the master theorem to solve the following recurrence relations:
 +
:(a) <math>T(n) = 64T(n/4) + n^4</math>
 +
:(b) <math>T(n) = 64T(n/4) + n^3</math>
 +
:(c) <math>T(n) = 64T(n/4) + 128</math>
 +
[[5.15|Solution]]
 +
 +
 +
:5.16. Give asymptotically tight upper (Big Oh) bounds for <math>T(n)</math> in each of the following recurrences. Justify your solutions by naming the particular case of the master theorem, by iterating the recurrence, or by using the substitution method:
 +
:(a) <math>T(n) = T(n - 2) + 1</math>.
 +
:(b) <math>T(n) = 2T(n/2) + n lg^2 n</math>.
 +
:(c) <math>T(n) = 9T(n/4) + n^2</math>.
  
  
 
Back to [[Chapter List]]
 
Back to [[Chapter List]]

Revision as of 18:49, 14 September 2020

Divide and Conquer

Binary Search

5.1. Suppose you are given a sorted array [math]\displaystyle{ A }[/math] of size n that has been circularly shifted [math]\displaystyle{ k }[/math] positions to the right. For example, [35, 42, 5, 15, 27, 29] is a sorted array that has been circularly shifted [math]\displaystyle{ k = 2 }[/math] positions, while [27, 29, 35, 42, 5, 15] has been shifted [math]\displaystyle{ k = 4 }[/math] positions.
• Suppose you know what [math]\displaystyle{ k }[/math] is. Give an [math]\displaystyle{ O(1) }[/math] algorithm to find the largest number in [math]\displaystyle{ A }[/math].
• Suppose you do not know what [math]\displaystyle{ k }[/math] is. Give an [math]\displaystyle{ O(lg n) }[/math] algorithm to find the largest number in [math]\displaystyle{ A }[/math]. For partial credit, you may give an [math]\displaystyle{ O(n) }[/math] algorithm.

Solution


5.2. A sorted array of size n contains distinct integers between [math]\displaystyle{ 1 }[/math] and [math]\displaystyle{ n + 1 }[/math] , with one element missing. Give an [math]\displaystyle{ O(log n) }[/math] algorithm to find the missing integer, without using any extra space.


5.3 Consider the numerical Twenty Questions game. In this game, the first player thinks of a number in the range 1 to [math]\displaystyle{ n }[/math]. The second player has to figure out this number by asking the fewest number of true/false questions. Assume that nobody cheats.
(a) What is an optimal strategy if [math]\displaystyle{ n }[/math] in known?
(b) What is a good strategy if [math]\displaystyle{ n }[/math] is not known?

Solution


5.4. You are given a unimodal array of [math]\displaystyle{ n }[/math] distinct elements, meaning that its entries are in increasing order up until its maximum element, after which its elements are in decreasing order. Give an algorithm to compute the maximum element of a unimodal array that runs in [math]\displaystyle{ O(log n) }[/math] time.


5.5. Suppose that you are given a sorted sequence of distinct integers [math]\displaystyle{ [a_1, a_2, . . . , a_n] }[/math]. Give an [math]\displaystyle{ O(lg n) }[/math] algorithm to determine whether there exists an index [math]\displaystyle{ i }[/math] such that [math]\displaystyle{ a_i = i }[/math]. For example, in [-10, -3, 3, 5, 7], [math]\displaystyle{ a_3 = 3 }[/math]. In [2, 3, 4, 5, 6, 7], there is no such [math]\displaystyle{ i }[/math].

Solution


5.6. Suppose that you are given a sorted sequence of distinct integers [math]\displaystyle{ a = [a_1, a_2, . . . , a_n] }[/math], drawn from 1 to [math]\displaystyle{ m }[/math] where [math]\displaystyle{ n \lt m }[/math]. Give an [math]\displaystyle{ O(lg n) }[/math] algorithm to find an integer [math]\displaystyle{ \leq m }[/math] that is not present in [math]\displaystyle{ a }[/math]. For full credit, find the smallest such integer [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ 1 \leq x \leq m }[/math].


5.7. Let [math]\displaystyle{ M }[/math] be an [math]\displaystyle{ n * m }[/math] integer matrix in which the entries of each row are sorted in increasing order (from left to right) and the entries in each column are in increasing order (from top to bottom). Give an efficient algorithm to find the position of an integer [math]\displaystyle{ x }[/math] in [math]\displaystyle{ M }[/math], or to determine that [math]\displaystyle{ x }[/math] is not there. How many comparisons of [math]\displaystyle{ x }[/math] with matrix entries does your algorithm use in worst case?

Solution

Divide and Conquer Algorithms

5.8. Given two sorted arrays [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] of size [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math] respectively, find the median of the [math]\displaystyle{ n + m }[/math] elements. The overall run time complexity should be [math]\displaystyle{ O(log(m + n)) }[/math].


5.9. The largest subrange problem, discussed in Section 5.6, takes an array [math]\displaystyle{ A }[/math] of [math]\displaystyle{ n }[/math] numbers, and asks for the index pair [math]\displaystyle{ i }[/math] and [math]\displaystyle{ j }[/math] that maximizes [math]\displaystyle{ S = \sum_{k=1}^j A[k] }[/math]. Give an [math]\displaystyle{ O(n) }[/math] algorithm for largest subrange.

Solution


5.10. We are given [math]\displaystyle{ n }[/math] wooden sticks, each of integer length, where the [math]\displaystyle{ i }[/math]th piece has length [math]\displaystyle{ L[i] }[/math]. We seek to cut them so that we end up with [math]\displaystyle{ k }[/math] pieces of exactly the same length, in addition to other fragments. Furthermore, we want these [math]\displaystyle{ k }[/math] pieces to be as large as possible.
(a) Given four wood sticks, of lengths [math]\displaystyle{ L = {10, 6, 5, 3} }[/math], what are the largest sized pieces you can get for [math]\displaystyle{ k = 4 }[/math]? (Hint: the answer is not 3).
(b) Give a correct and efficient algorithm that, for a given [math]\displaystyle{ L }[/math] and [math]\displaystyle{ k }[/math], returns the maximum possible length of the [math]\displaystyle{ k }[/math] equal pieces cut from the initial [math]\displaystyle{ n }[/math] sticks.


5.11. Extend the convolution-based string-matching algorithm described in the text to the case of pattern matching with wildcard characters “*”, which match any character. For example, “sh*t” should match both “shot” and “shut”.

Solution

Recurrence Relations

5.12. In Section 5.3, it is asserted that any polynomial can be represented by a recurrence. Find a recurrence relation that represents the polynomial [math]\displaystyle{ a_n = n^2 }[/math].


5.13. Suppose you are choosing between the following three algorithms:
• Algorithm [math]\displaystyle{ A }[/math] solves problems by dividing them into five subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
• Algorithm [math]\displaystyle{ B }[/math] solves problems of size [math]\displaystyle{ n }[/math] by recursively solving two subproblems of size [math]\displaystyle{ n - 1 }[/math] and then combining the solutions in constant time.
• Algorithm [math]\displaystyle{ C }[/math] solves problems of size [math]\displaystyle{ n }[/math] by dividing them into nine subproblems of size [math]\displaystyle{ n/3 }[/math], recursively solving each subproblem, and then combining the solutions in [math]\displaystyle{ \Theta(n^2) }[/math] time.
What are the running times of each of these algorithms (in big O notation), and which would you choose?

Solution


5.14. Solve the following recurrence relations and give a [math]\displaystyle{ \Theta }[/math] bound for each of them:
(a) [math]\displaystyle{ T(n) = 2T(n/3) + 1 }[/math]
(b) [math]\displaystyle{ T(n) = 5T(n/4) + n }[/math]
(c) [math]\displaystyle{ T(n) = 7T(n/7) + n }[/math]
(d) [math]\displaystyle{ T(n) = 9T(n/3) + n^2 }[/math]


5.15. Use the master theorem to solve the following recurrence relations:
(a) [math]\displaystyle{ T(n) = 64T(n/4) + n^4 }[/math]
(b) [math]\displaystyle{ T(n) = 64T(n/4) + n^3 }[/math]
(c) [math]\displaystyle{ T(n) = 64T(n/4) + 128 }[/math]

Solution


5.16. Give asymptotically tight upper (Big Oh) bounds for [math]\displaystyle{ T(n) }[/math] in each of the following recurrences. Justify your solutions by naming the particular case of the master theorem, by iterating the recurrence, or by using the substitution method:
(a) [math]\displaystyle{ T(n) = T(n - 2) + 1 }[/math].
(b) [math]\displaystyle{ T(n) = 2T(n/2) + n lg^2 n }[/math].
(c) [math]\displaystyle{ T(n) = 9T(n/4) + n^2 }[/math].


Back to Chapter List

Retrieved from "https://algorist.com//algowiki/index.php?title=Chapter_6&oldid=253"