COMP309, EFFICIENT SEQUENTIAL ALGORITHMS, 2018--2019


Module information

The module is organised by Prof. Igor Potapov. Lectures take place during Semester 1.
  • Monday 14:00, Engineering Walker Lecture Theatre
  • Tuesday 12:00, Engineering Walker Lecture Theatre
  • Thursday 16:00, Engineering Walker Lecture Theatre
  • There will be 30 lectures and 6 tutorials/workshops.

    Lectures start on Thursday 27th of September 2018.

    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 Wednesday the 14th of November 2018).
  • 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.