Advanced Algorithmic Techniques (COMP523)

First Semester, Masters Module
Department of Computer Science, University of Liverpool

Lecturer: Aris Filos-Ratsikas
Tutorials: Michail Theofilatos
Weekly Hours: 3h lectures + 1h tutorial (over 10 weeks).

Assessment: 75% Exam, 25% Continuous Assessment.
Continous Assessment: 2 Coursework Assignments, 12.5% each.

Announcements

• The first assignment has been posted, you can find it it the link below. The deadline is October 30 at 16.00. Below you may also find some useful information.
  – Assignment 1.
  – Relevant Information.

• The second assignment has been posted, you can find it it the link below. The deadline is December 2 at 17.00.
  – Assignment 2.

Schedule

Class Type	Day	Time	Room
Lecture	Wednesday	9:00-10:00	126MP-110
	Thursday	10:00-11:00	ELEC-201[E1]
	Thursday	12:00-13:00	SHER SR-1
Tutorial	Friday	14:00-15:00	MATH-103

Office hours: Thursday 11.15-12.15, or by e-mail appointment.
Location: Room 314, Ashton Building

Description of the module

This module introduces students to fundamental algorithmic primitives, as well as a range of algorithmic techniques. Specific topics include:

• Paradigms of algorithm design.
• Data structures used in the design of algorithms.
• Running time and memory complexity of algorithms, asymptotic analysis.
• Formal proofs of correctness and efficiency.
• Recursive algorithms.
• Graph algorithms.
• Network flows.
• Randomised Algorithms.
• Approximation algorithms and NP-completeness.
• Online algorithms and competitive analysis.

At the end of the module, the students are expected to be able to describe the design the principles related to algorithms in the aforementioned classes and to formally analyse and prove their time complexity and memory requirements. The students are expected to be able to identify which principles are appropriate for a wide range of problems and apply those principles to design algorithms for those problems.

For more information, see the official module specification here.

Recommended reading material

Module textbooks:

Algorithm Design by Jon Kleinberg and Eva Tardos. Pearson International Edition, 2006.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Third Edition, MIT Press, 2009.

Complementary reading:

Algorithm Design: Foundations, Analysis and Internet Examples by Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, Inc., 2002.

Distributed Computing: Fundamentals, Simulations and Advanced Topics by Hagit Attiya and Jennifer Welch, Second Edition, John Wiley & Sons, Inc., 2004.

Lectures

This section will be updated and populated as the semester progresses.

Lecture 1: Introduction to algorithms and basic complexity notions.
– Examples of algorithms.
– Examples of basic algorithmic techniques.
– Running time and memory use.
– Asymptotic notation and asymptotic complexity.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapters 2.1 - 2.4.

• Lecture Slides:
  – Introduction to the module.
  – Lecture 1.

• Lecture Video: Lecture 1 video.

Lecture 2: Recursion and Divide and Conquer techniques.
– Asymptotic notation and asymptotic complexity.
– Binary Search.
– Majority.

• Reading:
  – Kleinberg and Tardos - Algorithm Design, Chapters 2.2, 5.1., 5.2.
  – Cormen, Leiserson, Rivest and Stein - Introduction to Algorithms, Chapters 7.1, 7.2, 7.4.

• Lecture Slides: Lecture 2.

• Lecture video: Lecture 2 video.

Lecture 3: Recursion and Divide and Conquer techniques #2.
– Sorting in $O(n \log n)$ time with Mergesort.
– Quicksort.
– Lower bound for comparison-based sorting.

• Reading:
  – Kleinberg and Tardos - Algorithm Design, Chapter 5.1.
  – Cormen, Leiserson, Rivest and Stein - Introduction to Algorithms, Chapters 2.3.1, 2.3.2, 7.1, 7.2, 7.4, 8.1.

• Lecture Slides: Lecture 3.

• Lecture video: Lecture 3 video.

-Lecture 4: Recursion and Divide and Conquer techniques #3.
– Finding the closest pair of points.
– Integer multiplication.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapters 5.4, 5.5.

• Lecture Slides: Lecture 4.

• Lecture video: Lecture 4 video.

-Lecture 5: Recursion and Divide and Conquer techniques #4.
– The Selection Problem.

• Reading: Cormen, Leiserson, Rivest and Stein - Introduction to Algorithms, Introduction to Chapter 9, Chapter 9.3.

