9/22/05: Basic definitions:
algorithm, computational problem, problem solution. The analysis of
algorithms: correctness and complexity. Models of
computation. Example: multiplication of arbitrary
integers. Computation of the factorial of arbitrary integers.
9/27/05: The Analysis of algorithms: worst case, best case
and average case complexity. Analysis of LargeFactorial: loop
invariants. Multiplying arbitrary integers: an elementary
solution. Summation formulas: Gauss formula and geometric sums.
Textbook: cp 1, 2.1, 2.2. Do exercises at the end of Section
2.2.
9/29/05 Test.
10/4/05: Analysis of Algorithms: correctness and complexity
of SelectionSort.
Textbook: cp 2.3
10/6/05: Analysis of Algorithms: asymptotic
notation. Examples. MergeSort.
Textbook: cp 2.3 (all)
10/11/05: Recurrence Ralations. Master Method. Analysis of MergeSort.
Textbook: cp 2.4
10/13/05: MergeSort revisited. The Divide-And-Conquer
design technique. Example: a problem of Computational Geometry.
Textbook: cp 2.4, 5.2, 5.3
10/18/05: Midterm 1.
10/20/05: Review of the midterm examination. Backtracking
algorithms.
10/25/05: More on the asymptotic notation. Properties of
the limit of the ratio of two positive functions of the integers. Data
Structures: specification and implementation. Adt's. Use of Java
interfaces. Array and Linked List implementation of the Stack
Adt.
10/27/05: In-class exam.
11/1/05: The Adt Queue. Graphs. Bipartite graphs. BFS.
11/3/05: Graph colorings. Using BFS to determine whether a
graph is 2-colorable. The Subset-Sum Problem. A bactracking
solution. Computational Difficulty of the Subset-Sum problem. The
class NP.
11/8/05: NP-completeness. Statement of Cook's Theorem. The
PriorityQueue Adt. Heap-based implementation. Heapsort.
11/10/05: Analysis of makeheap. The Ordered Dictionary
Adt. Binary Search Trees implementation. Insertion and deletion in
BST's. Experimental analysis of the average height of a BST with
respect to a random permutation of keys.
11/15/05: Red-Black Trees. The Java classes TreeSet and
TreeMap. Implementing interface Comparable.
11/17/05: MT2.
11/22/05: Review of MT2. Definition of AVL
Trees. Worst-case AVL Trees: Fibonacci Trees.
11/29/05: B-trees. Insertion in
B-trees. Hashtables. Conflict resolution by chaining. Hashcodes and
Compression. The Java classes HashSet and HashMap: overriding methods
equals and hashCode. Hashing strings and evaluating polynomials: the
Horner method. The Union-Find data structure. Implementation with path
compression.
12/1/05: Greedy Programming. Shortest Paths in digraphs and
the Dijkstra Algorithm. (Indirect) Min-heap implementation. Minimal
Spanning Trees and the Kruskal algorithm. Union-Find
implementation. Dynamic Programming. Principle of suboptimality. The
matrix-chain multiplication problem. Memoization.