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

OFFICE HOURS:  Office: SITE 5027 Wednesdays 10:1511:15, Thursdays 16:0017: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
0321295358. (Chapters 813) It will be available at: the University of Ottawa Bookstore . 

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

COURSE OBJECTIVES: 


COURSE OUTLINE:  Part I: Introduction to the theory of NPcompleteness 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. 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 and13, and some topics from other resources. Algorithms from the following topics will be covered:




MARKING SCHEME:  25% Midterm exam (M) 45% Final exam (F) 30% Assignments average (A) Final Grade (G): 



IMPORTANT DATES: 
First lecture: January 5 Study break: February 2024 Last date to drop: March 3 Last lecture: April 6 Final Exam Period: April 1130, 2006 