| Times | TTh 11:00am - 12:15pm | ||
|---|---|---|---|
| Location | Gates B12 | ||
| Instructor | Amin Saberi (saberi at stanford dot edu) | Office Hours | Th 2-4, Terman 317 |
| Course Assistants | Adam
Guetz (guetz at stanford dot edu) |
TuW 2-4, Terman 399 | |
| Chen Gu (guc at stanford dot edu) | M 1-4, Terman 399 |
||
Recommended Texts
- Algorithm Design by Kleinberg and Tardos [KT]
- Discrete Mathematics by Lovasz, Pelikan and Vesztergombi [LPV] (available here for Stanford IPs)
- A Course in combinatorics by van Lint and Wilson [vLW]
Topics
- Basic concepts and definitions
- Cayley's theorem, Prufer codes
- Minimum Spanning Trees, Applications in phylogeny
- Introduction to algorithms
- Matching, flow, LP-duality
- Eulerian and Hamiltonian cycles, DNA sequencing
- NP-hardness
- Advanced techniques
- Randomization
- probabilistic methods, random graphs
- random walks on graphs, hitting and cover times
- matching via matrix inversion
- Approximation algorithms
- Algorithms and game theory
See the course syllabus.
