CSI 4105 Winter 2014 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-14/
PROFESSOR: Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@eecs.uottawa.ca
OFFICE HOURS: Office: SITE 5-027 
Tuesdays 9:30AM-10:30AM
Wednesdays 9:30AM-10:30AM
LECTURES: Lecture 1: Wednesday 1:00-2:30 FSS 10003
Lecture 2: Friday 11:30-1:00 STE C0136.  
TEXTBOOK: Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2005. ISBN 0-321-29535-8. (Chapters 8-13)
Textbook will be available at Agora bookstore.
The textbook is required!
OTHER
REFERENCES:		 Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill, 2nd ed., 2001.  (Chapter 34 NP-completeness)

Kreher and Stinson, Combinatorial algorithms: generation, enumeration and search, CRC Press, 1998 (Chapter 3 Backtracking, Chapter 4: Heuristic searches).

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 to the theory of NP-completeness
    References: Textbook Chapters 8 and 9.
    Introduction to the course. Polynomial time reductions. 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. The complexity class PSPACE.

    Part II: Methods for dealing with NP-complete problems
    References: Texbook Chapters 10,11,12 and 13, and backtracking from other resources. Algorithms from the following topics will be covered:
    • Exhaustive algorithms (backtracking): solving small instances of hard problems exactly.
    • Solving polynomially-solvable special cases of hard problems.
    • Aproximation algorithms for NP-complete problems
    • Heuristic Searches/Local Searches
    • Randomized Algorithms
    MARKING SCHEME: 25% Midterm Exam 1 (M1)
    25% Midterm Exam 2 (M2)
    25% Assignments average (A) = 3 assignments (submit via blackboard learn)
    25% Project (P) = 2% project proposal (PP), 5% project talk (PT), 18% project report (PR)

    Final Grade (G):
    if (M1+M2)/2 < 50% then G=(M1+M2)/2  
    if (M1+M2)/2>= 50% then G=0.25*M1 + 0.25*M2 + 0.25*A + 0.25* P
    IMPORTANT
    DATES:

    		weight: due date: (tentative)
    Assignment 1 8.33%  February 4 (Tues)
    Midterm Test 1 25%  February 14 (Fri)
    Project Proposal 2%  February 25(Tues)
    Assignment 2 8.33%  March 11 (Tues)
    Midterm Test 2 25%  March 22 (Saturday) room/time TBA
    Assignment 3 8.33%  April 1 (Tues)
    Project Talk 5%  April 5 (Monday) time/room TBA
    Project Report 18%  due date TBA
    Dates from the Academic Calendar:
    First lecture: January 8 
    Study break: February 19-21
    Last lecture: April 4 (Friday)