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