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

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.

Divide and conquer (mergesorting as an example).

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

Linear time selection (randomized, then deterministic).

Weighted version of the selection problem.

Using selection to solve linear programming in linear time (lines in the plane)
	Reference: http://www-ma2.upc.es/~geoc/m-lalparp-83.pdf

Dynamic programming solution to matrix chain multiplication 
problem 

String editing ; longest common subsequence as special case
Linear space solution 

Maximal elements in 2 dimensions as an example of plane-sweep
Output-sensitive algo for 2-dim maxima 

Longest Increasing Subsequence (LIS) 
        Reference for LIS: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
        (explains + gives references to other sources for this problem)

Algorithms for closest pair (both divide and conquer solution and plane-sweep solution)

Maximal elements in 3 dimensions as an example of dimension-reduction

Intersection detection using plane sweep + data struct 
Enumeration of all intersections

Convex hull algo

Greedy algorithms: activity selection, scheduling

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

KMP pattern matching algorithm ; applications of pattern matching

Review of balanced tree data structures: 2-3 trees (search, insert, 
delete operations, concatenate, split).  

Range queries for d > 1.  Multisearch structures.

FFT algorithm. Inverse FFT.  Proof of convolution theorem. 
Applications of convolution (pattern matching with mismatches, 
polynomial multiplication).  

Review of depth-first search, breadth-first search, connected components

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

Topological sorting

Bridges, biconnected components

Review of Dijkstra's algo for single-source shortest paths

All-pairs path problems 
Efficient (sub-quadratic) storage of shortest paths information
for special classes of graphs (trees as an example)

Review of Kruskal's algo for min spanning tree (MST)  [ Given as part of hwk 6 ]
Union-Find structure.  

Use of MST for shortest paths under Max metric  [ Given as part of hwk 6 ]
Application of MST to approximate Euclidean TSP

Matching, network flow and its applications

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

Parallelism