• Lecture Slides: Lecture 5.

• Lecture video: Lecture 5 video.

-Lecture 6: Graph Algorithms.
– Basic Graph Definitions.
– Depth First Search.
– Breadth First Search.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapters 3.1, 3.2 and 3.3.

• Lecture Slides: Lecture 6.

• Lecture Video: Lecture 6 video.

-Lecture 7: Graph Algorithms #2.
– Testing for bipartiteness.
– Testing for strong connectivity.
– Finding strongly connected components.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapters 3.4 and 3.5.

• Lecture Slides: Lecture 7.

• Lecture Video: Lecture 7 video.

-Lecture 8: Graph Algorithms #3.
– Directed Acyclic Graphs (DAGs).
– Topological Ordering.
– Finding strongly connected components (cont.).

• Reading: Kleinberg and Tardos - Algorithm Design, Chapters 3.6.

• Lecture Slides: Lecture 8.

• Lecture Video: Lecture 8 video.

-Lecture 9: Greedy Algorithms.
– Interval Scheduling.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 4.1.

• Lecture Slides: Lecture 9.

• Lecture Video: Lecture 9 video.

-Lecture 10: Greedy Algorithms #2.
– Minimum Spanning Tree.
– Kruskal’s Algorithm.
– Prim’s Algorithm.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 4.5.

• Lecture Slides: Lecture 10.

-Lecture 11: Greedy Algorithms #3.
– Prim’s Algorithm (continued).
– Clustering of maximum spacing.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 4.5, 4.7.

• Lecture Slides: Lecture 11.

-Lecture 12: Dynamic Programming.
– Weighted Interval Scheduling.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 6.1.

• Lecture Slides: Lecture 12.

-Lecture 13: Dynamic Programming #2.
– Subset Sum.
– Knapsack.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 6.4.

• Lecture Slides: Lecture 13.

-Lecture 14: Network Flows.
– Network Flow Definitions.
– Maximum Flow.
– The Ford-Fulkerson algorithm.
– Max-Flow - Min-Cut.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 7.1. and 7.2.

• Lecture Slides: Lecture 14.

-Lecture 15: Network Flows #2.
– The Max-Flow-Min-Cut theorem.
– Integer-valued flows and better augmenting paths.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 7.2 and 7.3.

• Lecture Slides: Lecture 15.

-Lecture 16: Network Flows #3.
– Modelling Max-Flow problems.
– Maximum Bipartite Matching.
– Baseball Elimination.
– Open Pit Mining.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 7.5 and 7.12.

• Lecture Slides: Lecture 16.

-Lecture 17: NP-completeness
– Polynomial-time reductions.
– The classes P and NP.
– NP-hardness and NP-completeness.
– 3SAT.
– Vertex Cover.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 8.1., 8.2., 8.3. and 8.4.

• Lecture Slides: Lecture 17.

-Lecture 18: NP-completeness #2
– Decision vs Optimisation.
– Subset Sum and Knapsack.
– A catalogue of NP-complete problems.
– A taxonomy of NP-complete problems.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 8.7., 8.8., 8.9. and 8.10.

• Lecture Slides: Lecture 18.

-Lecture 19: Linear Programming
– Linear Programs.
– Integer Linear Programs.
– Duality.
– Max-Flow and Min-Cut as linear programs.
– Total Unimodularity.

• Reading: Cormen, Leiserson, Rivest and Stein - Introduction to Algorithms, Chapters 29 (introduction, before 29.1), 29.2, 29.4

• Lecture Slides: Lecture 19.

-Lecture 20: Approximation Algorithms
– Approximaton Algorithm Techniques.
– The Greedy Method.
– Load Balancing on Identical Machines.
– Approximation Ratio.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 11.1.

• Lecture Slides: Lecture 20.

-Lecture 21: Approximation Algorithms #2
– The Pricing Method.
– Approximation Algorithm for Vertex Cover.
– Connection to LP-duality.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 11.4.

• Lecture Slides: Lecture 21.

-Lecture: Solutions and Discussion of Assignment 1
– Assignment 1.
– Assignment 1 solutions.

-Lecture 22: Approximation Algorithms #3
– Linear Programming Relaxation and Rounding.
– ILP rounding algorithm for Vertex Cover.
– Inapproximability of Vertex Cover.
– Vertex Cover on Bipartite Graphs.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 11.6.

