Difference between revisions of "Chapter 5"

From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search
Line 3: Line 3:
 
===Binary Search===
 
===Binary Search===
  
:[[5.1]]
+
:[[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.
 +
:• Suppose you know what <math>k</math> is. Give an <math>O(1)</math> algorithm to find the largest number in <math>A</math>.
 +
:• 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.
 +
[[5.1|Solution]]
  
  
:5.2
+
: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.
  
  
:[[5.3]]
+
:[[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) What is an optimal strategy if <math>n</math> in known?
 +
:(b) What is a good strategy if <math>n</math> is not known?
 +
[[5.3|Solution]]
  
  
:5.4
+
: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.
  
  
:[[5.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]]
  
  
:5.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>.
  
  
:[[5.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===
 
===Divide and Conquer Algorithms===

Revision as of 18:33, 14 September 2020

Divide and Conquer

Binary Search

5.1. Suppose you are given a sorted array of size n that has been circularly shifted positions to the right. For example, [35, 42, 5, 15, 27, 29] is a sorted array that has been circularly shifted positions, while [27, 29, 35, 42, 5, 15] has been shifted positions.
• Suppose you know what is. Give an algorithm to find the largest number in .
• Suppose you do not know what is. Give an algorithm to find the largest number in . For partial credit, you may give an algorithm.

Solution


5.2. A sorted array of size n contains distinct integers between and , with one element missing. Give an 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 . 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 in known?
(b) What is a good strategy if is not known?

Solution


5.4. You are given a unimodal array of 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 time.


5.5. Suppose that you are given a sorted sequence of distinct integers . Give an algorithm to determine whether there exists an index such that . For example, in [-10, -3, 3, 5, 7], . In [2, 3, 4, 5, 6, 7], there is no such .

Solution


5.6. Suppose that you are given a sorted sequence of distinct integers , drawn from 1 to where . Give an algorithm to find an integer that is not present in . For full credit, find the smallest such integer such that .


5.7. Let be an 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 in , or to determine that is not there. How many comparisons of 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