

Status: May 23, 2007

CS244: »Algorithm Design«
Term II (2006/2007)
7.5 CATS (3.75 ECTS)


There will be 2 revisions classes:
 May 16, 14:00  15:00 Physics Lecture Theatre
(slides)
 May 30, 11:00  12:00 MS01
Sample test (in pdf format) is available.
The exam will be DIFFERENT from that in the last years (at least because this module is taught
for the very first time) and so the exam will follow the format of the sample exam and the class test.
The final exam will take place on June 16, 14:00
Class hours: 
Monday  
13:00  14:00  
[MS01] 

Office hours: 
Monday  
14:10  16:00 
(during 2nd term only) 
Tuesday  
13:00  14:00   [ACCR] 

Friday  
9:00  10:00   [H051] 

Group seminars: 
Monday  
15:00  16:00  
[F111] 

Peter Krusche's office hours: 
Thursday  
15:00  16:00 

Thursday  
11:00  12:00  
[CS104] 

Friday  
13:00  14:00  
[S011] 
7.5 CATS (3.75 ECTS)
Availability:
Core  CS. Option  CSys, CMS CBS, Mathematics and Mathematics with Computing
Seminars are timetabled in weeks 6 to 10 of Term 2 and will be run by
Peter Krusche.
In week 6, the seminars will follow CS243 scenario, but starting from week 7,
there will be three seminar groups:
 Monday 15:0016:00 [F111],
 Thursday 11:0012:00 [CS104],
 Friday 13:0014:00 [S011].
Partition into groups has been done during Friday's lecture, on February 16.
Problem Sets:
 Algorithms are fundamental to programming and to understanding computation.
The purpose of this module is to provide students with a coherent knowledge
of techniques for designing algorithms, and with the tools for applying
these techniques to computational problems. Teaching and learning methods
include lectures and reading material which describe algorithmic techniques
and applications of these techniques to specific problems.
A problem sheet gives students an opportunity to practice problem solving.
 On completion of the module the student should be able to:
 Understand a variety of techniques for designing algorithms
 Understand a wide variety of data structures and should be able to use them appropriately to solve problems
 Understand some fundamental algorithms
Main topics covered include (all all these topics are subject to the final exam):
 Graph algorithms
 Network flow
 NP and computational intractability
 Approximation algorithms
 Randomized algorithms
Textbooks and references:

 90 min. examination (80%)
 Class test (20%)
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.

(13/02/2007)
 Discussion of the syllabus, requirements, topics to be covered, textbook.
 Introduction to directed graphs: DAGs, topological ordering.
 Slides (in pdf format, local access only).

(16/02/2007)
 Introduction to directed graphs: DAGs, topological ordering.
 A directed graph has topological ordering iff it's a DAG.
 Lineartime algorithm for finding topological ordering.
 Bipartite graphs and testing if a graph is bipartite.
 Slides (in pdf format, local access only).

(19/02/2007)
 Bipartite graphs and testing if a graph is bipartite.
 Connectivity in directed graphs and lineartime algorithm for stronglyconnected components.
 Maxflow: introduction, motivations, applications, and basic concepts.
 Slides (in pdf format, local access only).
 1st Problem Set has been posted (in pdf format, local access only).

(20/02/2007)
 Maxflow: introduction, motivations, applications, and basic concepts.
 Maxflow and mincut.
 Augmenting paths and FordFulkerson algorithm.
 Slides (in pdf format, local access only).

(23/02/2007)
 Maximum matching problem.
 Maxflow and mincut.
 Augmenting paths and FordFulkerson algorithm.
 Finding good augmenting paths.
 Slides (in pdf format, local access only).

(26/02/2007)
 Maxflow and its applications.
 Maximum matching problem.
 Perfect matchings, matchings in bipartite graphs, and their relation to maximumflows.
 Slides (in pdf format, local access only).

(27/02/2007)
 Matching in regular bipartite graphs.
 Edgedisjoint paths
 Edgedisjoint paths and network connectivity.
 Computational intractability and polynomialtime reductions.
 Slides (in pdf format, local access only).

2nd Problem Set has been posted (in pdf format, local access only).

(2/03/2007)
 Computational intractability and polynomialtime reductions.
 Hard problems, easy problem, and class NP.
 Slides (in pdf format, local access only).

(5/03/2007)
 Hard and easy problems.
 Classes P, NP, and EXP, and relations between them.
 Polynomialtime reductions.
 Class NP and NPcomplete.
 Proving NPcompleteness.
 Slides (in pdf format, local access only).

(6/03/2007)
 P, NP, and coNP.
 polynomialtime reductions.
 proving that a problem is NPcomplete.
 Slides (in pdf format, local access only).

Problem Set 3

(9/03/2007)
 Further proofs of NPcompleteness.
 What to do if the problem is NPcomplete or NPhard?
 Load balancing (scheduling problem)  Graham's algorithm and 2approximation.
 Slides (in pdf format, local access only)  slides cover material presented on this and the next lecture.

(12/03/2007)
 Approximation algorithms (won't be on the test  will be on the final exam).
 Load balancing and 2approximation algorithms, and 4/3approximation algorithm.
 PTAS for the knapsack problem.
 2approximation algorithm for vertex cover.
 Slides (in pdf format, local access only)  slides cover material presented on this and the next lecture.

(13/03/2007)

(16/03/2007)
 Randomized algorithms (was not on the test  will be on the final exam)
 Contention resolution.
 Linearity of expectation and card guessing.
 Randomized Quicksort.
 Slides (in pdf format, local access only).
 Final exam: material which students have to prepare  all what has been done in the lectures, including:
 Basic graph algorithms,
 maxflow and mincut,
 matching in graphs,
 P, NP, coNP, NPcompleteness (including proofs that a problem is NPcomplete),
 approximation algorithms, and
 randomized algorithms.


