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-02/ | |||||||||||||||||||||
PROFESSOR: | Lucia Moura
tel: 562-5800 ext. 6678 email: lucia@site.uottawa.ca |
|||||||||||||||||||||
OFFICE HOURS: | Office: SITE 5-027
Mondays 10:10-11:30; (another time to be decided) |
|||||||||||||||||||||
LECTURES: | Place: MRT 221
Mondays 8:30 - 10:00; Thursdays 10:00 - 11:30 |
|||||||||||||||||||||
POLICIES: | You are responsible for reading my policies on plagiarism, remarking,
late assignments and missed midterm, posted in the course web page.
Any mass communication with the class is going to be posted on the course web page under the heading of "News/Announcements" |
|||||||||||||||||||||
|
||||||||||||||||||||||
TEXTBOOKS: | Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill,
2nd ed., 2001.
The first 2/3 of the course will cover: Chapter 34 NP-completeness and Chapter 35 Approximation Algorithms (For 1st ed. 1990: Chapters 36 and 37) Buy this book! Very useful to have this book; other chapters lots of algorithms and data structures. Available at: the University of Ottawa Bookstore ($114.25). Neapolitan and Naimipour, Foundations of Algorithms, Heath, 1st
or 2nd ed., 1996 or 1997.
|
|||||||||||||||||||||
RECOMMENDED
REFERENCES: |
Sipser, Introduction to the theory of computation, PWS, 1997.
(Chapter 3 The Church-Turing Thesis, Chapter 4 Decidability, Chapter 5 Reducibility and Chapter 7 Time Complexity) You may have this book from CSI3104 Introduction to formal languages. Garey and Johnson, Computers and Intractability, Freeman, 1979.
|
|||||||||||||||||||||
COURSE
OBJECTIVES: |
|
|||||||||||||||||||||
COURSE OUTLINE: | Part I: Introduction and the theory of NP-completeness (around 11
lectures)
References: Lecture notes (lect 1-5) and Textbook CLR Ch. 34 (or for old edition: Ch. 36). 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. NP-completeness and reducibility. NP-completeness proofs. NP-completeness of various problems (clique, vertex-cover, subset-sum, hamiltonian cycle, the traveling salesman problem). Part II: Approximation Algorithms (around 4 lectures)
Part III: Exponential-time Techniques (around 7 lectures)
Other 3 Lectures: midterm review, midterm test and final exam review. |
|||||||||||||||||||||
|
||||||||||||||||||||||
MARKING SCHEME: | 25% Midterm exam (M)
45% Final exam (F) 30% Assignments average (A) Final Grade (G):
|
|||||||||||||||||||||
|
||||||||||||||||||||||
IMPORTANT
DATES: |
Schedule of assignments and midterm test:
We expect to return assignment and midterm test marks within one week of the due date. Dates from the Academic
Calendar:
|
|||||||||||||||||||||
|