|CSI 4105.||DESIGN AND ANALYSIS OF ALGORITHMS II (3 hs of lecture
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
tel: 562-5800 ext. 6678
|OFFICE HOURS:||Office: SITE 5-027
Mondays 14:30-15:30; Wednesdays 13:30-14:30
|LECTURES:||Mon 13:00-14:30 (room LMX 121) and Wed 11:30-13:00 (room FTX235).|
|TEXTBOOK:||Kleinberg and Tardos, Algorithm
Design, Addison Wesley, 2005. ISBN
0-321-29535-8. (Chapters 8-13)
It is available at the University of Ottawa bookstore and at Agora bookstore (approximately $118)
The textbook is required!
|Cormen, Leiserson and Rivest, Introduction to Algorithms,
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,
|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:
|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):
First lecture: January 6
Study break: February 14-20
Last date to drop: March 1
Last lecture: April 12