Difference between pages "Chapter 1" and "Chapter 4"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
Line 1: Line 1:
−
=Introduction to Algorithms=
+
=Sorting=
  
−
Problems
+
===Applications of Sorting: Numbers===
  
−
:[[1.1]]. Show that ''a'' + ''b'' can be less than ''min(a, b)''.
+
:[[4.1]]. The Grinch is given the job of partitioning <math>2n</math> players into two teams of <math>n</math> players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as ''unfairly'' as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in <math>O(n log n)</math> time.
 +
[[4.1|Solution]]
  
  
−
:1.2. Show that ''a'' × ''b'' can be less than ''min(a, b)''.
+
:4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, <math>S = {6, 13, 19, 3, 8}</math>, 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
 +
:(a) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x-y|</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
 +
:(b) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x - y|</math>. Your algorithm must run in <math>O(1)</math> worst-case time.
 +
:(c) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n log n)</math> worst-case time.
 +
:(d) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
  
  
−
:[[1.3]]. Design/draw a road network with two points ''a'' and ''b'' such that the fastest route between ''a'' and ''b'' is not the shortest route.
+
:[[4.3]]. Take a list of <math>2n</math> real numbers as input. Design an <math>O(n log n)</math> algorithm that partitions the numbers into <math>n</math> pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum over the three partitions.
 +
[[4.3|Solution]]
  
  
−
:1.4. Design/draw a road network with two points ''a'' and ''b'' such that the shortest route between ''a'' and ''b'' is not the route with the fewest turns.
+
:4.4. Assume that we are given <math>n</math> pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an <math>O(n)</math> algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
 +
:For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).
  
  
−
:[[1.5]]. The ''knapsack problem'' is as follows: given a set of integers ''S'' = {''s1, s2. . . , sn''}, and a target number ''T'', find a subset of ''S'' that adds up exactly to ''T''. For example, there exists a subset within ''S'' = {1, 2, 5, 9, 10} that adds up to ''T'' = 22 but not ''T'' = 23.
+
:[[4.5]]. The ''mode'' of a bag of numbers is the number that occurs most frequently in the set. The set {4, 6, 2, 4, 3, 1} has a mode of 4. Give an efficient and correct algorithm to compute the mode of a bag of <math>n</math> numbers.
 +
[[4.5|Solution]]
  
−
:Find counterexamples to each of the following algorithms for the knapsack problem. That is, give an ''S'' and ''T'' where the algorithm does not find a solution that leaves the knapsack completely full, even though a full-knapsack solution exists.
 
  
−
::(a) Put the elements of ''S'' in the knapsack in left to right order if they fit, that is, the first-fit algorithm.
+
:4.6. Given two sets <math>S_1</math> and <math>S_2</math> (each of size <math>n</math>), and a number <math>x</math>, describe an <math>O(n log n)</math> algorithm for finding whether there exists a pair of elements, one from <math>S_1</math> and one from <math>S_2</math>, that add up to <math>x</math>. (For partial credit, give a <math>\Theta(n^2)</math> algorithm for this problem.)
  
−
::(b) Put the elements of ''S'' in the knapsack from smallest to largest, that is, the best-fit algorithm.
 
  
−
::(c) Put the elements of ''S'' in the knapsack from largest to smallest.
+
:[[4.7]]. Give an efficient algorithm to take the array of citation counts (each count is a non-negative integer) of a researcher’s papers, and compute the researcher’s <math>h</math>-index. By definition, a scientist has index <math>h</math> if <math>h</math> of his or her <math>n</math> papers have been cited at least <math>h</math> times, while the other <math>n-h</math> papers each have no more than <math>h</math> citations.
 +
[[4.7|Solution]]
  
  
−
:1.6. The ''set cover problem'' is as follows: given a set ''S'' of subsets ''S1, . . . , Sm'' of the universal set ''U'' = {1, ..., ''n''}, find the smallest subset of subsets ''T ⊆ S'' such that ''∪ti∈T ti'' = ''U''. For example, consider the subsets ''S1'' = {1, 3, 5}, ''S2'' = {2, 4}, ''S3'' = {1, 4}, and ''S4'' = {2, 5}. The set cover of {1, . . . , 5} would then be ''S1'' and ''S2''.
+
:4.8. Outline a reasonable method of solving each of the following problems. Give the order of the worst-case complexity of your methods.
−
: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.
+
:(a) You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. Find out who did not pay.
 +
:(b) You are given a printed list containing the title, author, call number, and publisher of all the books in a school library and another list of thirty publishers. Find out how many of the books in the library were published by each company.
 +
