Session: Semester 2, 2012
Coordinator: Julian Mestre

COMP2907: Algorithms and Complexity (Advanced)

Introduction

This unit provides an introduction to the design and analysis of algorithms. The main aims are (i) to learn how to develop algorithmic solutions to computational problem and (ii) to develop understanding of algorithm efficiency and the notion of computational hardness.

Assumed Knowledge

This course assumes basic knowledge of discrete math. In particular, students should be familiar with graphs, Big O notation, and induction.

Assessment

In addition, there is a final exam barrier of 40%.

Textbook

"Algorithm Design" by Tardos and Kleinberg, Addison Lecture.

Time table

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 Reference Slides Scribbles Python code Python output Tutorial
July 30 Algorithm analysis review 2-1,2,4,5 introduction
analysis
scribbles find_window interaction
plot
problem set 1
(Adv lecture) Stable matching 1.1 stable matching
August 6 Graph algorithms 3
notes
graphs scribbles bfs interaction problem set 2
(Adv lecture) DFS on directed graphs 3 directed graphs scribbles
August 13 Greedy algorithms 4.1,2,5,6 greedy scribbles problem set 3
(Adv lecture) Fibonacci heaps 3 fibonacci
August 20 Divide and conquer 5.1,2,5 dnc problem set 4
(Adv lecture) Fast Fourier Transform 5.6 fft
August 27 Dynamic programming 6.1,2,4 slides scribbles problem set 5
(Adv lecture) Bellman-Ford 6.8,10 slides scribbles
September 3 Dynamic programming 2 6.5,6 slides scribbles nim problem set 6
(Adv lecture) Optimal binary search trees scribbles
September 10 Network flows 7.1,2,5 slides scribbles problem set 7
(Adv lecture) Augmenting path rules 7.3 - scribbles
September 17 Network flows applications 7.6,7,9,11 slides scribbles problem set 8
(Advanced) Karger's algorithm 13.2 - scribbles
October 8 NP-completeness 8.1,2,3,4.6 slides scribbles problem set 9
(Adv lecture) PRIMES ni NP notes - scribbles
October 15 Weak NP-hardness, coNP 8.8-9 slides scribbles problem set 10
(Adv lecture) Polynomial time hierarchy - - scribbles
October 22 Coping with NP-hardness 10.1,2 11.3 12.1,2,4 slides scribbles problem set 11
(Adv lecture) Kernelization notes scribbles