15-451			12/11/01

* Review                                   - review session Sun 7pm
* Further directions                       - old final now on Bb
[FCEs in last 10 min]                      - Final Dec 19, 1-4pm, DH2315
					     Open book + 1 page notes
==========================================================================

Review
------
What the course has been about:
 1. techniques for developing algorithms
 2. techniques for analysis

Break down (1) into
 (a) fast subroutines: useful tools that go *inside* an algorithm.
     E.g., data structures like splay trees, hashing, union-find.  Things
     like sorting, DFS/BFS.

 (b) Harder problems that are important because you can reduce a lot
     of *other* problems to them: network flow, linear programming.

Notion of reduction is important in algorithms and in complexity
theory: 
 - solve a problem by reducing it to something you know how to do.
 - show a problem is hard by reducing a known hard problem to it.



Let's organize the algorithms we've discussed in class along a "running
time" line.

sublinear  ---  near-linear  ---  low-degree poly  ---  general poly(n) -->
O(1) O(log n)   O(n), O(nlogn)    O(n^2)

   --- hard but probably not NP-complete  ---  NP-complete  --- undecidable


sublinear:
 - data structures: hashing, balanced search trees, heaps, union find.

linear:
 - depth-first search, breadth-first search: SCC's etc.
 - selection/median-finding
 - string matching, DFAs (thinking of the DFA as an algorithm for
			 processing some input)
 - GCD

near-linear:
 - greedy algs with good data structures
   -  Prim, Kruskal, Dijkstra
 - divide-and-conquer algorithms
   - sorting, FFTs
 - DFA minimization

low-degree & general poly(n):
 - dynamic programming: Bellman-Ford, LCS, etc.
 - network flow, matchings, min-cost flow
 - min cuts
 - linear programming
 - Graph matrix algorithms
 - primality testing (we didn't really worry about exact running time)

Hard-but-not-NP-complete:
 - factoring

NP-complete:
 - 3-SAT, Vertex cover, TSP, etc.

Undecidable: 
 - halting problem

----------------------------------------------------------------

Algorithm tools and where they are typically used:
* Dynamic programming: typically for improving exponential time down to
	polynomial. 
* Reducing to LP, flows: ditto.
* Divide-and-conquer: typically for getting from O(n^2) to O(n log n).
        Sometimes just for reducing exponent (like Karatsuba or Strassen).
* Data structures: ditto
* Randomization: everywhere.
* Approximation algorithms: typically for NP-complete problems, but
        sometimes also makes sense for easier problems too.

Analysis tools:
* Amortized analysis, Potential functions, piggy banks:
    Typically for showing O(1) or O(log n) amortized cost per operation
* Reductions:  proving NP-complete or reducing to problem like LP, flows.
* Recurrences.  Esp with divide-and-conquer
* Linearity of expectation
* Group properties for number-theory algs.

=====================================

Further directions
------------------
Suppose I wanted to go further in algorithms (classes / research /
grad school)?  What are some of the directions I could go in?

Computational geometry [sometimes grad course in Fall, plus discussion
				       in 15-750]
  - e.g., point location, Voronoi diagrams
  - data structure issues, lots of analogies to quicksort, randomized
    search trees.
	      
Approximation Algorithms  [grad course in GSIA this Spring]
  - various alg techniques.  LP, SDP, lower-bounding optimal soln.
  - complexity theory

Online algorithms
  - competitive ratio
  - E.g., rent-or-buy problem, stairs-or-elevator
    (rent until you wish you had bought, etc.)
  - amortized analysis.  Lots of use of potential functions.

Cryptography [typically course in Fall]
  - ZK proofs
  - practical & theoretical issues.  Protocols.

Parallel Algorithms [sometimes course in Fall]

Computational Biology (and other sciences)
  - string-matching / tree-matching algorithms 
  - a lot of Dynamic Programming
  - geometrical (3-d structure) issues

Machine Learning [both theory and application-oriented courses]

Quantum Computing [grad course this Spring]
...