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<Edge> 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].