4005-800-01: Theory of Computer Algorithms (RIT CS, 20081)

Department of Computer Science
Theory of Computer Algorithms (Winter 2008)
 4005-800-01 (Calendar Description)
Home --- Syllabus --- Slides --- Assignments --- Resources

Instructor: Richard Zanibbi, Office hours: Tues 2-4pm, Thursday 10am-12pm (or by appointment), 70-3551 (Golisano College)
Lectures (NOTE: two locations):
Mondays 12-1:50pm (70-2590, Golisano College)
Wednesdays 12-1:50pm (70-3435, Golisano College)

Syllabus

Calendar Description

A study of techniques to design and analyze the complexity of algorithms. This course will make students aware of a large number of classical algorithms and their complexity and will introduce the area of NP-completeness. Programming projects will be required. Class 4, Credit 4.

Prerequisites

Algorithms and Data Structures, and Discrete Math (4003-705 or 1016-265)

Course Outcomes

At the end of this course, students will be able to:

Course Text and Other Sources

Course Web Page: http://www.cs.rit.edu/~rlaz/algorithms20082/
Course Text: Kleinberg, Jon and Tardos, Éva. Algorithm Design. Addison-Wesley, 2005. [ Text Web Page ]

A list of additional recommended texts is provided within the course web pages at: http://www.cs.rit.edu/~rlaz/algorithms20082/Resources.html.

Grading Scheme

Students will be evaluated based on written assignments (completed individually), programming projects (completed in teams of two), quizzes, and midterm and final examinations.

6% Quizzes (3)
24% Assignments (4)
20% Programming project
20% Midterm Examination (1hr)
30% Final Examination (cumulative, 2hrs)

Provided that all quizzes and assignments are completed (and no 0's for academic dishonesty are received), the lowest quiz and assignment grades will be 'dropped' (rounded up to 100%) before computing a student's final grade.

Tentative Schedule

Please note that this schedule may change over the course of the quarter.

Week Topics Notes
1-2
  • Asymptotic analysis
  • Analysis of basic algorithms
  • Recurrences, divide-and-conquer
  • The Master Theorem
Wed Wk 2: Quiz 1
3
  • Greedy Algorithms
 Wed: Assign 1 due
Project posted
4
  • Dynamic Programming
 Wed: Quiz 2
5
  • Graph traversals
  • Minimum spanning trees
Wed: Assign 2 due
6
  • Minimum spanning trees, cont'd
  • Single source shortest path
Wed: Midterm exam
7
  • All pairs shortest path
  • Network Flow
Wed: Assign 3 due
8
  • Heuristics and Approximation
  • Linear Programming
Wed: Quiz 3
9
  • Complexity (P, NP, NP-completeness)
Wed: Assign 4 due
10
  • Other topics (TBA)
 Wed: Project due
11 Exam week: exam will be Monday Feb. 23 at 8-10am (location TBA).

Late Policy and Examination Rescheduling

Late assignment and project submissions are penalized 10% (1 letter grade) per day, for up to three days. After three days, late submissions will not be accepted.

Exams will only be rescheduled in the case of difficult situations for which there is formal documentation (e.g. a doctor's note). See the instructor as soon as possible if you encounter issues regarding exams.

Disability Services Office

If you have special needs for seating, tests, note-taking services, or other matters due to a disability, please contact the Disability Services Office (www.rit.edu/dso). If you receive approval for accommodation within the course, please contact me as soon as possible so that we can make the necessary arrangements.

Academic Dishonesty

Students may discuss assignments and projects with others, but submitted work (papers and code) must be created independently by each student or group, and not copied from another student or other source.