Status: May 29, 2007

CS301: »Complexity of Algorithms«

Term I (2006/2007)

15 CATS (7.5 ECTS)

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.

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

Sample exam questions are available (in pdf format)!

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.

Instructor:

Prof. Artur Czumaj

Office:	CS.313	E-Mail:
Tel:	024 765 73796	WWW:	http://www.dcs.warwick.ac.uk/~czumaj/
Fax:	024 765 23363

Schedule:

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]

Administration:

15 CATS (7.5 ECTS)

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

Prerequisites: CS203 and CS236 are recommended

Contents:

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

Content:

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:

C.H. Papadimitriou: »Computational Complexity«, Addison-Wesley, 1994.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C.Stein: »Introduction to Algorithms«, The MIT Press, 2nd edition, 2001.
J. Kleinberg and E. Tardos: »Algorithm Design«, Addison-Wesley, 2005.

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):

S. Arora and B. Barak: »Computational Complexity: A Modern Approach«, (Part I is of our main interest)
O. Goldreich: »Computational Complexity: A Conceptual Perspective«

Assessment:

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.

(3/10/2006)
- Discussion of the syllabus, requirements, topics to be covered, textbooks.
- Slides lecture 1 (and in unformatted pdf format)
(6/10/2006)
- Efficient algorithms, and measure of quality of algorithms (worst-case and average-case)
- Sorting in linear-time: Counting-sort and Radix-sort
- Slides lecture 2 (and in unformatted pdf format)
(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)
(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
  - Solves many recurrences in the generic form T(n) = a T(n/b) + f(n)
  - See also description/discussion in Wikipedia
- Material with an outline of the proof of the Master Theorem will be provided during the class on Friday (Oct 13).
(13/10/2006)
- Quick Sort and its running-time analysis
- Strings and string (pattern) matching algorithms
- Slides lecture 5 (and in unformatted pdf format)
(16/10/2006)
- Strings and Boyer-Moore algorithm for string (pattern) matching
- Slides lecture 6 (and in unformatted pdf format)
- Some additional information about string matching (in postscript)
(17/10/2006)
- Knuth-Morris-Pratt algorithm for string (pattern) matching
- Slides lecture 7 (and in unformatted pdf format)
- Some additional information about string matching (in postscript)
- Animations in Java: exact string matching algorithms (try it if you like to play)
(20/10/2006)
- Knuth-Morris-Pratt string (pattern) matching algorithm
- Longest Common Subsequence algorithm (O(nm)-time algorithm); see Wikipedia link
- Slides lecture 8 (and in unformatted pdf format)
- Some additional information about string matching (in postscript)
- Animations in Java: exact string matching algorithms (try it if you like to play)
(23/10/2006)
- Edit distance between strings (O(nm)-time algorithm); see Wikipedia link
- Text compression, prefix codes, and Huffman coding
- Slides lecture 9 (and in unformatted pdf format)
(24/10/2006)
- Text compression, prefix codes, and Huffman coding
- Variable-length codes and Ziv-Lempel compression (see in Wikipedia for more information)
- Slides lecture 10 (and in unformatted pdf format)
- Some additional information about compression algorithms (in postscript)
(27/10/2006)
- Variable-length codes and Ziv-Lempel compression (see in Wikipedia for more information)
- Multiplication of two numbers
- Matrix computations (introduction)
- Slides lecture 11 (and in unformatted pdf format)
- Some additional information about compression algorithms (in postscript)
(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 A₀, A₁, ..., A_n-1 over alphabet {a, b, c, ...z}
  - Output: permutation B₀, B₁, ..., B_n-1 of the A_i's such that B₀ ≤ B₁ ≤ ... ≤ B_n-1
  - Goal: Design an algorithm running in time proportional to the input size, that is, in O(|A₀| + |A₁| + ... + |A_n-1|) time, where |A_i| is the length of string A_i
(6/11/2006)
(no class on October 31 and November 3 - the classes will rescheduled)
- Matrix multiplications and graph algorithms (shortest path problem)
- Boolean matrix multiplications
- Slides lecture 13 (and in unformatted pdf format)
(7/11/2006)
- Boolean matrix multiplications
- Transitive closure and Boolean matrix multiplications
- Further notes on fast matrix multiplications
- Slides lecture 14 (and in unformatted pdf format)
(10/11/2006)
- Boolean matrix multiplications: the Four Russians algorithm
(13/11/2006)
- Discrete Fast Fourier Transform
- Slides lecture 16 (and in unformatted pdf format)
(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 T₁ and T₂ are similar if
    - either each of T₁ and T₂ has exactly one node,
    - or if the root of T₁ has children c₁, c₂, ... c_k and the root of T₂ has children d₁, d₂, ..., d_k such that there is a permutation P of k elements so that for every i, the subtree rooted at c_i is similar to the subtree rooted at d_P(i).
  - Design an algorithm that verifies of two trees T₁ and T₂ are similar, and which does it in time proportional to the size of the trees (size of a tree = number of its nodes).
11:00am (15/11/2006) [Rescheduled class from October 31]
- Soft introduction into complexity classes P and NP
(17/11/2006)
- Introduction to Complexity Classes: P, PSPACE, EXP, NP
- Slides lecture 19 (and in unformatted pdf format)
(20/11/2006)
- Introduction to Complexity Classes: P, PSPACE, EXP, NP, Co-NP
- P vs. NP question: central problem in Computer Science (see discussion in http://www.win.tue.nl/~gwoegi/P-versus-NP.htm and http://scottaaronson.com/blog/?p=122)
- Slides lecture 20 (and in unformatted pdf format)
(21/11/2006)
- NP-completeness
- 2-SAT is not NP-complete (is in P)
- Slides lecture 21 (and in unformatted pdf format)
(27/11/2006)
- Polynomial-time algorithm for 2-SAT
- Slides lecture 22 (and in unformatted pdf format)
(28/11/2006)
- NP-completeness
- 3-SAT is NP-complete
- Other NP-complete problems and problems which might be between P and NP
- Slides lecture 23 (and in unformatted pdf format)
(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!)
(4/12/2006)
- Coping with hard (and NP-hard) problems
- Approximation algorithms
- 4/3-approximation for coloring planar graphs
- Slides lecture 25 (and in unformatted pdf format)
(5/12/2006)
- 2-approximation for minimum vertex cover
- Hardness of approximating TSP
- Slides lecture 26 (and in unformatted pdf format)
11:00am (6/12/2006)
- Re-scheduled lecture from November 24
- 2-approximation algorithm for metric TSP
- 1.5-approximation algorithm for metric TSP (Christofides algorithm)
- See also TSP web page from Concordia - how to deal with real problem instances of TSP
- Knapsack problem
- Slides lecture 27 (and in unformatted pdf format)
(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.