CSI 4105 Winter 2006 course description

CALENDAR 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-06/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@site.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Wednesdays 10:15-11:15, Thursdays 16:00-17:00
LECTURES: Place: SMD 222
Tuesdays 16:00 - 17:30; Thursdays 14:30 - 16:00 
TEXTBOOK: Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2005. ISBN 0-321-29535-8. (Chapters 8-13)
It will be available at: the University of Ottawa Bookstore .
OTHER
REFERENCES:		 Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill, 2nd ed., 2001.  (Chapter 34 NP-completeness and Chapter 35 Approximation Algorithms; for 1st ed. 1990: Chapters 36 and 37) This was the previous textbook for this course.

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.
COURSE
OBJECTIVES:
  • 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: my lecture notes (5 lectures available from my web page) and Textbook Chapters 8 and 9.
    Introduction to the course. Problems, encodings, formal languages, computational models and algorithms. 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 and13, and some topics from other resources. Algorithms from the following topics will be covered:
    • Solving polinomially solvable special cases of hard problems.
    • Aproximation algorithms for NP-complete problems
    • Exhaustive algorithms (backtrancking, branch-and-bound): solving small instances of hard problems exactly.
    • Heuristic Searches/Local Searches
    • Randomized Algorithms
    MARKING SCHEME: 25% Midterm exam (M)
    45% Final exam (F)
    30% Assignments average (A)

    Final Grade (G):
    if (0.25*M + 0.45*F)/0.70 < 50% then G=(0.25*M + 0.45*F)/0.70 
    if (0.25*M + 0.45*F)/0.70>= 50% then G=0.25*M + 0.45*F + 0.30*A
    IMPORTANT
    DATES:

    		weight: due date:
    Assignment 1 10%  February 7 (Tuesday)
    Midterm Test 25%  February 16 (Thursday)
    Assignment 2 10%  March 7 (Tuesday)
    Assignment 3 10%  March 30 (Thursday)
    Dates from the Academic Calendar:
    First lecture: January 5 
    Study break: February 20-24
    Last date to drop: March 3
    Last lecture: April 6
    Final Exam Period: April 11-30, 2006