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

OFFICE HOURS:  Office: SITE 5027 Mondays and Fridays 1:15PM2:15PM 

LECTURES:  Wed 1:002:30 and Fri 11:301:00 (room Simard SMD 428).  


TEXTBOOK:  Kleinberg and Tardos, Algorithm
Design, Addison Wesley, 2005. ISBN
0321295358. (Chapters 813) 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) 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): 



IMPORTANT DATES: 
First lecture: January 11 Study break: February 1925 Last date to drop: March 16 Last lecture: April 6 (Friday) 