CSI 4105.  DESIGN AND ANALYSIS OF ALGORITHMS II (3 hs of lecture
per week,
3 credits). Theory of NPcompleteness, methods for dealing with NPcomplete 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/410514/  
PROFESSOR:  Lucia Moura tel: 5625800 ext. 6678 email: lucia@eecs.uottawa.ca 

OFFICE HOURS:  Office: SITE 5027 Tuesdays 9:30AM10:30AM Wednesdays 9:30AM10:30AM 

LECTURES: 
Lecture 1: Wednesday 1:002:30 FSS 10003 Lecture 2: Friday 11:301:00 STE C0136. 



TEXTBOOK:  Kleinberg and Tardos, Algorithm
Design, Addison Wesley, 2005. ISBN
0321295358. (Chapters 813) Textbook will be available at Agora bookstore. The textbook is required! 

OTHER REFERENCES: 
Cormen, Leiserson and Rivest, Introduction to Algorithms,
McGrawHill,
2nd ed., 2001.
(Chapter 34 NPcompleteness)
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. 

COURSE OBJECTIVES: 


COURSE OUTLINE:  Part I: Introduction to the theory of NPcompleteness 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. NPcompleteness and reducibility. NPcompleteness proofs. NPcompleteness of various problems. The complexity class PSPACE. Part II: Methods for dealing with NPcomplete problems References: Texbook Chapters 10,11,12 and 13, and backtracking from other resources. Algorithms from the following topics will be covered:




MARKING SCHEME:  25% Midterm Exam 1 (M1) 25% Midterm Exam 2 (M2) 25% Assignments average (A) = 3 assignments (submit via blackboard learn) 25% Project (P) = 2% project proposal (PP), 5% project talk (PT), 18% project report (PR) Final Grade (G): 



IMPORTANT DATES: 
First lecture: January 8 Study break: February 1921 Last lecture: April 4 (Friday) 