Computer Science 160
Algorithms
Fall 2008 Syllabus
http://www.cs.tufts.edu/comp/160

FIRST EXAM: To be arranged
SECOND EXAM: To be arranged
FINAL EXAM: Friday, December 12th 3:30 - 5:30 pm.

Handouts:

Announcements, assignments, and handouts will be posted on the class web pages http://www.cs.tufts.edu/comp/160/documents . Please check frequently.

Brief Description:

Prerequisites: Prior completion of COMP 15 (Data Structures and Algorithms) and MATH 22 (Discrete Mathematics) OR the EXPLICIT permission of the instructor.

Class Meetings in Halligan 111B:

Lectures: Mondays and Wednesdays, 10:30 - 11:45 PM
Problem Sessions: Thursdays, 9:00 - 10:15 AM

Instructional Staff: (ta160@cs.tufts.edu):

Mail sent to ta160@ is sent to all of the instructional staff, including Professor Souvaine. Please try to make e-mails about homework questions concise. If a message takes more than one screen, then you should come to office hours or make an appointment to talk with someone in person or raise the issue in a problem session, instead of sending an email.

Prof. Diane L. Souvaine (dls@cs.tufts.edu)

.
Office: Halligan 102A Office Hours: TENTATIVELY Mondays, 2:30-3:30
Problem Sessions: Thursdays, 9:00-10:15 in classroom.

Mashhood Ishaque (mishaq01@cs.tufts.edu)

.
Office: Halligan Extension
Office Hours: TBA

Saket Joshi (sjoshi01@cs.tufts.edu)


Office: Halligan 107
Office Hours: TBA.

Textbooks:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms (second edition) MIT Press, Cambridge, MA & McGraw Hill, New York, NY, 2001. [REQUIRED]

S. Baase and A. Van Gelder, Computer Algorithms, 3rd edition, Addison-Wesley, Reading, MA, 2000. [RECOMMENDED]

Expected Work:

Students are expected to attend class regularly and to complete regular reading assignments in CLR. Students are responsible for all material covered in class as will as all material covered in the assigned reading, whether or not the material is also covered in class. Graded course work will include regular homework sets, frequent quizzes, two in-class examinations, one final examination, and one programming assignment.

Homework will be collected at the BEGINNING of the lecture on the specified due date and will NOT be accepted thereafter. Individual completion and submission of the homework with full attribution of sources is a prerequisite for passing this course. NOTE: Groups of people may work together at the outset, discussing and strategizing how to solve problems, and various other sources may be consulted, subject to the following conditions: EACH person must write up and submit his/her solutions in his/her OWN words; every person and/or text and/or web site consulted in the process of completing the assignment must be accurately cited on the homework paper submitted.
Spontaneous short quizzes will be given during the class period roughly once per week. At the end of the semester, the two lowest quiz grades will be thrown out, to cover for unavoidable absence from class. There will be no makeup quizzes. The two in-class exams and the one final exam will include questions similar to those included on homework assignments and will draw on material covered in lecture and/or in the reading. NO COLLABORATION IS ALLOWED ON QUIZZES OR EXAMINATIONS.
Toward the end of the semester, each student will pick a problem/algorithm of interest to implement and test.









Outline and Reading List :

1. Basic Concepts of Algorithm Design and Analysis
Background Reading: Chapters 1-4, C.1 & C.2
Application Reading: Chapters 6-9, 32.1 & 32.4
Technique Reading: Chapters 15, 16.1 & 16.2, 17 2. Basic Data Types and Corresponding Data Structures
Essential Reading: Chapters 10-14
Advanced Reading: Portions of Chapters 18-21 3. Graph Algorithms
Background reading: Chapter B
Application reading: Chapters 22-25 4. Coda on Algorithmic Complexity: Tractable and Intractable Problems
Reading: Chapters 34-35. Chapter 33.3.