August 20 (Thu), 1998 Introduction to the Course: Goals and Topics to Be Covered. Example: Minimum Spanning Trees, with Kruskal and Dijikstra-Prim Algorithms. Importance of Abstraction, the Graph ADT, Correctness, Complexity. Introduction to Algorithm Correctness. Example of factorial.
August 25 (Tue) Syllabus, grade policy, etc. handed out. Quiz 1 assigned. HW 1 assigned: Exercise 1 Ch. 1 due *this Thursday* (Aug 27). Correctness of Recursive Algorithms (1.2), including recursive binary search. Correctness of Iterative Algorithms (1.3): loop invariant (def. and basics), example of summing algorithm.
August 27 (Thu) HW 1 collected. HW 1 discussed in class. (This was exceptionally accepted only today.) HW 2 assigned: Exercise 2 Ch. 1 due next Tuesday (Sep 1). Review of the Induction Schema. Simple and Complete Induction. Informal arguments to justify the induction schema: cranking and smallest counterexample. Detailed explanation of the loop invariant for the summing algorithm.
September 1 (Tue) HW 2 collected. HW 3 assigned: Exercise 1.5 die Thursday. Loop invariants; correctness of iterative selection sort and of iterative binary search. Completion of Ch. 1.
September 3 (Thu) HW 3 collected HW 4 assigned: Exercises 1.6, 1.9, 1.10 due in one week; to be done in teams of two students. Correction of HW 2 (correctness of recursive binary search). In-class exercise 1 (recursive squaring program) done and discussed. Introduction to Analysis of Algorithms: Bentley's paper on maximal contiguous subvector started.
September 8 (Tue) Change in HW 4: HW 4 now consists of only Exercise 1.6 and is still due on Thursday, September 10. HW 5 consists of 1.9 and 1.10, which are due on Tuesday, September 15 Bentley's paper continued. Correctness part completed. Complexity part to be continued.
September 10 (Thu) HW 4 collected. HW 5, unchanged, is still due on Tuesday, September 15. Algorithm for term-by-term evaluation of polynomials discussed, including complexity analysis and correctness analysis. Horner's rule discussed; observation made that Horner's rule requires n multiplications, instead of 2n-1 multiplications, for a polynomial of degree n-1.
September 15 (Tue) HW 5 collected. No new homework assigned. Characteristic operations; problem size. Best, worst, and average-time complexity. Complexity of linear search and of Towers of Hanoi (recursive). Solution of the recurrence T(n) = 2T(n-1)+1, with T(0) = 0, by repeated substitution.
September 17 (Thu) HW 6 assigned: Exercises 2.1, 2.2, 2.3, 2.4 due Tuesday, September 22. These are _not_ team exercises. (Reminder: all homework is to be done individually except if explicitly stated otherwise!) Exam 1 will be on Thursday, September 24 and will be almost certainly closed book. Solution of the recurrence T(n) = 2T(n-1)+1, with T(0) = 0 by pattern recognition (guessing) and verification by substitution. Complexity of binary search. Complexity of loops. Complexity of bubblesort, where inner index bound(s) depend on a value set in the outer index.
September 22 (Tue) Correction of HW 6 Exercises: 2.1, 2.2, 2.3, 2.4. No new homework assigned.
September 24 (Thu) HW 7 assigned: Exercise 2.16 due Tuesday, September 29. Big-Oh notation. Chapter 2 concluded.
September 29 (Tue) Midterm.
October 1 (Thu) Correction of Midterm.
October 6 (Tue) HW 7 (Ex. 2.16) collected. HW 8 assigned: Exercises 2.17, 2.18, 2,19 due Thursday, October 15. Chapter 3, sections 3.1 and 3.2: ADTs and their correctness.
October 8 (Thu) Review of 3.1 and 3.2. Complexity Analysis of ADT Implementations: 3.3 (worst case), started 3.4 (Amortized). Assigned reading of whole ch.3.
October 13 (Tue) Fall Break
October 15 (Thu) HW 8 collected. Amortized Complexity completed. Rest of Chapter 4 assigned as readings. Ch 5 (Algorithm Design) started. Incremental Algorithms of the first and second kind, with examples (sorting).
October 20 (Tue) HW 9 assigned: Exercises 4.11 and 4.12, tentatively due on Tuesday, October 27. HW 10 assigned: Exercises 4.2 and 4.3, tentatively due on Thursday, October 29. Divide-and-Conquer: Mergesort (pp.215-218) and its analysis; general divide-and-conquer scheme (handout from Baase given) and recurrence.
October 22 (Thu) HW 9 and 10 confirmed, with same due dates. Review of Divide-and-Conquer. The AHU divide and conquer recurrence solution theorem, with full proof. Recall of definition of Fibonacci numbers.
October 27 (Tue) HW 9 (4.11 and 4.12) collected. HW 10 (4.2 and 4.3) due dates changed to Thursday, November 5. Fibonacci numbers: recurrences for number of additions and number of returns. Constructive induction proof that the Fibonacci numbers grow exponentially.
October 29 (Thu) Dynamic programming, including the example of Fibonacci numbers and the following examples from Brassard and Bratley: binomial coefficients, world series, and making change. Bellman's principle of optimality introduced.
November 3 (Tue) Election Day--No classes.
November 5 (Thu) HW 10 collected. More on dynamic programming: Bellman's principle of optimality, with examples. The knapsack problem: in class exercise and discussion.
November 10 (Tue) More on DP. Cheapest Paths in Staged Networks (notes from OR text by Brioschi). Cheapest paths of bounded length in graphs (even with negative costs): the Bellman-Kabala (also known as Bellman-Moore) algorithm (parts of Section 12.1 of text).
November 12 (Thu) Second midterm test.
November 17 (Tue) HW 11 assigned: Exercises 6.1 and 6.2, due on Thursday, November 19. Correction of second midterm. Trees (Ch.6): definitions; exercise 6.1 for binary trees.
November 19 (Thu) HW 11 collected. HW 12 assigned: Exercises 6.5, 6.9. 6.10 Section 6.3 (Mathematical Properties of Trees: All).
November 24 (Tue) HW 12 will be collected on Tuesday, December 1: Exercises 6.5, 6.9. 6.10 Huffman trees (6.4). Priority Queues and Heap-Ordered trees: 8.1 and 8.2.
November 26 (Thu) Thanksgiving. No classes.
Deacember 1 (Tue) HW 12 collected: Exercises 6.5, 6.9, 6.10. Heaps. Dijkstra's shortest path algorithm.
Deacember 3 (Thu) Dijkstra's shortest path algorithm, completed.