COMP309, EFFICIENT SEQUENTIAL ALGORITHMS, 2017--2018


Module information

The module is organised by Dr. Igor Potapov. Lectures take place during Semester 1.
The lectures will be given by Dr. Igor Potapov.
  • Tuesday 11:00, REN-LT8 , Rendall Building, Lecture Room LT8
  • Thursday 15:00, REN-LT8 , Rendall Building, Lecture Room LT8
  • Thursday 16:00, REN-LT8 , Rendall Building, Lecture Room LT8
  • There will be 30 lectures and 6 tutorials/workshops. Tutorials/workshops will take place diring week 3 - week 9:
  • Group 1, Tuesday 16.00, JSM(bdg. 232), Muspratt Building (JSM), SR7
  • Group 2, Friday 15.00, CEDAR, Cedar House (bdg 360), 512
  • Group 3, Tuesday 13.00, JSM(bdg. 232), Muspratt Building (JSM), SR7
  • Group 4, Friday 14.00, CEDAR, Cedar House (bdg 360), 512
  • 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.