COMP30172: Advanced Algorithms (2008-2009)
This unit provides an advanced course in algorithms, assuming the student already knows simple algorithms for common computational tasks, and can reason about the correctness of algorithms and derive their complexity.
The course unit covers (1) a range of advanced algorithms in areas such as string searching and graph algorithms and their applications, (2) the notion of complexity classes for algorithmic tasks, completeness and hardness, and proofs by reduction, and (3) probabilistic techniques and algorithms.
The range of advanced algorithms will illustrate the complexity classes and also the structure, origins and correctness of algorithms.
On successful completion of this course unit you will:
Understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction. You will also have seen how to show tasks are NP-complete.
Be able to develop, and reason about the correctness and performance of algorithms, in particular for string searching and graph manipulation, and understand how graph algorithms arise in automated verification.
Have studied a range of probabilistic algorithms, understand the key issues involved, and be able to use probabilistic techniques in algorithms.
Assessment of Learning outcomesAll learning outcomes are assessed through examination, but the practical aspects in outcomes (1), (2) and (3) are developed in the practical exercises in advance of the examinations which will assess these practical aspects as well as the conceptual understanding.
Contribution to Programme Learning OutcomesA2, B1, B2, B3, C5.
Overview, organisation, background, issues.
String Searching Algorithms
Including preconditioning for Boyer-Moore and Knuth-Morris-Pratt type algorithms, and Harrison hashing and applications in web search engines.
Review of graphs, Graph Traversal, DFS algorithms, Path Finding. Other computational tasks on graphs,.
Automated Verification via finite and infinite word automata.
Polynomial Time and Space, NP Time and Space, Completeness and Hardness, SAT and Cook's Theorem, 2-SAT. Proofs of NP-Completeness for Computations on Graphs.
Randomised and Probabilistic Algorithms
Random number generators. Applications of randomisation: Sherwood, Las Vegas , Monte Carlo algorithms.
Summary, Revision and Exam
2 exercise sessions. 2 revision sessions