Advanced Algorithms
Professor:
Paul Wollan
Office Hours:
Thursday 10:30 - 12:30
Viale Regina Elena 295,
Office number G26
Class Times:
Wednesday 17:00 - 18:30 - Aula G50, Regina Elena 295
Thursday 14:00 - 15:30 - Aula G50, Regina Elena 295
Announcements
- Class will not be held the week of February 24 - 28. The first class will be Wednesday, March 4.
- Classes will be held online until further notice. Online classes are held with a combination of gotomeeting and jamboard sessions during the regularly scheduled class times. Any students wishing to receive an invite to the online class should contact the professor directly via email.
Class summaries
- March 11 - Amortized analysis: aggregate analysis, the accounting method, the potential method. (pdf)
- March 12 - Dynamic tables and amortized analysis. (pdf)
- March 18 - Binary search trees. (pdf)
- March 19 - AVL Binary search trees. (pdf)
- March 25 - Fibonacci heaps: insert, find_min, merge, extract_min. (pdf)
- March 26 - Fibonacci heaps: decrease key, deletion, bounding the depth. (pdf)
- April 1 - Dijkstra's algorithm; Matchings in graphs, finding a maximum cardinality matching in a bipartite graph. (pdf)
- April 2 - Weighted matchings in complete bipartite graphs; the Hungarian method. (pdf)
- April 8 - Matchings in general graphs; Edmond's blossom algorithm. (pdf)
- April 15 - Edmond's blossom algorithm. (pdf)
- April 16 - Flows in graphs; Ford-Fulkerson. (pdf)
- April 22 - Flows in graphs; Edmonds-Karp. (pdf)
- April 23 - Properties of planar graphs. (pdf)
- April 29 - Finding an st-labeling of a graph. (pdf)
- April 30 - class cancelled.