:(c) You are given all the book checkout cards used in the campus library during the past year, each of which contains the name of the person who took out the book. Determine how many distinct people checked out at least one book.
  
  
−
:[[1.7]]. The ''maximum clique problem'' in a graph ''G'' = (''V'', ''E'') asks for the largest subset ''C'' of vertices ''V'' such that there is an edge in ''E'' between every pair of vertices in ''C''. Find a counterexample for the following algorithm: Sort the vertices of ''G'' 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.
+
:[[4.9]]. Given a set <math>S</math> of <math>n</math> integers and an integer <math>T</math>, give an <math>O(n^{k-1}log n)</math> algorithm to test whether <math>k</math> of the integers in <math>S</math> add up to <math>T</math>.
 +
[[4.9|Solution]]
  
  
−
:1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants ''c'' ≥ 2.
+
:4.10. We are given a set of <math>S</math> containing <math>n</math> real numbers and a real number <math>x</math>, and seek efficient algorithms to determine whether two elements of <math>S</math> exist whose sum is exactly <math>x</math>.
−
::Multiply(''y, z'')
+
:(a) Assume that <math>S</math> is unsorted. Give an <math>O(n log n)</math> algorithm for the problem.
−
:::''if z'' = 0 ''then'' return(0) ''else''
+
:(b) Assume that <math>S</math> is sorted. Give an <math>O(n)</math> algorithm for the problem.
−
:::return(Multiply(''cy'', [''z/c'']) + ''y'' · (''z'' mod ''c''))
 
  
  
−
:[[1.9]]. Prove the correctness of the following algorithm for evaluating a polynomial ''anxn + an−1xn−1 + · · · + a1x + a0''.
+
:[[4.11]]. Design an <math>O(n)</math> algorithm that, given a list of <math>n</math> elements, finds all the elements that appear more than <math>n/2</math> times in the list. Then, design an <math>O(n)</math> algorithm that, given a list of <math>n</math> elements, finds all the elements that appear more than <math>n/4</math> times.
−
::Horner(''a, x'')
+
[[4.11|Solution]]
−
:::''p'' = ''an''
 
−
:::for ''i'' from ''n'' − 1 to 0
 
−
::::''p'' = ''p · x'' + ''ai''
 
−
:::return ''p''
 
  
 +
===Applications of Sorting: Intervals and Sets===
  
−
:1.10
+
:4.12. Give an efficient algorithm to compute the union of sets <math>A</math> and <math>B</math>, where <math>n = max(|A|, |B|)</math>. The output should be an array of distinct elements that form the union of the sets.
 +
:(a) Assume that <math>A</math> and <math>B</math> are unsorted arrays. Give an <math>O(n log n)</math> algorithm for the problem.
 +
:(b) Assume that <math>A</math> and <math>B</math> are sorted arrays. Give an <math>O(n)</math> algorithm for the problem.
  
−
:[[1.11]]
 
  
−
:1.12
+
:[[4.13]]. A camera at the door tracks the entry time <math>a_i</math> and exit time <math>b_i</math> (assume <math>b_i > a_i</math>) for each of <math>n</math> persons <math>p_i</math> attending a party. Give an <math>O(n log n)</math> algorithm that analyzes this data to determine the time when the most people were simultaneously present at the party. You may assume that all entry and exit times are distinct (no ties).
 +
[[4.13|Solution]]
  
−
:[[1.13]]
 
  
−
:1.14
+
:4.14. Given a list <math>I</math> of <math>n</math> intervals, specified as <math>(x_i, y_i)</math> pairs, return a list where the overlapping intervals are merged. For <math>I = {(1, 3),(2, 6),(8, 10),(7, 18)}</math> the output should be {(1, 6),(7, 18)}. Your algorithm should run in worst-case <math>O(n log n)</math> time complexity.
  
−
:[[1.15]]
 
  
−
:1.16
+
:[[4.15]]. You are given a set <math>S</math> of <math>n</math> intervals on a line, with the <math>i</math>th interval described by its left and right endpoints <math>(l_i, r_i)</math>. Give an <math>O(n log n)</math> algorithm to identify a point <math>p</math> on the line that is in the largest number of intervals.
 +
:As an example, for <math>S = {(10, 40),(20, 60),(50, 90),(15, 70)}</math> no point exists in all four intervals, but <math>p = 50</math> is an example of a point in three intervals. You can assume an endpoint counts as being in its interval.
 +
[[4.15|Solution]]
  
−
:[[1.17]]
 
  
−
:1.18
+
:4.16. You are given a set <math>S</math> of <math>n</math> segments on the line, where segment <math>S_i</math> ranges from <math>l_i</math> to <math>r_i</math>. Give an efficient algorithm to select the fewest number of segments whose union completely covers the interval from 0 to <math>m</math>.
  
−
:[[1.19]]
+
===Heaps===
  
−
:1.20
+
:[[4.17]]
  
