COMP309, EFFICIENT SEQUENTIAL ALGORITHMS, 2019--2020


Module information

The module is organised by Prof. Igor Potapov. Lectures take place during Semester 1.
  • Tuesday 13:00, Nicholson Building (NICH) Lecture Theatre NICH-LT
  • Tuesday 14:00, Nicholson Building (NICH) Lecture Theatre NICH-LT
  • Thursday 10:00, MATH 029/ Forsyth Lecture Theatre Mathematical Sciences Building
  • There will be 30 lectures and 6 tutorials/workshops.

    Lectures start on Thursday 26th of September 2019.

    Tutorials/workshops will take place during week 3 - week 9:

    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.

  • Assignment 1 (Due at 17:00 on Friday the 15th of November 2019).
  • Assignment 2 (Due at 17:00 on Monday the 9th of December 2019).
  • 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.