CS 6363: Design and Analysis of Computer Algorithms

CS 6363.004: Design and Analysis of Computer Algorithms (Spring 2017)

4/25: NP-completeness definitions, Instances of 3-CNF-SAT and Subset Sum
- Ex. 34.1-2 (p. 1060) [Longest cycle].
- Ex. 34.2-1 (p. 1065) [Graph isomorphism].
- Ex. 34.2-3 (p. 1065) [Hamiltonian cycle].
- Ex. 34.2-6 (p. 1066) [Hamiltonian path].
- Ex. 34.5-1 (p. 1100) [Subgraph isomorphism].
- Ex. 34.5-2 (p. 1100) [0-1 IP].
- Ex. 34.5-5 (p. 1101) [Set partition].
- Ex. 34.5-7 (p. 1101) [Longest simple cycle].
- Ex. 34.5-6 (p. 1101) [Hamiltonian path].

4/20: Sample run of Edmonds-Karp algorithm for maximum flow
- Ex. 26.1-1 (p. 712) [Splitting an edge]. Level: C.
- Ex. 26.1-2 (p. 713) [Reducing multiple sources/sinks to single source/sink]. Level: C.
- Ex. 26.1-7 (p. 714) [Vertex capacities]. Level: B.
- Ex. 26.2-6 (p. 730-731) [Sources and sinks with capacities]. Level: B.
- Ex. 26.2-11 (p. 731) [Edge connectivity]. Level: AB.
- Ex. 26.2-13 (p. 731) [Min cut with fewest edges]. Level: AB.
- Problem 26-1 (p. 760-761) [Escape problem]. Level: AB.
- 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).

4/19: Topics for final exam on Thu, May 4

4/13: Topics for next week: Maximum flow problem (Ch 26), NP-completeness (Ch 34).
Exam viewing: Fri, Apr 14, 10:00 AM - 12:00 noon, or, next week, during office hours.
Sample runs of APSP algorithms
Practice problem: Given a directed graph G=(V,E), with positive integer weights w:E-->Z+, and a source vertex s in V, write an efficient algorithm that computes for each vertex u in V, RT(u) = delta(u,s) + delta(s,u), and stores it in the field u.rt. RT(u) is the round-trip distance between u and s.

4/12: Sample runs of shortest path algorithms
4/11: MST problems:
- 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]. Level: A.
- Problem 23-3 (p. 640) [Bottleneck spanning tree].
- Problem 23-4 (p. 641) [Alternative MST algorithms].
Shortest path problems:
- Ex. 24.1-3 (p. 654) [Early exit for Bellman-Ford algorithm].
- Ex. 24.1.6 (p. 655) [Finding a negative-weight cycle]. Level: AB.
- 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]. Level: AB.
- Problem 24-5 (p. 680-681) [Min mean cycle]. Level: A.
- 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].

4/4: Strongly connected components algorithm (corrected version)

3/28: Exam 2 is postponed to Thu, April 6 (from March 30).
Pseudocode for some DFS algorithms

3/24: Strongly connected components example
Topics for next week: BFS, minimum spanning trees. Practice Problems:
1. Ex. 22.1-4 (p. 593) [Underlying undirected graph].
2. Ex. 22.2-7 (p. 602) [Verify if given graph is bipartite]. Solve this problem using BFS/DFS.
3. Ex. 22.2-8 (p. 602) [Diameter of tree, with proof].
4. Ex. 22.3-5 (p. 611) [Proof of DFS properties].
5. Ex. 22.3-8 (p. 611) [Counterexample to conjecture].
6. Ex. 22.3-9 (p. 612) [Counterexample to conjecture].
7. Ex. 22.3-10 (p. 612) [Output type of each edge].
8. Ex. 22.3-11 (p. 612) [DFS example].
9. Ex. 22.3-12 (p. 612) [Connected components].
10. Ex. 22.4.2 (p. 614) [Count number of paths in a DAG].
11. Ex. 22.4.5 (p. 615) [Alternate algorithm for topological ordering].
12. Problem 22-1 (p. 621) [Classifying edges by BFS].
13. Problem 22-2, parts d,f (p. 621-622) [Articulation points, bridges].

3/21: Example to illustrate computation of bridges and cut vertices
Topics for exam 2 on Thu, March 30: Contents of lectures 1-20 (Divide and conquer, Lower bounds, Dynamic Programming, Greedy algorithms, Graph representations, DFS). Note that the exam covers all topics covered in class until the end of this week, including the topics covered in exam 1. There will be more problems from newer topics.

3/7: Practice problems:
1. Ex. 16.1-2 (p. 422) [Alternate greedy strategy].
2. Ex. 16.1-3 (p. 422) [Counterexamples].
3. Ex. 16.1-4 (p. 422) [Interval-graph coloring].
4. Ex. 16.2-1 (p. 427) [Fractional knapsack].
5. Ex. 16.2-4 (p. 427-428) [Skating across ND].
6. Ex. 16.2-5 (p. 428) [Covering points with unit intervals].
7. Ex. 16.2-6 (p. 428) [Fractional knapsack in O(n) time].
8. Problem 16-2 (p. 447) [Scheduling to minimize average completion time].

