CS241 Syllabus - Spring 2008

Class Meeting Time

10:30 to 11:45 am Tuesday and Thursday, OLB 105

Instructor Information

Dr. Jennifer Walter
Office phone: 437-7449 Office: 124 OLB
Home phone: 485-1413 Email: walter at cs dot vassar dot edu

Office hours: 1:30 to 3:30 pm Tuesday, 3 to 5 pm Monday and Wednesday and by appointment.

Text

Introduction to Algorithms, 2nd ed., Cormen, Leiserson, Rivest, and Stein, McGraw-Hill.

Course Goals

By the end of the semester you should:

be familiar with fundamental algorithms and algorithmic techniques for a given problem domain,

be able to decide which algorithm among a set of possible choices is the most efficient solution,
be able to prove correctness and to analyze the running time of a given algorithm, and
be able to design efficient algorithms for new situations.

Course Content and Order of Lecture Topics

Introduction and Mathematical Fundamentals - Chapters 1, 2, 3, and 4
Sorting - Chapters 6, 7, and 8
Selection - Chapter 9
Hashing - Chapter 11
Basic Graph Algorithms - Chapters 22, 23, and 24
Data Structure for Disjoint Sets - Chapter 21
Dynamic Programming - Chapter 15
String Matching Algorithms - Chapter 32
Geometric Algorithms - Chapter 33
NP-Completeness - Chapters 34, 35

Grading

First Exam (Thursday, February 21) = 20%
Second Exam (Thursday, April 10) = 25%
Final Exam (Time to be determined) = 25%
Weekly Written assignments and small between-class assignments = 20%
Participation = 10%

Requirements for the course consist of three exams, weekly written assignments, weekly quizzes, and possible in-class student presentations. You are responsible for keeping up with the reading and for all material covered in class (some of which may not be in the book). This includes classnotes, assignments, handouts, additional readings, etc. If you miss a class for any reason you are responsible for making arrangements with classmates to provide you with all information disseminated in class that day. No make-up exams or quizzes will be given unless you get an official excuse from Baldwin, the Dean of Studies, or advance permission from the instructor.

Classroom Etiquette

We are all interested in hearing your questions and views. But remember that part of class participation is also being an alert listener. If you have issues and questions in class that I feel are best addressed during my office hours, I will make the suggestion that we continue our conversation "off-line," and I hope you will be so kind as to honor my suggestion.

Rules for Assignment Preparation & Submission

One goal of this course is to develop your facility to develop and analyze algorithms, so individual completion of weekly assignments is extremely important. Assignments and due dates are included as they are determined in the Schedule. Assignments are due at 8 pm on the indicated dates (to give you time to finish up after class if necessary). Full solutions to all problems will be handed out in class, attached to your graded assignments.

No late assignments will be accepted unless you have arranged for late submission in advance of the due date with the instructor.

PLEASE NOTE: Neatness counts! Two points will be automatically deducted from any assignment that does not meet the following requirements:

Solution must be clearly indicated.
Show all the steps used to arrive at your solution.
Write legibly and hand in clean copy. When in doubt, ask the instructor if your work is sufficiently legible.
Hand assignments in on 8 x 11" lined paper or on 8 x 11" computer printout (i.e., use of LaTex is encouraged), preferably stapled in the upper left corner.
Do not hand in paper with frayed edges torn from a notebook.

Academic accommodations are available for students with disabilities who are registered with the Office of Disability and Support Services. Students in need of disability accommodations should schedule an appointment with me early in the semester to discuss any accommodations for this course which have been approved by Office of Disability and Support Services, as indicated in your DSS accommodation letter.