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