CSI 4105 FALL 2001 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/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@site.uottawa.ca
OFFICE HOURS: Office: MCD 314
Mondays 10:10-11:30; Thursdays 11:40-12:40; Thursdays 3:30-4: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, 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. Available at: the University of Ottawa Bookstore ($110.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 should 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.

Kreher and Stinson, Combinatorial Algorithms, CRC Press, 1998.
(Chapter 4 Backtracking)

Garey and Johnson, Computers and Intractability, Freeman, 1979.
(Chapters 1-3) This book is 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)
    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)
    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)
    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% Oct 1 (Mon) Oct 18 (Thurs) 10:00 am
    Midterm Test 25% - Oct 25 (Thurs) 10:00 am
    Assignment 2 10% Oct 29 (Mon) Nov 15 (Thurs) 10:00 am
    Assignment 3 10% Nov 15 (Thurs) Nov 29 (Thurs) 10:00 am

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

    Dates from the Academic Calendar:
    First lecture: September 6
    Last date to drop: November 2
    Last lecture: December 3
    Final Exam Period: December 6-21, 2001