CSI 4105. | DESIGN AND ANALYSIS OF ALGORITHMS II (3 hs of lecture
per week,
3 credits). 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 |
WEB PAGE: | http://www.site.uottawa.ca/~lucia/courses/4105-10/ | ||||||||||||||||||||||||||||
PROFESSOR: | Lucia Moura tel: 562-5800 ext. 6678 email: lucia@site.uottawa.ca |
||||||||||||||||||||||||||||
OFFICE HOURS: | Office: SITE 5-027 Wednesdays 2:30-3:30 (another TBA - Tuesday?) |
||||||||||||||||||||||||||||
LECTURES: | Tues 10:00-11:30 (room LMX223) and Wed 1:00-2:30 (room STE1010). | ||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||
TEXTBOOK: | Kleinberg and Tardos, Algorithm
Design, Addison Wesley, 2005. ISBN
0-321-29535-8. (Chapters 8-13) The textbook is required! |
||||||||||||||||||||||||||||
OTHER REFERENCES: |
Cormen, Leiserson and Rivest, Introduction to Algorithms,
McGraw-Hill,
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,
Freeman, 1979. |
||||||||||||||||||||||||||||
COURSE OBJECTIVES: |
|
||||||||||||||||||||||||||||
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): |
||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||
IMPORTANT DATES: |
First lecture: January 5 Study break: February 20-26 Last date to drop: March 4 Last lecture: April 8 |