3/2: Topics for next week: greedy algorithms (Ch 16), Graphs (Ch 21). More DP problems:
1. 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.
2. 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.
3. Modification of RCP: sizes that have value are given as a sorted array s[1..k], with s_1 < s_2 < ... < s_k. A rode 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.
4. 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.
5. 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.

2/28: Exam viewing: Wed, Mar 1, 8:00-10:30 AM, or later, during office hours.

2/23: Dynamic programming problems (for this week and next week):
1. Ex. 15.1-2 (p. 370) [Counterexample for greedy strategy].
2. Ex. 15.1-4 (p. 370) [Output a solution].
3. Ex. 15.1-3 (p. 370) [Addition of cost for each cut].
4. Ex. 15.2-2 (p. 378) [Optimal solution to MCM].
5. Ex. 15.3-3 (p. 389-390) [MCM with max instead of min].
6. Ex. 15.3-5 (p. 390) [Rod cutting problem with limits].
7. Ex. 15.4-3 (p. 396) [Memoized LCS].
8. Ex. 15.4-5 (p. 397) [LMIS problem].
9. Problem 15-1 (p. 404) [Longest path in a DAG].
10. Problem 15-6 (p. 408) [Planning a company party].
11. Ex. 16.2-2 (p. 427) [0-1 knapsack].
12. Ex. 15.4-6 (p. 397) [O(nlogn) algorithm for LMIS].
13. Problem 15-2 (p. 405) [Longest palindromic subsequence from first principles].
14. Problem 15-2 (p. 405) [same problem; reduction to LCS, with a proof of correctness].
15. Problem 15-3 (p. 405) [Bitonic TSP].
16. Problem 15-4 (p. 405-406) [Printing neatly].
17. Problem 15-5 (p. 406-408) [Edit distance].
18. Problem 15-7 (p. 408-409) [Viterbi algorihtm].
19. Problem 15-9 (p. 410) [Breaking a string].
20. Problem 15-10 (p. 410-411) [Planning an investment strategy].
21. Problem 15-11 (p. 411) [Inventory planning].

2/9: Topics for mid-term exam 1 on Thu, Feb 16: Lectures 1-9: Order notation, mathematical method, recurrences, divide and conquer. Closed book, closed notes.

2/9: Topics for next week (Feb 14): Dynamic programming (Ch 15).
Problems:
1. Ex. 33.3-2 (p. 1038) [nlogn lower bound for convex hull].
2. Ex. 9.1-1 (p. 215) [second min].
3. Ex. 9.1-2 (p. 215) [min and max].
4. 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.
5. 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.

2/3: Topics for next week (Feb 7,9): Closest pair of points, Lower bounds for sorting, Dynamic programming: Rod-cutting problem.
Problems:
1. Prove that log(n!) = Theta(nlogn).
2. Problem 7-4 (p. 188) [Quick sort and stack depth].
3. Problem 7-6 (p. 189) [Fuzzy sorting of intervals].
4. Ex. 8.2-4 (p. 197) [Application of counting sort].
5. Prove the correctness of Radix sort using loop invariants.
6. Ex. 8.3-4 (p. 200) [Application of radix sort].
7. Ex. 8.4-5 (p. 204) [Application of bucket sort].
8. Problem 8-2 (p. 206) [Sorting in-place in linear time].
9. Problem 8-4 (p. 206-207) [Red/Blue water jugs].
10. Ex. 9.2-1 (p. 219) [Select never calls empty array].
11. Suppose Select(A, k) returns x=A[q] as the kth smallest element of A[1..n], prove that q=k, A[1..q-1] <= x, and, A[q+1..n] > x.
12. Ex. 9.3-1 (p. 223) [Select with groups of 7].
13. Ex. 9.3-6 (p. 223) [kth quantiles].
14. Ex. 9.3-7 (p. 223) [k elements closest to median].
15. Ex. 9.3-9 (p. 223-224) [Application of median].
16. Problem 9-1 (p. 224) [Largest i numbers].
17. Problem 9-2 (p. 225) [Weighted median].
18. Ex. 30.1-7 (p. 906) [Cartesian sum].
19. Ex. 30.2-8 (p. 914-915) [Chirp transform].
Programming projects:
- Implement and compare performance of Insertion sort, Quicksort, Dual-pivot quicksort, and merge sort, on large, randomly generated inputs.
- Compare the performances of the naive algorithms for Select(A, k) with the O(n) algorithms (randomized and deterministic).
- See if Radix sort, applied on arrays of longs, runs faster than merge sort. Try large values of n, up to the limit on your machine.
- Implement Graham's algorithm for convex hulls.
- Implement the FFT algorithm, writing your own Complex number class.
1/26: Topics for next week (Jan 31, Feb 2): Median (Ch 9), Geometric algorithms (Ch 33): Convex hull, closest pair of points, Linear-time sorting and lower bounds for comparison-based sorting (Ch 8).

