CS 41: Algorithms

Fall 2000
Swarthmore College
Professor Andrew Rieger

Course Description

Welcome to Algorithms. This course is a continuation of the study of the basic data structures and algorithms found to be useful in many diverse areas . This study was begun in CS21, CS22, and CS35. The approach here will be more formal both with respect to correctness and with respect to the time and space resources required for the various algorithms and their associated data structures.

There will be numerous homework exercises and several programming projects illustrating the concepts presented. These projects should be regarded as a laboratory part of the course.

We are going to do this course in a modified seminar format. I will lecture some, expecially in the beginning, but will strive to include both class discussion and student presentations. Each week, reading and some other work will be assigned. You should hand in 'publication quality' written work and be prepared to present or discuss your work. You should also be prepared to discuss intelligently the reading. Some work will be assigned to groups. For work that is not expressly assigned to groups, I do not object to your talking about the problems or working together some of the time; but, the assumption is that each solution is independently arrived at unless noted by the solver.

Required text: Algorithms by Cormen, Leiserson, Rivest

Contact Info

Office Hours: 1:00-2:30pm Monday
Office: CS Reading Room, Sproul Observatory
Office Phone and Voice Mail: (610) 543-2398
E-mail: andrew@cs.swarthmore.edu If you need to see me but can't make it to my office hours, I'll be happy to schedule an appointment. Please contact me by e-mail or leave a message on my voice mail.

Grading

10% Homework Assignments
10% Project 1
20% Project 2
20% Project 3
40% Final Exam (To be scheduled by registrar. May be as late as Dec. 23)

Homework 1 (due Sept. 11)
Homework 2 (due Sept. 18)
Homework 3 (due Sept. 25)
Homework 4 (due Oct. 2)
Homework 5 (due Oct. 9)
Homework 6 (due Oct. 23, not graded)
Homework 7 (due Oct. 30)
Homework 8 (due Nov. 6)
Homework 9 (due Nov. 13)
Final Project (due Dec. 21)

Homework Policy

Written homework will generally be due by the beginning of class on Tuesdays. Late homework will not be accepted. Even if you miss a deadline, you are strongly encouraged to complete the assignment anyway, since this really is the only effective way to learn the material.

Academic Integrity

The utmost level of academic integrity is expected of every student. Under no circumstances may you hand in work done with (or by) someone else under your own name. If in doubt, credit the person(s) with whom you worked or from whom you got help. Discussing ideas and approaches to problems with others on a general level is fine (in fact, encouraged) but you must credit collaborators. Failure to abide by these rules constitutes academic dishonesty, and will be dealt with severely. Please do not put me or yourself in this unpleasant situation. Faculty are required to report academic dishonesty to the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Good Programming Style

In its purest form, programming is the art of expressing abstract ideas about computation in language that is as clear, unambiguous, and explicit as possible. To become a expert programmer, it is not enough simply to write programs that work correctly when run on a computer. Your programs must also be easy for other humans to read and understand. Indeed, good programming is as dependent on a deeply-developed sense of aesthetics as is good writing or other types of artistic activity. In short, style matters. Accordingly, programs will be graded with respect to both style and correctness. Good programming style typically includes the following: