Practice problems:
Introduction, Order notation, Summations, Recurrences (Ch 1-4, App A):
Problem A-1 (p. 1156-1157) [Bounding summations].
Ex. A.2-4 (p. 1156). [Approximate with integral].
Ex. 2.2-1 (p. 29) [Theta notation].
Problems 3-1 to 3-4 (p. 61-62) [Asymptotic growth rates].
Prove that ln(n) = o(n).
Divide and conquer:
Problem 2-4, part d (p. 42) [Inversions].
Proof of correctness and RT analysis:
xsort(A, p, r): // Sort A[p..r]
n <-- r-p+1
if n <= 1 then return
if A[p] > A[r] then exchange A[p] <--> A[r]
if n = 2 then return
nb3 = n/3
xsort(A, p, r-nb3) // sort first two-thirds
xsort(A, p+nb3, r) // sort last two-thirds
xsort(A, p, r-nb3) // sort first two-thirds again
Partition, Quicksort, Select:
Problem 7-2 (p. 186-187) [Quicksort with equal element values].
Ex. 9.3-7 (p. 223) [k elements closest to median].
Ex. 9.3-6 (p. 223) [kth quantiles].
Problem 9-2 (p. 225) [Weighted median].
Problem 8-4, part c (p. 207). Water jugs.
Linear sorts:
Ex. 8.2-4 (p. 197) [Describe an algorithm that, ... preprocessing time.]
Prove using a loop invariant that Radix sort is correct.
Ex. 8.3-4 (p. 200) [Show how to sort n integers in ...]
Problem 8-2 (p. 206) [Sorting in place in linear time].
Divide and Conquer:
An array is bitonic, if it is monotonically increasing and then monotonically decreasing.
Find the maximum element of a bitonic array A[1..n].
Given a stream of n integers (n >> memory), where the number of its distinct
elements is smaller than the available memory, design an algorithm to find
the median of the stream.
Given a sorted array A[1..n], output its distinct elements D[1..d] and their
counts C[1..d]. For example, if A={1,4,4,5,5,5,5,8,8,9,9}, then D={1,4,5,8,9}
and C={1,2,4,2,2}. Related problem: Find the k^th smallest distinct element
of a sorted array. In the above example, if k=3, the output is 5.
Compute Gray codes for a given n. A Gray code is an ordering of all possible
n-bit binary numbers (2^n, in all), such that only one bit changes from one entry to the next.
Design an algorithm for the following problem: given an unsorted array A[1..n]
(of distinct positive integers), and a positive integer T, find the cardinality
of the largest subset of A whose sum is less than T.
Sorting lower bound:
Ex. 33.3-2 (p. 1038) [nlogn lower bound for convex hull].
Prove that there is no algorithm that uses only comparisons and swaps,
which rearranges the elements of a given array in O(n) time, so that
each element is within 10 places of its location in a sorted order.
Dynamic programming:
Ex. 15.1-2 (p. 370) [Counterexample for greedy strategy].
Ex. 15.1-3 (p. 370) [Addition of cost for each cut].
Ex. 15.1-4 (p. 370) [Output a solution].
Ex. 15.3-5 (p. 390) [Rod cutting problem with limits].
Modification of RCP: cutting a rod of length i into two pieces incurs a cost
of C_i. The input consists of two arrays P[1..n] and C[1..n]. The revenue
associated with a solution is now the sum of the pieces minus the costs of
making the cuts. Give a dynamic program to solve this problem.
Modification of RCP: sizes that have value are given as a sorted array s[1..k],
with s_1 < s_2 < ... < s_k. A rod of length s[i] generates a revenue of p[i].
Other sizes have no value unless they are cut into one of the above sizes.
Input: n, s[1..k], p[1..k]. Output: max revenue.
Modification of RCP: A given instance of RCP may have many different solutions
with the same maximum revenue. Consider the version of the problem, where
the goal is to find a solution that yields maximum revenue with the least number
of cuts. Develop a dynamic program for this problem.
Ex. 15.2-2 (p. 378) [Optimal solution to MCM].
Ex. 16.2-2 (p. 427) [0-1 knapsack].
Modification of ASP: Suppose, some activities are marked as special events.
A boolean array S[1..n] is given, and S[i]=True whenever a_i is a special event.
Consider the problem of finding a set of compatible activities to generate
maximum total profit, with the restriction that two consecutive events that
are selected cannot both be special. One or more non-special events must be
scheduled between two special events. Non-special events do not have this
restriction and any number of them can be scheduled back to back.
Design a dynamic program for the problem.
Ex. 15.4-5 (p. 397) [LMIS problem].
An alternating monotonic sequence (AMS) is a monotonically increasing sequence
which alternates between even and odd numbers. For example, {7,12,13,22} is an
AMS, but {7,12,14,21} is not (though it is a monotonic sequence). Describe
a dynamic program for finding a longest alternating monotonic subsequence of
a given sequence.
Greedy algorithms:
Ex. 16.1-2 (p. 422) [Alternate greedy strategy].
Ex. 16.1-3 (p. 422) [Counterexamples].
Ex. 16.1-4 (p. 422) [Interval-graph coloring].
Ex. 16.2-1 (p. 427) [Fractional knapsack].
Ex. 16.2-4 (p. 427-428) [Skating across ND].
Ex. 16.2-5 (p. 428) [Covering points with unit intervals].
Ex. 16.2-6 (p. 428) [Fractional knapsack in O(n) time].
Problem 16-1 (p. 446-447) [Coin changing].
Problem 16-2 (p. 447) [Scheduling to minimize average completion time].
Graphs: DFS, BFS:
Ex. 22.1-4 (p. 593) [Underlying undirected graph].
Ex. 22.2-7 (p. 602) [Verify if given graph is bipartite]. Solve this problem using BFS/DFS.
Ex. 22.2-8 (p. 602) [Diameter of tree, with proof].
Ex. 22.3-5 (p. 611) [Proof of DFS properties].
Ex. 22.3-10 (p. 612) [Output type of each edge].
Ex. 22.3-11 (p. 612) [DFS example].
Ex. 22.3-12 (p. 612) [Connected components].
Ex. 22.4-2 (p. 614) [Count number of paths in a DAG].
Ex. 22.4-5 (p. 615) [Alternate algorithm for topological ordering].
Problem 22-1 (p. 621) [Classifying edges by BFS].
Problem 22-2, parts d,f (p. 621-622) [Articulation points, bridges].
Prove that no edge of an undirected graph is a cross edge with respect to DFS.
Prove that if (u,v) is a cross edge for DFS on a directed graph, then u.dis > v.fin.
Write DFS algorithm for finding topological order of G that throws exception
if G is not a DAG by detecting back edges during DFS.
Write a function isDAG(G) that uses the output of DFS algorithm for topological
order and outputs whether G is a DAG.
Minimum spanning trees:
Ex. 23.1-1 (p. 629) [Min edge and MST].
Ex. 23.1-3 (p. 629) [Every MST edge is a light edge for some cut; write proof without assuming that the given tree was computed using Prim/Kruskal/generic MST algorithms].
Prove or disprove: if e=(u,v) is an edge in an MST, and (S,V-S) is a cut crossed by e, then e is a light edge for this cut.
Ex. 23.1-5 (p. 629) [MST and max edge in cycle].
Ex. 23.1-10 (p. 630) [Sensitivity analysis of MST edges].
Ex. 23.1-11 (p. 630) [MST after decreasing weight of edge].
Ex. 23.2-4,5,6 (p. 637) [Special cases of MST].
Ex. 23.2-8 (p. 637-638) [DAC algorithm for MST?].
Problem 23-1 (p. 638) [Second-best MST].
Problem 23-3 (p. 640) [Bottleneck spanning tree].
Problem 23-4 (p. 641) [Alternative MST algorithms].
Write an algorithm that tests if a graph G=(V,E) contains an MST that includes
a given edge e=(u,v) in E. If such an MST exists, the algorithm returns it.
Otherwise it returns null. Explain its correctness and analyze its RT.
Signature: List mstWithGivenEdge( Graph g, Edge e=(u,v) ).
Shortest paths:
Ex. 24.1-3 (p. 654) [Early exit for Bellman-Ford algorithm].
Ex. 24.1.6 (p. 655) [Finding a negative-weight cycle].
Ex. 24.2-3 (p. 657) [PERT].
Ex. 24.2-4 (p. 658) [Counting number of paths in a DAG].
Ex. 24.3-2 (p. 663) [Counterexample with negative edges to Dijkstra's algorithm].
Ex. 24.3-6 (p. 663) [Most reliable path].
Ex. 24.3-8 (p. 664) [Special case of shortest paths].
Problem 24-2 (p. 678) [Nesting boxes].
Problem 24-3 (p. 679). [Arbitrage].
Problem 24-5 (p. 680-681) [Min mean cycle].
Ex. 25.1-9 (p. 692) [Does graph contain negative cycle?].
Ex. 25.1-10 (p. 693) [Find number of edges in a negative cycle with fewest edges].
Ex. 25.2-6 (p. 700) [Detect negative cycle with Floyd-Warshall algorithm].
Given a directed graph G=(V,E) with weights on the edges, a source
vertex s \in V, and a spanning tree T of G rooted at s, write an
algorithm that tests in linear time whether T is a shortest path tree
of G (i.e., if T contains paths of length \delta(s,u) to all u \in V).
Maximum flows:
Ex. 26.1-1 (p. 712) [Splitting an edge].
Ex. 26.1-2 (p. 713) [Reducing multiple sources/sinks to single source/sink].
Ex. 26.1-7 (p. 714) [Vertex capacities].
Ex. 26.2-6 (p. 730-731) [Sources and sinks with capacities].
Ex. 26.2-11 (p. 731) [Edge connectivity].
Ex. 26.2-13 (p. 731) [Min cut with fewest edges].
Problem 26-1 (p. 760-761) [Escape problem].
Suppose an algorithm for finding a maximum flow has been run, and you have
the flow value through each edge. It is suspected that the program has
a bug, and so the output may be wrong. Write an efficient function to
verify that the flow is valid, and is actually a maximum flow of the graph.
Your function should also print a minimum (S,T)-cut that is used in the
proof of the maxflow-mincut theorem. What is its running time?
Prototype: boolean verifyMaxFlow(G, s, t, c, f).
NP-completeness:
Ex. 34.2-6 (p. 1066) [Ham-Path is in NP].
Ex. 34.5-2 (p. 1100) [Subgraph-isomorphism is NP-complete].
Ex. 34.5-5 (p. 1101) [Set-partition is NP-complete].
Problem 34-3 (p. 1103) [Graph coloring is NP-complete].
Problem 34-4 (p. 1104) [Scheduling with profits and deadlines].