• Lecture Slides: Lecture 22.

-Lecture 23: Approximation Algorithms #4
– Dynamic Programming on Rounded Inputs.
– An FPTAS for 0/1-Knapsack.
– PTAS vs FTPAS.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 11.8.

• Lecture Slides: Lecture 23.

-Lecture 24: Randomised Algorithms
– Probabilities background.
– Identifier Selection.
– The Birthday Problem.
– Waiting for the first success.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 13.12 and 13.5.

• Lecture Slides: Lecture 24.

-Lecture 25: Randomised Algorithms #2
– Randomised cuts in multigraphs.
– Success amplification.

• Reading: Kleinberg and Tardos - Algorithm Design, Chapter 13.2.

• Lecture Slides: Lecture 25.

-Lecture 26: Randomised Algorithms #3
– Types of Randomised Algorithms (Monte Carlo vs Las Vegas).
– Randomised Approximation Algorithms.
– MAX-SAT, MAX-3SAT, MAX-CUT.

• Reading: D. R. Williamson and D. B. Shmoys, Chapter 5.1. (find it here).

• Lecture Slides: Lecture 26.

-Lecture 27: Randomised Algorithms #4
– Derandomisation using the method of conditional expectations.
– MAX-SAT via Randomised Rounding.

• Reading:
  – Kleinberg and Tardos, Chapter 13.4.
  – D. R. Williamson and D. B. Shmoys, Chapter 5.2 and 5.4. (find it here).

• Lecture Slides: Lecture 27.

-Lecture 28: Online Algorithms
– Online algorithms and competitive ratio.
– Online load balancing.
– Paging.

• Reading: A. Fiat and J. Woeginger, Chapter 1 and 3. (find it here).

• Lecture Slides: Lecture 28.

-Lecture 29: Online Algorithms #2
– LRU and FIFO algorithms for paging.
– Randomised marking algorithms for paging.

• Reading: A. Fiat and J. Woeginger, Chapter 1 and 3. (find it here).

• Lecture Slides:
  – Lecture 29.
  – Lecture 30 (Module Recap).

-Lecture: Solutions and Discussion of Assignment 2
– Assignment 2.
– Assignment 2 solutions.

Tutorials

This section will be updated and populated as the semester progresses.

Tutorial 1: Running time, asymptotic complexity, Divide and Conquer.

• Exercises:
  - J. Kleinberg and E. Tardos. Chapter 2, Exercises 1, 2, 3, 6(a), 6(b).
  - Problems: Tutorial 1.
  - Solutions: Solutions Tutorial 1.

Tutorial 2: Divide and Conquer, Recursion, Running time

• Exercises:
  - Problems: Tutorial 2.
  - Solutions: Solutions Tutorial 2.

Tutorial 3: Graph Algorithms

• Exercises:
  - Problems: Tutorial 3.
  - Solutions: Solutions Tutorial 3.

Tutorial 4: Greedy Algorithms and Dynamic Programming

• Exercises:
  - Problems: Tutorial 4.
  - Solutions: Solutions Tutorial 4.

Tutorial 5: Network Flows

• Exercises:
  - J. Kleinberg and E. Tardos. Chapter 7, Exercises 1, 2, 3, 4 and 5.
  - Problems: Tutorial 5.
  - Solutions: Solutions Tutorial 5.

Tutorial 6: Network Flows and NP-completness

• Exercises:
  - Problems: Tutorial 6.
  - Solutions: Solutions Tutorial 6.

Tutorial 7: Linear Programming and Approximation Algorithms

• Exercises:
  - Problems: Tutorial 7.
  - Solutions: Solutions Tutorial 7.

Tutorial 8: Approximation Algorithms

• Exercises:
  - J. Kleinberg and E. Tardos. Chapter 11, Solved Exercise 1.
  - Problem: Prove that the solutions to the LP-relaxation of the Vertex Cover ILP are half-integral, meaning that they take values in $\{0,\frac{1}{2},1\}$.
  - Solutions: Solutions Tutorial 8.

Tutorial 9: Randomised Algorithms

• Exercises:
  - J. Kleinberg and E. Tardos, Exercises 1 and 7.
  - Solutions: Solutions Tutorial 9.

Tutorial 10: Recap Tutorial

• Exercises:
  - A recap of some key exercises from Tutorials 1-9.