January 11 (Tue), 2005 Questionnaire, with discussion; syllabus and grading policy handed out. Informal definition of algorithm. A little history: Al-Khawarizmi. Computing the greatest common divisor. Euclid's algorithm for computing the GCD.
January 13 (Thu), 2005 HW1 assigned: exercises 1.2.1, 1.2.2, 1.3.4, 1.3.5, 1.4.10, due January 20. The sieve of Erathostenes. Termination and correctness of Euclid's algorithm (proved), with several variations. Sorting.
January 18 (Tue), 2005 Correctness: termination and partial correctness. Induction, Peano's first-order induction schema, and strong induction. Examples of proof of a recursive algorithm: factorial, in detail; BinarySearch, sketch.
January 20 (Thu), 2004 HW1 collected. Example of proof of a recursive algorithm: SelectionSort. The method of loop invariants. Examples of proof of iterative algorithm: iterative factorial (in detail), Linear-time algorithm for Maximum Contiguous Subvector (not in full detail).
January 25 (Tue), 2005 Q2. HW2 assigned, due Tuesday, Feb.1: 2.1.4, 2.1.10, 2.2.2 through 2.2.10. Introduction to time complexity analysis. Input size and characteristic operation, with examples for different problems. Computing the power "a to the n" in linear and logarithmic time: full example. Recurrence relations, forward and backward substitution.
January 27 (Thu), 2005 Q3. Analysis of correctness and time complexity of selection sort, including setting up a recurrence relation, attempting its solution by forward substitution, and solving it by backwards substitution, and checking the solution (inductively) by direct replacement. Worst, best, and average-case analysis, with linear search example. The "tyranny of asymptotics," using Jon Bentley's example of algorithms for the maximum contiguous subvector problem.
February 1 (Tue), 2005 Q4. Big Oh, Big Theta, Big Omega.
February 3 (Thu), 2005 Time complexity of iterative algorithms, with the examples on the transparencies. Sums. Time complexity of recursive algorithms, started. Simple recurrences. The master theorem (started).
February 8 (Tue), 2005 Q5. HW2 collected. HW3 assigned: Exercises 2.4.1, 2.4.2, 2.4.4, 2.5.2, 2.5.3, 2.5.4, 2.5.7, 2.5.9, due Tuesday, February 15. Midterm will be on Thursday, February 17. Discussion of quiz solution: complexity of bubblesort. Master Theorem, again. Fibonacci numbers: definition, rabbit families, homogeneous recurrence relations, the principle of superposition, recursive algorithm based on the definition and its complexity, data dependency graph and a linear time iterative algorithm, matrix identity and logarithmic time algorithm based on it.
February 10 (Thu), 2005 No quiz. More on Fibonacci: review and completion of logarithmic-time algorithm. Towers of Hanoi and problem reduction. Analysis of numbers of moves needed to solve the towers problem. Brute force approaches (Ch. 3; author's slides used): introduction, some examples up to polynomial evaluation (just started).
February 15 (Tue), 2005 HW3 collected. No quiz. Q&A on homework (partly in preparation for midterm). Brute force approach, concluded.
February 17 (Thu), 2005 MT1.
February 22 (Tue), 2005 MT1 returned and discussed. HW4 assigned: special homework to make up some points lost in MT1, due on Thursday, 2005-02-24. HW5 assigned: exercises 3.2.1, 3.2.4, 3.2.5, 3.2.6, 3.3.2, due March 1. Divide-and-conquer: introduction, master theorem for d-and-c recurrences, with an example of use.
February 25 (Thu), 2005 HW4 due date (with more precise instructions) is now Tuesday, March 1. Divide-and-conquer: review of intro, mergesort, quicksort.
March 1 (Tue), 2005 HW4 and HW5 returned. HW6 assigned, due first Tuesday after the break (2005-03-15): 4.1.5, 4.1.6, 4.2.1, 4.2.5, 4.3.2. Divide and conquer: average-case analysis of quicksort: recurrence, proof of upper bound c n ln n by induction (with c = 2). QuickHull.
March 3 (Thu), 2005 Review of exercise 3.3.2a. Dynamic programming: introduction, Fibonacci numbers, binomial coefficients. Data dependency patterns. Handwritten notes are on the web site, under "lecture notes."
March 15 (Tue), 2005 Linwei Niu (TA) does exercises 4.1.5, 4.1.6, 4.3.2, 4.4.2 in class. He explained the basic properties of trees and the different algorithms for tree traversal.
March 17 (Thu), 2005 Dynamic programming. Review of binomial coefficients. Warshall's algorithm to compute the transitive closure of a binary relation. Floyd's algorithm to compute the solution to the all-pair shortest path problem.
March 22 (Tue), 2005 HW7 assigned, due March 29: exercises 8.1.9, 8.3.10. Discussion of matrix chain multiplication problem. Optimal binary search trees. Knapsack problem.
March 24 (Thu), 2005 Heaps and heapsort. The priority queue ADT. Bottom-up and top-down construction of heaps. Making change: greedy approach for special choices of denominations, DP approach for the general case.
March 29 (Tue), 2005 HW8: exercise 6.4.4 due in one week (April 5, Tuesday). Greedy algorithms. Making change (review), Kruskal's algorithm for MSTs, Prim's algorithm for MSTs, Dijkstra's algorithm for single-source shortest paths.
March 31 (Thu), 2005 Huffman trees (Section 6.4), with proof of correctness of the algorithm, using the loop invariant: the forest kept by Huffman's algorithm is a fringing forest for some Huffman tree. Dijkstra's algorithm: AI-style presentation with handout, just begun. Good Q&A. Second midterm will be no earlier than one week from today.
April 5 (Tue), 2005 HW8 collected. Second midterm will be on Tuesday, April 12. Dijkstra's algorithm: review, proof of correctness using a loop invariant), weak optimality (counting number of node expansions, using an adversary-based argument for the lower bound), strong optimality (counting number of comparisons of keys, using a transformation from sorting for the lower bound), among (blind) unidirectional algorithms in the decision tree model.
April 7 (Thu), 2005 Second midterm will be on Tuesday, April 12. Several exercises done in class, as requested: 9.3.2 (Dijkstra's algorithm), 6.4.1, (heaps), 8.3.10 (factoring for matrix multiplication). Good Q&A, especially on Dijkstra's shortest path algorithm.
April 12 (Tue), 2005 Second midterm.
April 14 (Thu), 2005 Review of second midterm. Depth-first search on undirected graphs.
April 19 (Tue), 2005 MT2 returned. HW9 assigned: Exercise 5.2.1 due Thursday, April 21. Chapter 5 material: DFS (on directed graphs also, tree edges, back edges, forward edges, cross edges), BFS (with example), topological sorting (with example, description of source removal and DFS-based algorithms) Chapter 6 material: Presorting, with two examples: finding the median, and finding duplicates.
April 21 (Thu), 2005 HW9 collected. Gaussian elimination (from ch. 6). Backtracking and branch-and-bound (from ch. 11: material not to be tested). End of course.