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/410510/  
PROFESSOR:  Lucia Moura tel: 5625800 ext. 6678 email: lucia@site.uottawa.ca 

OFFICE HOURS:  Office: SITE 5027 Mondays 14:3015:30; Wednesdays 13:3014:30 

LECTURES:  Mon 13:0014:30 (room LMX 121) and Wed 11:3013:00 (room FTX235).  


TEXTBOOK:  Kleinberg and Tardos, Algorithm
Design, Addison Wesley, 2005. ISBN
0321295358. (Chapters 813) It is available at the University of Ottawa bookstore and at Agora bookstore (approximately $118) 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) 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): 



IMPORTANT DATES: 
First lecture: January 6 Study break: February 1420 Last date to drop: March 1 Last lecture: April 12 