COMP526: Efficient Algorithms

course materials for Fall 2024

Welcome to the Fall 2024 iteration of COMP526: Efficient Algorithms! This site will serve as the authoritative source for course materials. Please see the COMP526 Course Syllabus for more specific information about course policies.

Quick links: Canvas . Campus Wire . Poll Everywhere

Coordinates

Lectures

Lectures will be held at the following times and locations:

  • Tuesdays, 11:00–13:00, Engineering Building, Hele-Shaw Lecture Theatre
  • Thursday, 15:00–17:00, Thompson Yates Building, Lecture Theatre, Room 104

Note that the first lecture will be held on Tuesday 01 October.

Tutorials

All tutorials are held in the Electrical Engineering Building, Lecture Room E5 (Room 204). The tutorials meet at the following times:

  • Section 01: Tuesday 15:00–16:00
  • Section 02: Tuesday 16:00–17:00
  • Section 03: Monday 9:00–10:00
  • Section 04: Monday 10:00–11:00

My Office

My office is located in George Holt, Room 2.16B. Note that my office are by appointment only.

Resources

Software and Administrative Tools

Textbooks

There is no single textbook for this course. Instead, I have drawn materials mostly from the following sources, available from the University of Liverpool library (either in print or electronically). The following two books cover much of the material covered in COMP526:

  • CLRS: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
  • SW: Algorithms by Sedgewick and Wayne.

CLRS is the probably the “modern standard” reference text on algorithms. SW is less expansive, but focuses more on the text processing algorithms that we will study in this module. (Is is also the more accessible of these two books.) Additionally, I have used the sections of the following texts in preparing materials for this module:

  • Gusfield: Algorithms on Strings, Trees, and Sequences by Gusfield.
  • KT: Algorithm Design by Kleinberg and Tardos.
  • MacKay: Information Theory, Inference, and Learning Algorithms by MacKay.
  • SMDD: Sequential and Parallel Algorithms and Data Structures by Sanders, Mehlhorn, Dietzfelbinger, and Dementiev.

Occasionally, I will also link to other resources. See the weekly schedule below for relevant readings for each lecture.

Lecture Materials

Week 01 (23 Sept - 27 Sept)
  • No Lectures or Tutorials This Week!!
Week 02 (30 Sept - 4 Oct)
  • Lecture 01 (03 Oct): Course Introduction and Administrative Details
  • No Tutorials This Week!!
  • Reading (before Week 03 tutorials):
Week 03 (07 Oct - 11 Oct)
Week 04 (14 Oct - 18 Oct)
Week 05 (21 Oct - 25 Oct)
Week 06 (28 Oct - 1 Nov)
Week 07 (4 Nov - 8 Nov)
  • Lecture 10 (5 Nov): String Matching
    • Lecture Slides
    • Relevant Readings:
      • KT Chapter 5, Divide and Conquer
      • SW Section 5.3, Substring Search (start)
  • Lecture 11 (7 Nov): String Matching
  • Week 07 Tutorials tutorial-05.pdf
Week 08 (11 Nov - 15 Nov)
  • Lecture 12 (12 Nov): String Matching
  • Lecture 13 (14 Nov): Data Compression
    • Lecture Slides
    • Relevant Readings:
      • SW Section 5.5 Data Compression
      • CLRS Section 16.3 Huffman Codes
  • Week 08 Tutorials tutorial-06.pdf
  • Programming Assignment 1 Due Wednesday, 13 November
  • Quiz 05: String Matching
  • Programming Assignment 2 Released
Week 09 (18 Nov - 22 Nov)
  • Lecture 14 (19 Nov): Data Compression
  • Lecture 15 (21 Nov): Error Correcting Codes
  • Week 09 Tutorials
  • Quiz 06: Data Compression
Week 10 (25 Nov - 29 Nov)
  • Lecture 16 (26 Nov): Parallel Computation
  • Lecture 17 (28 Nov): Text Indexing
  • Week 10 Tutorials
  • Programming Assignment 2 Due
Week 11 (2 Dec - 6 Dec)
  • Lecture 18 (3 Dec): Text Indexing
  • Lecture 19 (5 Dec): Streaming Algorithms (Bonus Topic)
  • Week 11 Tutorials
  • Quiz 07
Week 12 (9 Dec - 13 Dec)
  • Lecture 21 (10 Dec): Review
  • Lecture 22 (12 Dec): Review
  • Week 12 Tutorials

Assignments

Programming Assignments

  • Programming Assignment 1: Due 13 Nov by 11:49pm
  • Programming Assignment 2 (Released Week 07) Due 29 Nov

Quizzes

  • Quiz 01 (Week 03): Logic & Proof Techniques
  • Quiz 02 (Week 04): Big-O Notation
  • Quiz 03 (Week 05): Fundamental Data Structures
  • Quiz 04 (Week 06): Sorting, Divide-and-Conquer
  • Quiz 05 (Week 08): String Matching
  • Quiz 06 (Week 09): Data Compression
  • Quiz 07 (Week 11): Error Correction/Text Indexing