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?