General Information

Administration

Location and Hours

Please check the course schedule.

Staff

Instructor:
li.ca.uat|dohinar#doH inaR .rD
Assistants:
moc.liamg|kablis.daj#kabliS daJ
li.ca.uat.liam|ztivoknaylat#hcivoknaY laT

Feel free to coordinate reception hours via email.

Prerequisites

Data Structures (and by that also Linear Algebra, Extended Intro to CS, and Discrete Mathematics).

Grade and Homework Assignments

There will be 6 homework assignments. The average of the best 5 of 6 assignments will be worth 10 points of your final grade but assignment 6 cannot be the one left out.
The final exam will be worth 90 points. You must pass the exam to pass the course.

The submission of homework assignments is not compulsory; for each assignment you don't submit, you will get a 0.
Therefore, if you choose to submit no assignments at all, your final grade will be at most 90.
The worst grade among HW1-HW5 will not affect your HW grade, but HW6 is always taken.
Example: perfect HW2-HW6 yields all 10 HW points, but perfect HW1-HW5 only yields 8 HW points.

In any case, we strongly advise against not submitting, as our experience shows that students who don't try solving the assignments tend to do badly in the exam.

Text Books

Most of the course follows the following two books.

  • Introduction to Algorithms, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Third edition, MIT Press, 2009.
  • Algorithm Design, by J. Kleinberg and E. Tardos. Pearson/Addison Wesley, 2006.

Additional reading:

  • Graph Algorithms, by S. Even. Computer Science Press, 1979.
  • Data Structures and Network Algorithms, by R. E. Tarjan. SIAM, 1983.
  • The Design and Analysis of Algorithms, by D. Kozen, 1992.

Course Syllabus

Graph Algorithms: Breadth first search, Depth first search, Topological sort, Strongly connected components, Biconnected components, Minimum spanning trees (Kruskal, Prim), Shortest paths (Dijkstra, Bellman-Ford), All pairs shortest paths (Floyd-Warshall, Johnson), Dynamic programming, Linear programming, Flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic).

Some extra material

Links

Note that the definitions used in other courses and websites may differ from the definitions given in the course. Please keep this in mind when browsing outside of the course website.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License