−
:[[1.21]]
 
  
−
:1.22
+
:4.18
  
−
:[[1.23]]
 
  
−
:1.24
+
:[[4.19]]
  
−
:[[1.25]]
 
  
−
:1.26
+
:4.20
  
−
:[[1.27]]
 
  
−
:1.28
+
===Quicksort===
  
−
:[[1.29]]
+
:[[4.21]]
  
−
:1.30
 
  
−
:[[1.31]]
+
:4.22
  
−
:1.32
 
  
−
:[[1.33]]
+
:[[4.23]]
  
−
:1.34
 
  
−
:[[1.35]]
+
:4.24
  
−
:1.36
 
  
−
:[[1.37]]
+
:[[4.25]]
  
−
:1.38
 
  
 +
:4.26
 +
 +
 +
:[[4.27]]
 +
 +
 +
===Mergesort===
 +
 +
:4.28
 +
 +
 +
:[[4.29]]
 +
 +
 +
:4.30
 +
 +
 +
===Other Sorting Alogrithims===
 +
 +
:[[4.31]]
 +
 +
 +
:4.32
 +
 +
 +
:[[4.33]]
 +
 +
 +
:4.34
 +
 +
 +
:[[4.35]]
 +
 +
 +
:4.36
 +
 +
 +
:[[4.37]]
 +
 +
 +
:4.38
 +
 +
 +
===Lower Bounds===
 +
 +
:[[4.39]]
 +
 +
 +
:4.40
 +
 +
 +
===Searching===
 +
 +
:[[4.41]]
 +
 +
 +
:4.42
 +
 +
 +
===Implementaion Challenges===
 +
 +
:[[4.43]]
 +
 +
 +
:4.44
 +
 +
 +
:[[4.45]]
 +
 +
 +
:4.46
 +
 +
===Interview Problems===
 +
 +
:[[4.47]]
 +
 +
 +
:4.48
 +
 +
 +
:[[4.49]]
 +
 +
 +
:4.50
 +
 +
 +
:[[4.51]]
 +
 +
 +
:4.52
 +
 +
 +
:[[4.53]]
  
  
 
Back to [[Chapter List]]
 
Back to [[Chapter List]]

Revision as of 19:35, 19 September 2020

Sorting

Applications of Sorting: Numbers

4.1. The Grinch is given the job of partitioning [math]\displaystyle{ 2n }[/math] players into two teams of [math]\displaystyle{ n }[/math] players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in [math]\displaystyle{ O(n log n) }[/math] time.

Solution


4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, [math]\displaystyle{ S = {6, 13, 19, 3, 8} }[/math], 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
(a) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x-y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.
(b) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x - y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(1) }[/math] worst-case time.
(c) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n log n) }[/math] worst-case time.
(d) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.


4.3. Take a list of [math]\displaystyle{ 2n }[/math] real numbers as input. Design an [math]\displaystyle{ O(n log n) }[/math] algorithm that partitions the numbers into [math]\displaystyle{ n }[/math] pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum over the three partitions.

Solution


4.4. Assume that we are given [math]\displaystyle{ n }[/math] pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an [math]\displaystyle{ O(n) }[/math] algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).


4.5. The mode of a bag of numbers is the number that occurs most frequently in the set. The set {4, 6, 2, 4, 3, 1} has a mode of 4. Give an efficient and correct algorithm to compute the mode of a bag of [math]\displaystyle{ n }[/math] numbers.

Solution


4.6. Given two sets [math]\displaystyle{ S_1 }[/math] and [math]\displaystyle{ S_2 }[/math] (each of size [math]\displaystyle{ n }[/math]), and a number [math]\displaystyle{ x }[/math], describe an [math]\displaystyle{ O(n log n) }[/math] algorithm for finding whether there exists a pair of elements, one from [math]\displaystyle{ S_1 }[/math] and one from [math]\displaystyle{ S_2 }[/math], that add up to [math]\displaystyle{ x }[/math]. (For partial credit, give a [math]\displaystyle{ \Theta(n^2) }[/math] algorithm for this problem.)


4.7. Give an efficient algorithm to take the array of citation counts (each count is a non-negative integer) of a researcher’s papers, and compute the researcher’s [math]\displaystyle{ h }[/math]-index. By definition, a scientist has index [math]\displaystyle{ h }[/math] if [math]\displaystyle{ h }[/math] of his or her [math]\displaystyle{ n }[/math] papers have been cited at least [math]\displaystyle{ h }[/math] times, while the other [math]\displaystyle{ n-h }[/math] papers each have no more than [math]\displaystyle{ h }[/math] citations.

Solution


