

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.
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
 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
 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,
nondeterministic computations, and also of randomized computations, approximation algorithms,
parallel computations, and online 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 welldefined 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, online algorithms, and approximation
algorithms. Next, we will study the complexity of computational problems in a
general setting  we will introduce the class of NPcomplete 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 PSPACEhard 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«,
AddisonWesley, 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«,
AddisonWesley, 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):
Threehour examination.
23 sets of exercises (homework) will be given to students to master the material discussed in the class.
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)

(6/10/2006)

(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
 Material with an outline of the proof of the Master Theorem will be provided during the class on Friday (Oct 13).

(13/10/2006)

(16/10/2006)

(17/10/2006)

(20/10/2006)

(23/10/2006)

(24/10/2006)

(27/10/2006)

(30/10/2006)
 Matrix computations
 Slides lecture 12
(and in unformatted pdf format)
 Homework (due Friday, November 10): Sorting strings in lineartime
 Input: n strings A_{0}, A_{1}, ..., A_{n1} over alphabet {a, b, c, ...z}
 Output: permutation B_{0}, B_{1}, ..., B_{n1} of the A_{i}'s such that
B_{0} ≤ B_{1} ≤ ... ≤ B_{n1}
 Goal: Design an algorithm running in time proportional to the input size, that is,
in O(A_{0} + A_{1} + ... + A_{n1}) 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)

(7/11/2006)

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

(13/11/2006)

(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_{1} and T_{2} are
similar if
 either each of T_{1} and T_{2} has exactly one node,
 or if the root of T_{1} has children c_{1}, c_{2},
... c_{k} and the root of T_{2} has children
d_{1}, d_{2}, ..., 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_{1} and
T_{2} 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)

(20/11/2006)

(21/11/2006)

(27/11/2006)

(28/11/2006)

(1/12/2006)
 A formal proof that clique is NPcomplete
 Some other hard problems which are unknown to be in P and are unknown to be NPhard
 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 NPcompleteness
 Give a formal proof showing that at least one of the following problems is NPcomplete:
 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

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

(5/12/2006)

11:00am (6/12/2006)

(8/12/2006)
 Last lecture
 Knapsack: 01 version and fraction version
 Polynomialtime algorithm for the fractional knapsack problem
 Pseudopolynomialtime algorithm for the 01 knapsack problem
 Fullypolynomialtime approximation scheme (FPTAS) for the 01 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.


