Give a linear-time algorithm that takes as input a directed acyclic graph G = (V,E) and two vertices s and t, and returns the number of simple paths from s to t in G. For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. Your algorithm needs only to count the simple paths, not list them.
Professor Harvey has always dreamed of inline skating across North
Dakota. She plans to cross the state on highway U.S. 2, which runs from Grand
Forks, on the eastern border with Minnesota, to Willston, near the western
border with Montana. The professor can carry two liters of water and she can
skate m miles before running out of water. Because North Dakota is
relatively flat, the professor does not have to worry about drinking water at
a greater rate on uphill sections than on flat or downhill sections. The
professor will start in Grand Forks with two full liters of water. Her
official North Dakota state map shows all the places along U.S. 2 at which she
can refill her water and the distances between these locations.
The professor's goal is to minimize the number of water stops along her route
across the state. Give an efficient method by which she can determine which
water stops she should make. Prove that your strategy yields an optimal
solution, and give the running time.
A certain string-processing language allows a programmer to break a
string into two pieces. Because this operation copies the string, it costs
n time units to break a string of n characters into two pieces.
Suppose a programmer wants to break a string into many pieces. The order in
which the breaks occur can affect the total amount of time used. For example,
suppose that the programmer wants to break a 20-character string after
characters 2, 8, and 10 (numbering the characters in ascending order from the
left-hand end, starting from 1). If she programs the breaks to occur in
left-to-right order, then the first break costs 20 time units, the second
break costs 18 time units (breaking the string from characters 3 to 20 at
character 8), and the third break costs 12 time units, totaling 50 time units.
If she programs the breaks to occur in right-to-left order, however, then the
first break costs 20 time units, the second break costs 10 time units, and the
third break costs 8 time units, totaling 38 time units. In yet another order,
she could break first at 8 (costing 20), then break the left piece at 2
(costing 8), and finally the right piece at 10 (costing 12), for a total cost
of 40.
Design an algorithm that, given the numbers of characters after which to
break, determines a least-cost way to sequence those breaks. More formally,
given a string S with n characters and an array
L[1..m] containing the break points, compute the lowest cost for
a sequence of breaks, along with a sequence of breaks that achieves this cost.
Problem 15-11, page 411. HINT: Formulate the solution for the final month of production (i.e., month n) and try to generalize from that.
Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence (16.2). Have your algorithm compute the sizes of c[i,j] as defined in recurrence (16.2) and also produce the maximum-size subset of mutually compatible activites. Assume that the inputs have been sorted as in equation (16.1). Compare the running time of your solution to the running time of GREEDY-ACTIVITY-SELECTOR.
Exercise 4.1-5, page 75 Solution
New: Exercise 4.5.1, page 96 Solution
Exercise 4.5-3, page 97
Use the substitution method to prove that the recurrence T(n) = T(n-1) + Θ(n) has the solution T(n) = Θ(n2), as claimed at the beginning of Section 7.2.
What is the running time of QUICKSORT when all elements of the array A have the same value?
Exercise 1.2-2, page 14
Problem 1-1, pp. 14-15; you only have to generate the answers for the first four columns (1 second to 1 day)
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = (41, 31, 26, 59, 58, 41).
Consider linear search (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in Θ-notation? Justify your answers.
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A = (41, 3, 57, 38, 26, 52, 49, 9)
A median of an array of n numbers is defined to be a value x in the array such that at least n/2 values in the array are ≤ x, and at least n/2 values in the array are ≥ x. (Note that at least one value in the array is ≤ x, since x is in the array.) A naive algorithm that operates in time Θ(n2) is to systematically take each value v in the array and count how many values in the array are ≤ v until the median is found. Describe an alternative algorithm that finds a median of an array in time Θ(nlg(n)).
Prove the following transitivity identity from page 51 of the text: if f(n) = Ω(g(n)) and g(n) = Ω(h(n)) then f(n) = Ω(h(n))
Apply the definition of O(f(n)) to prove the following reflexivity property: f(n) = O(f(n))
Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.