COMP309, EFFICIENT SEQUENTIAL ALGORITHMS, 2020--2021

Module information

The module is organised by Prof. Igor Potapov. Lectures take place during Semester 1.

TBA

Topics Covered

Module Introduction Slides(4up) Slides(1up)

Part 1. Algorithmic Paradigms Slides(4up) Slides(1up)

Part 2. Pattern Matching Slides(4up) Slides(1up)

Part 3. String Algorithms Slides(4up) Slides(1up)
Lempel-Ziv Welch (LZW) Compression Slides(4up) Slides(1up)

Part 4. NP-Completeness Slides(4up) Slides(1up)

Part 5. Approximation Algorithms and Complexity Slides(4up) Slides(1up)
3CP NP-completeness (extra slides)

Part 6. Sequential vs. parallel algorithms
Slides in pptx

Coursework

The coursework consists of two assignments, each of which is worth 10%.

Information about Coursework: The purpose of the coursework is to give you experience using the algorithmic ideas
that you are learning to solve computational problems. Thus, the main criterion used in allocating marks is correctness.

Main Textbooks

T. H. Cormen, C. E. Leiserson, R. L. Rivest Introduction to Algorithms, Second Edition. MIT Press (2001).

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation Springer 2003.

Other Recommended Books

A.V. Aho, Algorithms for finding patterns in Strings, Handbook of Theoretical Computer Science, Edited by J van Leeuwen, Elsevier (1990), 255-300.

C. Papadimitriou Computational Complexity Addison-Wesley 1993.