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

A "*" marks a topic already covered
A ">>>" marks ongoing 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.

* 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).

             References (from textbook) relevant to the lectures of Aug 25 and 27: 
                     Section 4.1 titled "The substitution method" page 63
                     Section 4.2 titled "The recursion-tree method" page 67
                     Section 9.2 titled "Selection in expected linear time" page 185
                     Section 9.3 titled "Selection in worst-case linear time" page 189
             [Note: You may need to read more material if you have forgotten the
             basics of algorithm design that you learned in the undergraduate
             algorithms course that is pre-requisite for this course.]

* Weighted version of the selection problem.
* Using selection to solve linear programming in linear time (lines in the plane)

             References relevant to the lecture of Sep 1 and 3:
                 For weighted median (similar to weighted selection):
                     http://www.archive.org/stream/lineartimealgori00blei#page/n3/mode/2up
                 For linear programming: 
                     http://www.ima.umn.edu/~dubois/projects/CompGeo/project/LP.html
                     http://theory.stanford.edu/~megiddo/pdf/lplin.pdf
                 For matrix chain multiplication: Section 15.2 of textbook

* Dynamic programming solution to matrix chain multiplication 
* problem (Section 15.2 of textbook)

* String editing (Problem 15-3 of textbook); point out that
* longest common subsequence (Section 15.4) is a special case.
* Linear space solution (not in textbook).
		For the lecture of Sept 7 on the linear space solution I recommend 
		using your lecture notes 

* Maximal elements in 2 dimensions as an example of plane-sweep
* Longest Increasing Subsequence (LIS) 
	Reference for LIS: the URL 
		http://en.wikipedia.org/wiki/Longest_increasing_subsequence	
	explains + gives references to other sources for this problem

* Algorithms for closest pair (Section 33.4) 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 (Section 33.2 on page 940 of textbook)
* Enumeration of all intersections

* Convex hull algo

* Output-sensitive algos for 2-dim maxima and convex hull 
	Reference:  http://hdl.handle.net/1813/6417 for convex hull

* Greedy algorithms: activity selection (Section 16.1), 
* Exercise 16.1-3, others 

* 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 (Section 32.4).  Applications of pattern matching.  

* FFT algorithm. Inverse FFT.  Proof of convolution theorem. 
* Applications of convolution (polynomial multiplication, pattern
* matching with mismatches).  
	Reference:  All from textbook except approximte pattern matching that
		is adapted from the following paper:
		Karl R. Abrahamson: Generalized String Matching. SIAM J. Comput. 16(6): 1039-1051 (1987)

* Review of depth-first search, connected components
* Strongly connected components (+ review of preorder/postorder numberings
of a tree)
* Topological sorting, 
* Bridges, biconnected components

* Review of breadth-first search
* Dijkstra's algo for single-source shortest paths
* All-pairs path problems 

>>>> Union-Find structure.  
>>>> Kruskal's algo for min spanning tree (MST)
>>>> Use of MST for shortest paths under Max metric
>>>> Application of MST to approximate Euclidean TSP

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

P, NP, NP-completeness, NP-hardness, polynomial-time reductions
NP-completeness of satisfiability, linear time algo for 2-satisfiability

As time allows:

Review of balanced tree data structures: 2-3 trees (search, insert, delete operations, concatenate, split).  
Range queries for d > 1.  Multisearch structures.

Relationship between path problems and matrix multiplication

Maximum matching 

Network flow, applications to disjoint-path problems