Status: May 29, 2007


CS301: »Complexity of Algorithms«

Term I (2006/2007)

15 CATS (7.5 ECTS)

NEW! There will be 2 revisions classes, with tentative dates/times:

  • May 16, 10:00 - 11:00, CS.104
  • May 30, 13:00 - 14:00, CS.101

The exam will be DIFFERENT from that in the last years and so the exam will follow the format of the sample exam provided below.

NEW! The final exam will take place on June 7, 9:30

Sample exam questions are available (in pdf format)!

NEW! Sample solutions to sample exam questions are available (in pdf format)! Only solutions to the problems not discussed in details in the class are presented.

These files are available only from the University of Warwick computer network. If you are away from campus you can access those files with the help of the ITS web proxy or using VNC for working remotely on DCS computers.
To prepare for the exam, answer these questions and work on similar/related problems.


Prof. Artur Czumaj

Office:   CS.313   E-Mail:  
Tel:   024 765 73796 WWW:
Fax:   024 765 23363


Class hours:    Monday  10:00 - 11:00  [Room CS 1.04]   Office hours:    Monday  14:00 - 16:00
Tuesday  14:00 - 15:00[Room CS 1.04]
Friday  12:00 - 13:00[Room CS 1.04]


15 CATS (7.5 ECTS)

Availability: Option - CS, CSys, CSE, and Mathematics

Prerequisites: CS203 and CS236 are recommended


Academic Aims:

  • To learn the notions of the complexity of algorithms and the complexity of computational problems
  • To learn various of models of computations
  • To understand what makes some computational problems harder than others
  • To understand how to deal with hard/intractable problems

Learning Outcomes:

  • Students will learn to analyse the intrinsic difficulty of various computational challenges, and how to specify useful variations that may be more tractable


The goal of this module is to understand the notion of complexity of algorithms and of computational problems. Students will learn how to design efficient algorithms, what makes an algorithm efficient, and what makes a problem hard (so that it has no fast algorithm). Various models of computations will be discussed, in particular, the models of classical deterministic computations, non-deterministic computations, and also of randomized computations, approximation algorithms, parallel computations, and on-line computations will be presented. Some part of the module will be also devoted to the discussions of what makes some computational problems harder than others, how to classify well-defined computational problems into levels of hardness, and how to deal with problems that are hard and intractable.

The module will begin with an introduction to "models of computation," including the model of Turing machines that can be used to specify computational algorithms. Then, we will address the applicability of these models of computations and we will discuss some general algorithmic techniques, and their applicability. Examples include the use of randomness, parallel algorithms, on-line algorithms, and approximation algorithms. Next, we will study the complexity of computational problems in a general setting - we will introduce the class of NP-complete problems, which includes many fundamental problems such as the Travelling Salesman Problem. The relationship between this and other classes of problems such as cryptographically hard problems, and PSPACE-hard problems (which include for example the problem of finding winning strategies in various board games) will be studied.

Textbooks and references:

There is no single textbook used in this module and almost all necessary material is (or will be made) available online.

A large part of the material discussed in the course is covered in the following three textbooks: Similar material as in the Papadimitriou's book is also available in two recent drafts (available online! but they cover MUCH more than what're doing here):


Three-hour examination.

2-3 sets of exercises (homework) will be given to students to master the material discussed in the class.

Specific contents:

The files containing lecture slides and exercises are available only from the University of Warwick computer network. If you are away from campus you can access those files with the help of the ITS web proxy. Using VNC for working remotely on DCS computers is another attractive alternative.

  1. (3/10/2006)

  2. (6/10/2006)

  3. (9/10/2006)
    • Lower bounds: what does it mean that a problem requires T(n) time
    • Examples: sorting requires W(n log n) comparisons
    • Slides of J. Edmonds (Lower Bounds & Models)

  4. (10/10/2006)
    • Sorting algorithms and Master Theorem for solving recurrences
    • Slides lecture 4 (and in unformatted pdf format)
    • Master theorem: a generic approach for solving basic recurrences
    • Material with an outline of the proof of the Master Theorem will be provided during the class on Friday (Oct 13).

  5. (13/10/2006)

  6. (16/10/2006)

  7. (17/10/2006)

  8. (20/10/2006)

  9. (23/10/2006)

  10. (24/10/2006)

  11. (27/10/2006)

  12. (30/10/2006)
    • Matrix computations
    • Slides lecture 12 (and in unformatted pdf format)
    • Homework (due Friday, November 10): Sorting strings in linear-time
      • Input: n strings A0, A1, ..., An-1 over alphabet {a, b, c, ...z}
      • Output: permutation B0, B1, ..., Bn-1 of the Ai's such that B0 ≤ B1 ≤ ... ≤ Bn-1
      • Goal: Design an algorithm running in time proportional to the input size, that is, in O(|A0| + |A1| + ... + |An-1|) time, where |Ai| is the length of string Ai

  13. (6/11/2006)     (no class on October 31 and November 3 - the classes will rescheduled)

  14. (7/11/2006)

  15. (10/11/2006)
    • Boolean matrix multiplications: the Four Russians algorithm

  16. (13/11/2006)

  17. (14/11/2006)
    • Discrete Fast Fourier Transform
    • Slides lecture 17 (and in unformatted pdf format)
    • Homework (due Monday, November 27): Verifying similarity of two trees
      • Two (rooted) trees T1 and T2 are similar if
        • either each of T1 and T2 has exactly one node,
        • or if the root of T1 has children c1, c2, ... ck and the root of T2 has children d1, d2, ..., dk such that there is a permutation P of k elements so that for every i, the subtree rooted at ci is similar to the subtree rooted at dP(i).
      • Design an algorithm that verifies of two trees T1 and T2 are similar, and which does it in time proportional to the size of the trees (size of a tree = number of its nodes).

  18. 11:00am (15/11/2006) [Rescheduled class from October 31]
    • Soft introduction into complexity classes P and NP

  19. (17/11/2006)

  20. (20/11/2006)

  21. (21/11/2006)

  22. (27/11/2006)

  23. (28/11/2006)

  24. (1/12/2006)
    • A formal proof that clique is NP-complete
    • Some other hard problems which are unknown to be in P and are unknown to be NP-hard
    • What to do if we have to coupe with a hard problem ...
    • Slides lecture 24 (and in unformatted pdf format)
    • Homework (due Friday, December 8): Proving NP-completeness
      • Give a formal proof showing that at least one of the following problems is NP-complete:
        • Hamiltonian cycle
        • Vertex cover
          • for a given integer k and a graph G = (V,E), does it exist a subset of vertices U of size k such that each edge in E is incident to a vertex in U
        • Subset-sum
          • Given an integer k and set S of integers; is it a subset U of S such that sum of the elements in U equals exactly k
        • Subgraph isomorphism
          • given two graphs G and H, does G contain a subgraph isomorphic to H
      • Try to solve it without using any textbook/Internet
      • If you don't know how to solve then read it in textbooks/Internet
      • If you know how to prove of these results, then try to prove more (or even all!)

  25. (4/12/2006)

  26. (5/12/2006)

  27. 11:00am (6/12/2006)

  28. (8/12/2006)
    • Last lecture
    • Knapsack: 0-1 version and fraction version
    • Polynomial-time algorithm for the fractional knapsack problem
    • Pseudo-polynomial-time algorithm for the 0-1 knapsack problem
    • Fully-polynomial-time approximation scheme (FPTAS) for the 0-1 knapsack problem
    • Final thoughts
    • Slides lecture 28 (and in unformatted pdf format)

Access to the web page from that module in 2005/2006.
Notice however that this year module is following a completely different syllabus.