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]]. An all-Beatles radio station plays nothing but recordings by the Beatles, selecting the next song at random (uniformly with replacement). They get through about ten songs per hour. I listened for 90 minutes before hearing a repeated song. Estimate how many songs the Beatles recorded.
+
:[[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>.
[[6.5|Solution]]
+
[[5.5|Solution]]
  
  
:6.6. Given strings <math>S</math> and <math>T</math> of length <math>n</math> and <math>m</math> respectively, find the shortest window in <math>S</math> that contains all the characters in <math>T</math> in expected <math>O(n + m)</math> time.
+
: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]]. Design and implement an efficient data structure to maintain a ''least recently used'' (LRU) cache of <math>n</math> integer elements. A LRU cache will discard the least recently accessed element once the cache has reached its capacity, supporting the following operations:
+
:[[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?
:• ''get(k)''– Return the value associated with the key <math>k</math> if it currently exists in the cache, otherwise return -1.
+
[[5.7|Solution]]
:• ''put(k,v)'' – Set the value associated with key <math>k</math> to <math>v</math>, or insert if <math>k</math> is not already present. If there are already <math>n</math> items in the queue, delete the least recently used item before inserting <math>(k, v)</math>. Both operations should be done in <math>O(1)</math> expected time.
 
[[6.7|Solution]]
 
  
===Randomized Algorithms===
+
===Divide and Conquer Algorithms===
  
:6.8. A pair of English words <math>(w_1, w_2)</math> is called a ''rotodrome'' if one can be circularly shifted (rotated) to create the other word. For example, the words (windup, upwind) are a rotodrome pair, because we can rotate “windup” two positions to the right to get “upwind.”
+
:5.8
:Give an efficient algorithm to find all rotodrome pairs among <math>n</math> words of length <math>k</math>, with a worst-case analysis. Also give a faster expected-time algorithm based on hashing.
 
  
  
:[[6.9]]. Given an array <math>w</math> of positive integers, where <math>w[i]</math> describes the weight of index <math>i</math>, propose an algorithm that randomly picks an index in proportion to its weight.
+
:[[5.9]]
[[6.9|Solution]]
 
  
  
:6.10. You are given a function ''rand7'', which generates a uniform random integer in the range 1 to 7. Use it to produce a function ''rand10'', which generates a uniform random integer in the range 1 to 10.
+
:5.10
  
  
:[[6.11]]. Let <math>0 < \alpha < 1/2</math> be some constant, independent of the input array length <math>n</math>. What is the probability that, with a randomly chosen pivot element, the partition subroutine from quicksort produces a split in which the size of both the resulting subproblems is at least <math>\alpha</math> times the size of the original array?
+
:[[5.11]]
[[6.11|Solution]]
 
  
  
:6.12. Show that for any given load <math>m/n</math>, the error probability of a Bloom filter is minimized when the number of hash functions is <math>k = exp(-1)/(m/n)</math>.
+
===Recurrence Relations===
  
 +
:5.12
 +
 +
 +
:[[5.13]]
 +
 +
 +
:5.14
 +
 +
 +
:[[5.15]]
 +
 +
 +
:5.16
  
  
 
Back to [[Chapter List]]
 
Back to [[Chapter List]]

Revision as of 18:33, 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


5.9


5.10


5.11


Recurrence Relations

5.12


5.13


5.14


5.15


5.16


Back to Chapter List