CSI 4105 FALL 2002 course description

CALENDAR DESCRIPTION:
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.
The last 1/3 of the course will cover: Chapter 5 Backtracking and Chapter 6 Branch-and-bound.
You may have this book from CSI3105; contact me otherwise.
 
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.
(Chapters 1-3) This book may be out of print, but it is available at the library.
COURSE
OBJECTIVES:
  • To understand the importance of a formal treatment of ``problems'' and ``algorithms'' in the design of algorithms for solving difficult problems and in computer science in general.
  • To learn what NP-complete problems are, to be able to recognize NP-complete problems, and to be able to formally prove that certain problems are NP-complete.
  • To learn techniques to deal with NP-complete problems, such as polynomial-time approximation algorithms and sophisticated exponential-time algorithms, and to be able to analyse these algorithms.
    		•
    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)
    Textbook CLR Ch. 35 (or for old edition: Ch. 37)
    Approximation algorithms and their performance bounds. Approximation algorithms for the vertex cover problem, the traveling salesman problem with cost satisfying the triangle inequality and the set-covering problem. Unlikeliness of epsilon-approximation for the general traveling salesman problem. An approximation algorithm for the weighted vertex cover using linear programming

    Part III: Exponential-time Techniques (around 7 lectures)
    Textbook NN Ch. 5 and 6
    The backtracking technique. Backtracking algorithms for problems such as the subset-sum problem, graph colouring, hamiltonian cycles, knapsack problems. The branch-and-bound technique. Breadth-first and best-first branch-and-bound. Branch-and-bound algorithms for the 0-1 knapsack and the traveling salesman problem. 

    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):
    if (0.25*M + 0.45*F)/0.70 < 50% then G=(0.25*M + 0.45*F)/0.70 
    if (0.25*M + 0.45*F)/0.70>= 50% then G=0.25*M + 0.45*F + 0.30*A
    IMPORTANT
    DATES:    		 Schedule of assignments and midterm test:
    weight: handout: (due) date:
    Assignment 1 10%  Sep 23 (Mon)  Oct 10 (Thurs) 10:00 am 
    Midterm Test 25%  -  Oct 24 (Thurs) 10:00 am 
    Assignment 2 10%  Oct 24 (Mon)  Nov 14 (Thurs) 10:00 am 
    Assignment 3 10%  Nov 14 (Thurs) Nov 28 (Thurs) 10:00 am 

    We expect to return assignment and midterm test marks within one week of the due date.

    Dates from the Academic Calendar:
    First lecture: September 5
    Last date to drop: November 4
    Last lecture: December 2
    Final Exam Period: December 5-20, 2001