CSI 4105 Winter 2012 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-12/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@site.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Mondays and Fridays 1:15PM-2:15PM
LECTURES: Wed 1:00-2:30 and Fri 11:30-1:00 (room Simard SMD 428).  
TEXTBOOK: Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2005. ISBN 0-321-29535-8. (Chapters 8-13)
The textbook is required!
OTHER
REFERENCES:		 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.
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: 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)
    20% Assignments average (A) = 3 assignments@6.67% each
    30% Project (P) = 3% project proposal (PP), 7% project talk (PT), 20% 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.20*A + 0.30* P
    IMPORTANT
    DATES:

    		weight: due date: (tentative)
    Assignment 1 6.7%  February 3 (Fri)
    Midterm Test 1 25%  February 17 (Fri)
    Project Proposal 3%  Feb 29 (Wed)
    Assignment 2 6.7%  March 9 (Fri)
    Midterm Test 2 25%  March 23 (Fri)
    Assignment 3 5%  March 30 (Fri)
    Project Talk 7%  April 10 (Tues) 10:00-14:30- room TBA
    Project Report 20%  April 24
    Dates from the Academic Calendar:
    First lecture: January 11 
    Study break: February 19-25
    Last date to drop: March 16
    Last lecture: April 6 (Friday)