CMSC 27200/37000 Algorithms -- Winter 2005
Handouts

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