Session: Semester 1, 2011
Coordinator: Julian Mestre

INFO5010A: Real-world algorithms


Oftentimes algorithmic theory is wrongfully deemed to be irrelevant to practitioners who are thought to resort only to simple ad-hoc heuristics when dealing with their computational problems. The objective of this class is to counter this notion by exposing students to sophisticated algorithmic techniques that are used in the real world, as well as more realistic models of computation that have been developed in recent years.

Assumed Knowledge

This course assumes basic knowledge in algorithm analysis, linear algebra, and probability.



Date Topic Further reading
Mar 3 Introduction to Linear Programming: Simplex and Duality [1, Ch 1 & 2]
Ma 10 Deriving the Simplex algorithm [1, Ch 3 & 4]
Mar 17 Introduction to Integer Programming: Integral LPs [2, Ch 3]
Mar 24 IP techniques: Branch and Bound, and Cutting Plane [2, Ch 7]
Mar 31 Approximation algorithms for covering problems [3, Ch 2 & 13]
Apr 7 Local search algorithms [4, Ch 12]
Apr 14 Cryptography: RSA algorithm [5, Ch 1]
Apr 21 Project Milestone 1
May 5 Pagerank algorithm (Taso Viglas invited lecture)
May 12 External memory algorithm: Persistent B-trees [6, Ch 1,2,4]
May 19 Cache-oblivious algorithms [7,8]
May 26 Steaming algorithms: Sampling [9]
June 2 Steaming algorithms: Majority and Median [9]