Course Policies

Overview

The language of computer science is to a great extent the language of algorithms. Although there are many thousands of algorithms, there are relatively few basic design techniques. These include divide-and-conquer, greedy, dynamic programming, and backtracking. We will illustrate these techniques by studying a few fundamental algorithms of each type. In addition to helping us understand classic solution techniques, these algorithms have proven very useful in practice. Their names and the names of the problems they solve have become a standard part of the language of computer science.

Unfortunately, there is rarely a best algorithm to solve a given problem. Each approach involves a series of tradeoffs. Therefore, we will also study methods for evaluating the usefulness of an algorithm in a given situation. Among the various competing measures, we will focus primarily on the analysis of time and space complexity. However, a number of other issues will also be discussed.

Prerequisites

The prerequisites for this course are CS230 and MATH225. We will assume a knowledge of elementary data structures such as arrays, linked lists, stacks, queues, and trees. In addition, you should be comfortable with recursion. If any of this is unfamiliar or you have any questions, please come see me as soon as possible.

FirstClass Conference

The class conference on FirstClass is Wellesley Conferences/Courses/CS/CS231-S08. You should check the conference regularly. The conference serves two purposes. I will post important course announcements to the conference. Also, you are encouraged to post questions or comments that are of general interest to people in the course.

Textbook

The text for the course is Introduction to Algorithms, written by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, and published by MIT Press, Cambridge, Massachusetts. Copies of the text are available in the College Bookstore.

Course Requirements

• Problem sets: During the term, there will be regular homework assignments.
• Midterm examinations: There will be two midterm examinations. Both will be in-class. The first will be on Tuesday, March 11. The second will be on Friday, April 18. Please note these dates in your calendar, as they are not flexible.
• Final examination: There will be a comprehensive final examination at the end of the semester. The final exam is self-scheduled.
All examinations are open book and open notes.

Assignment Policy

All assignments are due at the start of class on the due date. Late assignments will not be accepted.

Collaboration Policy

I encourage you to talk with other students about the course and to form study groups. Unless otherwise instructed, feel free to discuss problem sets with other students and exchange ideas about how to solve them. However, I require that you must compose your own solution to each assignment. In particular, while you may discuss problems with your classmates, you must always write up your own solutions from scratch.

Please acknowledge any collaborative work. If you make use of an idea that was developed by (or jointly with) others, please reference them appropriately in your work. When working on homework problems, it is perfectly reasonable to consult public literature (books, articles, etc.) for hints, techniques, even solutions. However, you must reference any sources that contribute to your solution. Assignments and solutions from previous terms of CS231 are not considered to be part of the "public" literature. You must refrain from looking at any solutions from previous terms of CS231.

Grading Policy

The final grade will be computed as a weighted average of each of the requirements described above. The relative weight of each component is as follows.