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

OFFICE HOURS:  Office: MCD 314
Mondays 10:1011:30; Thursdays 11:4012:40; Thursdays 3:304:30 

LECTURES:  Place: Sports Complex Room: E217 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. Available at: the University of Ottawa Bookstore ($110.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. Kreher and Stinson, Combinatorial Algorithms, CRC Press, 1998. Garey and Johnson, Computers and Intractability, Freeman, 1979. 

COURSE OBJECTIVES: 


COURSE OUTLINE: 
Part I: Introduction and the theory of NPcompleteness (around 11 lectures) 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 withing one week of the due date.
Dates from the Academic Calendar: 