4.8. Outline a reasonable method of solving each of the following problems. Give the order of the worst-case complexity of your methods.
(a) You are given a pile of thousands of telephone bills and thousands of checks sent in to pay the bills. Find out who did not pay.
(b) You are given a printed list containing the title, author, call number, and publisher of all the books in a school library and another list of thirty publishers. Find out how many of the books in the library were published by each company.
(c) You are given all the book checkout cards used in the campus library during the past year, each of which contains the name of the person who took out the book. Determine how many distinct people checked out at least one book.


4.9. Given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] integers and an integer [math]\displaystyle{ T }[/math], give an [math]\displaystyle{ O(n^{k-1}log n) }[/math] algorithm to test whether [math]\displaystyle{ k }[/math] of the integers in [math]\displaystyle{ S }[/math] add up to [math]\displaystyle{ T }[/math].

Solution


4.10. We are given a set of [math]\displaystyle{ S }[/math] containing [math]\displaystyle{ n }[/math] real numbers and a real number [math]\displaystyle{ x }[/math], and seek efficient algorithms to determine whether two elements of [math]\displaystyle{ S }[/math] exist whose sum is exactly [math]\displaystyle{ x }[/math].
(a) Assume that [math]\displaystyle{ S }[/math] is unsorted. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm for the problem.
(b) Assume that [math]\displaystyle{ S }[/math] is sorted. Give an [math]\displaystyle{ O(n) }[/math] algorithm for the problem.


4.11. Design an [math]\displaystyle{ O(n) }[/math] algorithm that, given a list of [math]\displaystyle{ n }[/math] elements, finds all the elements that appear more than [math]\displaystyle{ n/2 }[/math] times in the list. Then, design an [math]\displaystyle{ O(n) }[/math] algorithm that, given a list of [math]\displaystyle{ n }[/math] elements, finds all the elements that appear more than [math]\displaystyle{ n/4 }[/math] times.

Solution

Applications of Sorting: Intervals and Sets

4.12. Give an efficient algorithm to compute the union of sets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], where [math]\displaystyle{ n = max(|A|, |B|) }[/math]. The output should be an array of distinct elements that form the union of the sets.
(a) Assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are unsorted arrays. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm for the problem.
(b) Assume that [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are sorted arrays. Give an [math]\displaystyle{ O(n) }[/math] algorithm for the problem.


4.13. A camera at the door tracks the entry time [math]\displaystyle{ a_i }[/math] and exit time [math]\displaystyle{ b_i }[/math] (assume [math]\displaystyle{ b_i \gt a_i }[/math]) for each of [math]\displaystyle{ n }[/math] persons [math]\displaystyle{ p_i }[/math] attending a party. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm that analyzes this data to determine the time when the most people were simultaneously present at the party. You may assume that all entry and exit times are distinct (no ties).

Solution


4.14. Given a list [math]\displaystyle{ I }[/math] of [math]\displaystyle{ n }[/math] intervals, specified as [math]\displaystyle{ (x_i, y_i) }[/math] pairs, return a list where the overlapping intervals are merged. For [math]\displaystyle{ I = {(1, 3),(2, 6),(8, 10),(7, 18)} }[/math] the output should be {(1, 6),(7, 18)}. Your algorithm should run in worst-case [math]\displaystyle{ O(n log n) }[/math] time complexity.


4.15. You are given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] intervals on a line, with the [math]\displaystyle{ i }[/math]th interval described by its left and right endpoints [math]\displaystyle{ (l_i, r_i) }[/math]. Give an [math]\displaystyle{ O(n log n) }[/math] algorithm to identify a point [math]\displaystyle{ p }[/math] on the line that is in the largest number of intervals.
As an example, for [math]\displaystyle{ S = {(10, 40),(20, 60),(50, 90),(15, 70)} }[/math] no point exists in all four intervals, but [math]\displaystyle{ p = 50 }[/math] is an example of a point in three intervals. You can assume an endpoint counts as being in its interval.

Solution


4.16. You are given a set [math]\displaystyle{ S }[/math] of [math]\displaystyle{ n }[/math] segments on the line, where segment [math]\displaystyle{ S_i }[/math] ranges from [math]\displaystyle{ l_i }[/math] to [math]\displaystyle{ r_i }[/math]. Give an efficient algorithm to select the fewest number of segments whose union completely covers the interval from 0 to [math]\displaystyle{ m }[/math].

Heaps

4.17


4.18


4.19


4.20


Quicksort

4.21


4.22


4.23


4.24


4.25


4.26


4.27


Mergesort

4.28


4.29


4.30


Other Sorting Alogrithims

4.31


4.32


4.33


4.34


4.35


4.36


4.37


4.38


Lower Bounds

4.39


4.40


Searching

4.41


4.42


Implementaion Challenges

4.43


4.44


4.45


4.46

Interview Problems

4.47


4.48


4.49


4.50


4.51


4.52


4.53


Back to Chapter List

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