15-451 Algorithms		12/12/00

* Summary of course topics
* Question/answer session
	Final is on Monday Dec 18, 8:30am-11:30am in PH100
=============================================================================

What the course has been about:
 1. techniques for developing algorithms (useful tools, useful boxes)
 2. techniques for analysis

To organize these, it can help to draw a "running-time line" and place
various topics according to where they would typically come up.

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

sublinear up to low-degree poly:
 - data structures: hashing, search trees, heaps, union find.

sublinear:
 - amortized analysis

linear:
 - depth-first search, breadth-first search
 - selection/median-finding

near-linear:
 - greedy algs with good data structures
   -  Prim, Kruskal, Djikstra

 - divide-and-conquer (also for low-degree poly)
 - sorting
 - FFT

low-degree & general poly(n):
 - dynamic programming
 - network flow, matching
 - linear programming
 - NP-completeness to tell when to look elsewhere

general:
 - randomization

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

In addition to the running time axis, we've also looked at a couple of
different performance metrics.

Performance metrics:
 - approximation ratio (e.g., find a vertex cover at most twice the
	size of the minimum one)
 - competitive ratio for online problems (e.g., for rent-or-buy, pay
	at most twice as much as could have paid in hindsight.)
 - static optimality (splay trees do nearly as well as best fixed tree
	in hindsight.  learning algorithm for 2-player zero-sum games does
	nearly as well as best fixed strategy in hindsight).

Different kinds of problems:
 - online problems
 - cryptographic protocols: RSA, ZK proofs.

Analysis techniques:
 - recurrences
 - potential functions / piggy-banks
 - linearity of expectation (allows to break apart complicated RVs into
	simple ones).
 - CRT, group properties for number-theory algs.

Another way to organize:  some topics are useful tools that are used
*inside* an algorithm.  E.g., splay trees, hashing, union-find.  Some
are useful because you can reduce a lot of 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.


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

Answer questions.  Also some sample problems:

Define TSP problem: Given weighted graph G, find a tour that visits
all the nodes and returns home with least total cost.  Factor of 2
approximation: find minimum spanning tree.  Then traverse twice.  Why
is this within a factor of 2?