Administration
Location and Hours
Please check the course schedule.
Staff
- Instructors:
- li.ca.uat.tsop|kmiah#nalpaK miaH .forP
- li.ca.uat|kciwz#kciwZ irU .forP
- Assistants:
- moc.liamg|kablis.daj#kabliS daJ
- li.ca.uat.liam|ztivoknaylat#hcivoknaY laT (Office hours: Thursday 15:30, with prior coordination.)
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 homework grade will be worth 10 points of your final grade. The homework-grade composition will be: 95% - best 5 exercises, 5% - worst exercise.
The final exam will be worth 90 points. You must pass the exam to pass the course.
We strongly advise against not submitting the homework, even if disregarding their 10 points worth in the final grade, 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
- A booklet of algorithms.
- The LP material that is not in the booklet.
- A beginners guide to dynamic programming.
- A short outline of Ford Fulkerson variants and proofs for the Max Capacity Augmentation variant
- How to find a basic feasible solution for running the Simplex algorithm
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.
- A free online algorithms class given by Tim Roughgarden of Stanford University.
- Technion's algorithms course.
- MIT's algorithms course.
- Some examples of dynamic programming (from MIT).
- Some old tests and unofficial solutions.
- Some tests and unofficial solutions (Shlomi Rubinstein's site).
- Why you should never say things like "let's look at all the cycles in G"