Status: May 23, 2007

 

CS244: »Algorithm Design«

Term II (2006/2007)

7.5 CATS (3.75 ECTS)
  

NEW! There will be 2 revisions classes:

  • May 16, 14:00 - 15:00 Physics Lecture Theatre (NEW!slides)
  • May 30, 11:00 - 12:00 MS01

NEW! 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.

NEW! The final exam will take place on June 16, 14:00

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  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]

Administration:

7.5 CATS (3.75 ECTS)

Availability: Core - CS. Option - CSys, CMS CBS, Mathematics and Mathematics with Computing

Group seminars:

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:00-16:00 [F111],
  • Thursday 11:00-12:00 [CS104],
  • Friday 13:00-14:00 [S011].

Partition into groups has been done during Friday's lecture, on February 16.

Problem Sets:

Content:

Academic Aims:

  • 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.

Learning Outcomes:

  • 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

Content:

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:

Assessment:

  • 90 min. examination (80%)
  • Class test (20%)

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. (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).

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

  3. (19/02/2007)
    • Bipartite graphs and testing if a graph is bipartite.
    • Connectivity in directed graphs and linear-time algorithm for strongly-connected components.
    • Max-flow: 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).

  4. (20/02/2007)
    • Max-flow: introduction, motivations, applications, and basic concepts.
    • Max-flow and min-cut.
    • Augmenting paths and Ford-Fulkerson algorithm.
    • Slides (in pdf format, local access only).

  5. (23/02/2007)
    • Maximum matching problem.
    • Max-flow and min-cut.
    • Augmenting paths and Ford-Fulkerson algorithm.
    • Finding good augmenting paths.
    • Slides (in pdf format, local access only).

  6. (26/02/2007)
    • Max-flow and its applications.
    • Maximum matching problem.
    • Perfect matchings, matchings in bipartite graphs, and their relation to maximum-flows.
    • Slides (in pdf format, local access only).

  7. (27/02/2007)
    • Matching in regular bipartite graphs.
    • Edge-disjoint paths
    • Edge-disjoint paths and network connectivity.
    • Computational intractability and polynomial-time reductions.
    • Slides (in pdf format, local access only).
    • 2nd Problem Set has been posted (in pdf format, local access only).

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

  9. (5/03/2007)
    • Hard and easy problems.
    • Classes P, NP, and EXP, and relations between them.
    • Polynomial-time reductions.
    • Class NP and NP-complete.
    • Proving NP-completeness.
    • Slides (in pdf format, local access only).

  10. (6/03/2007)
    • P, NP, and co-NP.
    • polynomial-time reductions.
    • proving that a problem is NP-complete.
    • Slides (in pdf format, local access only).
    • Problem Set 3

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

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

  13. (13/03/2007)

  14. (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,
      • max-flow and min-cut,
      • matching in graphs,
      • P, NP, co-NP, NP-completeness (including proofs that a problem is NP-complete),
      • approximation algorithms, and
      • randomized algorithms.