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

Topics

  1. Basic concepts and definitions
    • Cayley's theorem, Prufer codes
    • Minimum Spanning Trees, Applications in phylogeny
  2. Introduction to algorithms
    • Matching, flow, LP-duality
    • Eulerian and Hamiltonian cycles, DNA sequencing
    • NP-hardness
  3. 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
    Topics illustrated with EE, CS and Bioinformatics applications.

    See the course syllabus.

Course Requirements

The requirements for this course are three homeworks (one every two weeks approximately), an in-class midterm examination and a project.