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.