Introduction
This unit introduces students to the algorithmic theory and applications of discrete optimization. The main aims of this unit are: (i) learn how to model various practical problems as abstract optimization problems, (ii) learn the theory underlying efficient algorithms for solving these problems, (iii) learn how to use these tools in practice.
Specific topics include: Linear and integer programming, polyhedral theory, min-cost max-flow problems, approximation algorithms, fixed parameter tractability, local search and meta-heuristics.
Assumed Knowledge
This course assumes basic linear algebra, and a good knowledge of algorithm design and analysis techniques
Assessment
- Assignments — 20%
- Project — 30%
- Final Exam — 50%
Lecture time table
- Time: Wednesday 10:00am - noon
- Location: TBA
Other Resources
Please go to the E-Learning site to the full UoS outline, access assignments, quizzes, and your marks for this unit.
Schedule
| Date | Topic | Lecture notes | Scribbles | Problem set |
|---|