| Times | TTh 11:00am - 12:15pm | ||
|---|---|---|---|
| Location | Gates B12 | ||
| Instructor | Amin Saberi (saberi at stanford dot edu) | Office Hours | Thu 9-11am, Terman 317 |
| Course Assistants | Adam
Guetz (guetz at stanford dot edu) |
TBD | |
| Alex Shkolnik (ads2 at stanford dot edu) | Mon 5-6pm, Fri 2-3pm Terman 152 |
||
Required Texts
- Algorithm Design by Kleinberg and Tardos [KT]
Recommended Texts
- 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.