1/24: Problems:

      1. Ex. 4.1-5 (p. 75).  Prove the correctness of the resulting O(n) algorithm.
      2. Problem 4-5 (p.109-110)  [Chip testing].
      3. Problem 7-2, part b (p. 186)  [Quick sort with 3-way partition].
      4. Ex. 7.4-5 (p. 185).  Quick sort with Insertion sort.
      5. Ex. 6.4-2 (p. 160) [Loop invariant for correctness of heap sort].

1/20: Topics for next week (Jan 24, 26): Maximum subarray sum (Sec 4.1), Quick sort (Ch 7), Median (Ch 9), Multiplication of n-bit integers (Problem 30-1), FFT (Ch 30).

      Practice problems: For all recurrences, assume that T(1)=1, if no base case is given.
      1. Iteration method:   T(n) <= 4T(n/2) + n^2, for n > 1.
      2. Substitution method:   T(n) = T(n-1) + n, for n > 1.
      3. Master method (special case): Problem 4-1, parts a-f (p. 107).
      4. Let Fib(n) be the n-th Fibonacci number.  Fib(0) = 0, Fib(1) = 1.
	 Fib(n) = Fib(n-1) + Fib(n-2), for n > 1.
	 Prove by induction: 1.5^n < Fib(n) < 1.7^n, for n >= 11.  [Fib(11)=89, Fib(12)=144].
      5. Prove by induction that the sum of Fib(i), i=0..n, is equal to Fib(n+2) - 1.
      6. Write an O(n) algorithm for the following problem:
      	 given a sorted array A[1..n] of integers and an integer x,
	 find how many pairs of i and j exist (1 <= i < j <=n) with A[i]+A[j]=x.
	 Prove its correctness using loop invariants.

1/18: Proof of correctness of insertion sort.

1/17: Slides used in class on loop invariants. Problems: correctness of merge, bubble sort, selection sort, factorial program.

1/16: Topics to be discussed in class this week (Jan 17,19): Proofs of correctness using loop invariants: Linear search, binary search, insertion sort, partition algorithm (of quick sort), merge algorithm (of merge sort); Recursive algorithms and their correctness using proof by induction.

1/13: Problems:
1. Problem A-1 (p. 1156-1157) [Bounding summations].
2. Ex. A.2-4 (p. 1156). [Approximate with integral].
3. Ex. 2.2-1 (p. 29) [Theta notation].
4. Problems 3-1 to 3-4 (p. 61-62) [Asymptotic growth rates].
5. Prove that ln(n) = o(n).

1/10: Practice problems: Find the running times of these algorithms.

1/10: Path to success:
- Try solving problems on your own. Form a study group. Meet at least one hour every week to discuss what was covered in class, and solutions to problems. Study regularly.
- Avoid looking at solutions before trying to solve problems by yourself. In this area, all answers are easy. Finding them is hard. In addition, you need to be able to prove that your algorithms are correct, to get full credit.
- Ask questions, if something is not clear. Seek help from instructor during office hours. Send email for appointment to meet outside office hours.
- Read complete description of algorithms and proofs from book. Notes taken during class is a supplement to, not a replacement of, the text book.
- Read the book ahead of class to gain full advantage of lectures. If you are familiar with what is coming, you will learn better.

1/10: Administrivia:
- You must be registered in this section to attend its lectures. UTD/CS department policy does not allow audits.
- You should have completed the prerequisites (Discrete math, Data structures) to this class already. You may not be enrolled in either of these prerequisite classes in the same semester you are enrolled in this class.
- Class notes will not be provided. Write your own notes, take pictures of screen, as needed.
- No recording (audio or video) of class is allowed.
- Attendance of all classes is required.
- Sample problems will be published (here) every week. Try solving them (and other problems) to test your knowledge.
- Some programming projects will also be published. Those interested in becoming experts in the implementation of algorithms are encouraged to try them.
- C-level: knowledge of algorithms discussed in class; ability to run these algorithms on given inputs.
- B-level: analysis of running times, proofs of correctness, algorithms for problems/exercises from book.
- A-level: design algorithms for new problems; solve "star" questions from book.

1/2: Course Syllabus

List of topics:
1. Introduction, Mathematical background, Running time analysis, Recurrences (Ch 1-4, App A)
2. Divide and conquer: merge sort, binary search, quick sort, geometric algorithms, median (Ch 2,7,9,33)
3. Sorting algorithms for special inputs: counting, radix, bucket sorts, lower bound (Ch 8)
4. Dynamic programming (Ch 15)
5. Greedy algorithms (Ch 16)
6. Graphs, DFS, BFS (Ch 22)
7. Minimum spanning trees, Disjoint sets (Ch 23, 21)
8. Shortest paths (Ch 24, 25)
9. Maximum flow problem (Ch 26)
10. NP-completeness (Ch 34)

Return to Balaji Raghavachari's home page.