CMSC 27200/37000 Algorithms -- Winter 2005

If you notice omissions/errors, please send email to the instructor.

Jan. 3
Asymptotic notation

Jan. 5
Binary search to find item in sorted array

Jan. 7
Dynamic programming : the knapsack problem

Jan. 10
Course information - revised
Divide and Conquer - the Karatsuba-Ofman algorithm
Evaluation of recurrent inequalities

Jan. 12
Graphs and Digraphs

Jan. 17
A dynamic programming solution : maximum all-ones square
A dynamic programming solution : maximum common substring
Solution to "12 coins" problem

Jan. 21
Linear time graph algorithms : digraph reversal, sorting adjacency lists, recognizing undirected graphs

Jan. 26
k-way merge in O(n log(k)) using a heap

Jan. 31
A dynamic programming solution : the "interval sum" problem

Feb. 2
Batcher's odd-even sorting network : n=8

Feb. 7
Lovász Lattice Reduction   (G only)

Feb. 9
AVL Trees

Feb. 11
Branch-and-bound: improved exponential time bounds
Maximum independent sets in graphs

Feb. 16
Pseudocodes for basic algorithms in Number theory:
The Euclidean algorithm and Repeated squaring

Mar. 4
Distance transforms

Return to course home page