Algorithms (Efficiency of Computation) - 0368.2160
This page will be modified during the course, and will outline
the classes
Grade:
10% Exercises
90% Final Exam
PAGE FOR THE EXAM:
Page for the Exam
Exercises:
Exercise 1
Exercise 2
Exercise 3
Exercise 4
Exercise 5
Exercise 6
Solutions:
Solutions 1
Solutions 2
Solutions 3
Solutions 4
Solutions 5
Solutions 6
Text books:
Introduction to Algorithms,
by T. Cormen, C. Leiserson and R. Rivest.
MIT Press, 1990 (CLR).
Most of the course follows the above book.
Graph Algorithms,
by S. Even.
Computer Science Press, 1979.
Data Structures and Network Algorithms
by R. E. Tarjan.
SIAM, 1983.
Course syllabus:
Greedy algorithms and Dynamic Programming.
Graph Algorithms: Breadth first search, Depth first search,
Topological sort, Strongly connected components, Biconnected
components, Minimum spanning trees (Kruskal, Prim),
Shortest path (Dijkstra, Bellman-Ford),
All-pairs shortest path (Floyd-Warshall, Johnson),
Flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinic).
String matching: KMP.
Introduction to Linear Programming.
Randomized and Approximation Algorithms
Notes
Here is a link to course notes written by the student Assaf Shtilman.
The notes are NOT offical, were NOT checked by me in any way and may
contain errors.
Link to Notes
Course outline
Session numbers referred to the CLR book (first edition). Newer editions
may have different chapter numbers.
-
Nov 1 :
Introduction
Dynamic Programming (16)
Ex. Nov 3
Greedy algorithms (17) Dynamic Programming (16)
-
Nov 8 :
Dynamic Programming (16)
Representations of graphs (23.1)
Breadth first search (23.2)
Ex. Nov 10
Euler cycle and path
-
Nov 15 :
Breadth first search (23.2)
Depth first search (23.3)
BFS and DFS for undirected graphs
Ex. Nov 17
BFS applications (23)
-
Nov 22 :
Topological sort and DAGS (23.4)
Strongly connected components (23.5)
Ex. Nov 24
Bridges and articulation points (23)
Strongly connected components (23)
-
Nov 29 :
Minimum spanning trees (Kruskal, Prim) (24)
Ex. Dec 1
Minimum spanning trees (24)
-
Dec 6 :
Shortest paths - general (25.1)
Shortest paths - Dijkstra (25.2)
Ex. Dec 8
DAG shortest paths (25) Dijkstra (25)
-
Dec 13 :
Shortest paths - Bellman-Ford (25.3)
All pairs shortest paths (26.1)
Ex. Dec 15
Bellman-Ford applications (26)
-
Dec 20 :
Floyd-Warshall (26.2)
Transitive closure (26.2)
Johnson algorithm (26.3)
Ex. Dec 22
All pairs shortest paths (26)
-
Dec 27 :
Max Flow (27.1)
Ford-Fulkerson (27.2)
Ex. Dec 29
Max Flow (27)
-
Jan 3 :
Ford-Fulkerson (27.2)
Edmonds-Karp (27.2)
Dinics (Even's book)
Ex. Jan 5
Bipartite matching (27) Hall's theorem
k-connectivity
-
Jan 10 :
0-1 flow and matching (27.3)
String matching (34)
Ex. Jan 12
Flow
-
Jan 17 :
String matching (34)
Intorduction to Linear Programming
Ex. Jan 19
String matching (34)
-
Jan 24 :
Intorduction to Linear Programming
Approximation algorithms - Vertex cover
Ex. Jan 26
Linear Programming
-
Jan 31 :
Randomized algorithms, Approximation algorithms
Ex. Feb 2
Randomized and Approximation Algorithms
Last updated January 29, 2006