CSI 4105 Winter 2010 course description

CSI 4105. DESIGN AND ANALYSIS OF ALGORITHMS II (3 hs of lecture per week, 3 credits).
Theory of NP-completeness, methods for dealing with NP-complete problems. Selected topics in such areas as combinatorial optimization, computational geometry, cryptography, parallel algorithms.
Prerequisite: CSI 3105

WEB PAGE: http://www.site.uottawa.ca/~lucia/courses/4105-10/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@site.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Mondays 14:30-15:30; Wednesdays 13:30-14:30
LECTURES: Mon 13:00-14:30 (room LMX 121) and Wed 11:30-13:00 (room FTX235).  

TEXTBOOK: Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2005. ISBN 0-321-29535-8. (Chapters 8-13)
It is available at the University of Ottawa bookstore and at Agora bookstore (approximately $118)
The textbook is required!
Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill, 2nd ed., 2001.  (Chapter 34 NP-completeness)

Kreher and Stinson, Combinatorial algorithms: generation, enumeration and search, CRC Press, 1998 (Chapter 3 Backtracking, Chapter 4: Heuristic searches).

Garey and Johnson, Computers and Intractability, Freeman, 1979.
(Chapters 1-3) This book may be out of print, but it is available at the library.

  • To understand the importance of a formal treatment of ``problems'' and ``algorithms'' in the design of algorithms for solving difficult problems and in computer science in general.
  • To learn what NP-complete problems are, to be able to recognize NP-complete problems, and to be able to formally prove that certain problems are NP-complete.
  • To learn techniques to deal with NP-complete problems, such as polynomial-time approximation algorithms and sophisticated exponential-time algorithms, and to be able to analyse these algorithms.
  • COURSE OUTLINE: Part I: Introduction to the theory of NP-completeness
    References: Textbook Chapters 8 and 9.
    Introduction to the course. Polynomial time reductions. Polynomial time and the complexity class P. Polynomial verification and the complexity class NP. NP-completeness and reducibility. NP-completeness proofs. NP-completeness of various problems. The complexity class PSPACE.

    Part II: Methods for dealing with NP-complete problems
    References: Texbook Chapters 10,11,12 and 13, and backtracking from other resources. Algorithms from the following topics will be covered:
    • Exhaustive algorithms (backtracking): solving small instances of hard problems exactly.
    • Solving polynomially-solvable special cases of hard problems.
    • Aproximation algorithms for NP-complete problems
    • Heuristic Searches/Local Searches
    • Randomized Algorithms

    MARKING SCHEME: 25% Midterm Exam 1 (M1)
    25% Midterm Exam 2 (M2)
    15% Assignments average (A) = 3 assignments@5% each
    35% Project (P) = 5% project proposal (PP), 5% project talk (PT), 25% project report (PR)

    Final Grade (G):
    if (M1+M2)/2 < 50% then G=(M1+M2)/2  
    if (M1+M2)/2>= 50% then G=0.25*M1 + 0.25*M2 + 0.15*A + 0.35* P


    weight: due date: (tentative)
    Assignment 1 5%  January 27 (Wed)
    Midterm Test 1 25%  February 6 (Saturday)
    Project Proposal 5%  March 1 (Monday)
    Assignment 2 5%  March 10 (Wednesday)
    Midterm Test 2 25%  March 20 (Saturday)
    Assignment 3 5%  March 31 (Wednesday)
    Project Talk 5%  April 12 (Monday)
    Project Report 25%  April 29
    Dates from the Academic Calendar:
    First lecture: January 6 
    Study break: February 14-20
    Last date to drop: March 1
    Last lecture: April 12