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

OFFICE HOURS:  Office: SITE 5027
Mondays 10:1011: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, McGrawHill,
2nd ed., 2001.
The first 2/3 of the course will cover: Chapter 34 NPcompleteness 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 ChurchTuring 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 NPcompleteness (around 11
lectures)
References: Lecture notes (lect 15) 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. NPcompleteness and reducibility. NPcompleteness proofs. NPcompleteness of various problems (clique, vertexcover, subsetsum, hamiltonian cycle, the traveling salesman problem). Part II: Approximation Algorithms (around 4 lectures)
Part III: Exponentialtime 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:


