List of topics to be covered in class (as time allows)

A ">>>>>>>" marks topic to be continued (or started) next lecture

Framework for analysis of algorithms, rate of growth of functions
("big oh" notation, etc), review of proofs by induction, summations,
recurrences and how to solve them.  Worst-case vs average case
analysis.

Divide and conquer paradigm (mergesorting as an example).

An important general recurrence (of which the recurrence 
for mergesort is a special case).

Linear time selection (randomized, then deterministic).
Application of selection to majority.

Dynamic programming paradigm: 
Solution to matrix chain multiplication problem (Section 15.2)
Finding largest square block of 1's in a Boolean matrix

String editing (Problem 15-3 of textbook); point out that
longest common subsequence (Section 15.4) is a special case.
	[ Brief sketch (not thorough coverage) of linear space 
	solution (not in textbook). ]

Greedy algorithms: 
Activity selection (Section 16.1), Exercise 16.1-3

Plane sweep paradigm:  
Maximal points in two dimensions (points not
dominated by any other point from the input set)
Longest Increasing Subsequence 

Extended Euclid algo 

Proximity problems:
Algorithms for closest pair (Section 33.4).

Lower bounds: 
Information-theoretic
Adversary-based
Examples:  For searching, sorting, min, min and max, 
element uniqueness, proofs by reduction (convex hull, closest pair).

Graph algorithms:
Depth-first search, breadth-first search,
connected components, topological sorting 
Bridges, biconnected components

Strongly connected components (+review of preorder/postorder numberings of a tree)

Kruskal's algo for min spanning tree (MST)
Application of MST to approximate Euclidean TSP

Dijkstra's algo for single-source shortest paths

All-pairs path problems (dynamic prog solution)

Balanced tree data structures: 2-3 trees (search, insert, delete,
	split, concatenate)
Range queries for d > 1.  
Multisearch structures.
Union-find.  
Application of data structures: Intersection problems

KMP pattern matching algorithm (Section 32.4).  

Basic number-theoretic algorithms 

Maximum matching, network flow
	(just problem def and time complexity)

Applications of network flow to disjoint-path problems

P, NP, NP-completeness, NP-hardness, polynomial-time reductions.

Approximation algorithms

Intro to parallelism