- 3/28: Exam 2 is postponed to Thu, April 6 (from March 30).
- 3/24: Strongly connected components example
Topics for next week: BFS, minimum spanning trees. Practice Problems:

- 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-8 (p. 611) [Counterexample to conjecture].
- Ex. 22.3-9 (p. 612) [Counterexample to conjecture].
- 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].

- 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:
- 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-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:
- 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.
- 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 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.
- 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.
- 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):
- Ex. 15.1-2 (p. 370) [Counterexample for greedy strategy].
- Ex. 15.1-4 (p. 370) [Output a solution].
- Ex. 15.1-3 (p. 370) [Addition of cost for each cut].
- Ex. 15.2-2 (p. 378) [Optimal solution to MCM].
- Ex. 15.3-3 (p. 389-390) [MCM with max instead of min].
- Ex. 15.3-5 (p. 390) [Rod cutting problem with limits].
- Ex. 15.4-3 (p. 396) [Memoized LCS].
- Ex. 15.4-5 (p. 397) [LMIS problem].
- Problem 15-1 (p. 404) [Longest path in a DAG].
- Problem 15-6 (p. 408) [Planning a company party].
- Ex. 16.2-2 (p. 427) [0-1 knapsack].
- Ex. 15.4-6 (p. 397) [O(nlogn) algorithm for LMIS].
- Problem 15-2 (p. 405) [Longest palindromic subsequence from first principles].
- Problem 15-2 (p. 405) [same problem; reduction to LCS, with a proof of correctness].
- Problem 15-3 (p. 405) [Bitonic TSP].
- Problem 15-4 (p. 405-406) [Printing neatly].
- Problem 15-5 (p. 406-408) [Edit distance].
- Problem 15-7 (p. 408-409) [Viterbi algorihtm].
- Problem 15-9 (p. 410) [Breaking a string].
- Problem 15-10 (p. 410-411) [Planning an investment strategy].
- 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:
- Ex. 33.3-2 (p. 1038) [nlogn lower bound for convex hull].
- Ex. 9.1-1 (p. 215) [second min].
- Ex. 9.1-2 (p. 215) [min and max].
- 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.
- 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:
- Prove that log(n!) = Theta(nlogn).
- Problem 7-4 (p. 188) [Quick sort and stack depth].
- Problem 7-6 (p. 189) [Fuzzy sorting of intervals].
- Ex. 8.2-4 (p. 197) [Application of counting sort].
- Prove the correctness of Radix sort using loop invariants.
- Ex. 8.3-4 (p. 200) [Application of radix sort].
- Ex. 8.4-5 (p. 204) [Application of bucket sort].
- Problem 8-2 (p. 206) [Sorting in-place in linear time].
- Problem 8-4 (p. 206-207) [Red/Blue water jugs].
- Ex. 9.2-1 (p. 219) [Select never calls empty array].
- 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.
- Ex. 9.3-1 (p. 223) [Select with groups of 7].
- Ex. 9.3-6 (p. 223) [kth quantiles].
- Ex. 9.3-7 (p. 223) [k elements closest to median].
- Ex. 9.3-9 (p. 223-224) [Application of median].
- Problem 9-1 (p. 224) [Largest i numbers].
- Problem 9-2 (p. 225) [Weighted median].
- Ex. 30.1-7 (p. 906) [Cartesian sum].
- 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:
- 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).

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