Princeton University

Computer Science 226
Data Structures and Algorithms
Bernard Chazelle

Spring 2000
Computer Science Dept.
General Information | Announcements | Assignments | Collaboration Policy | Lecture Notes |Course Newsgroup

COS 226 lectures will be held in McCosh 50 after April 3 (include April 3).

Lecture Notes available at Pequod at Friday, March 31.

This course material has been prepared to supplement Algorithms in C by Robert Sedgewick. The schedule and some other information is specific to the spring 2000 offering of our algorithms course at Princeton, but much of the material may be useful to others taking and teaching similar courses.


COURSE INFORMATION

Instructor: Bernard Chazelle
chazelle@cs.princeton.edu
CS Bldg. room 404, 258-5380,
(Office hours W 11:50 am or by appointment).


Course Secretary: Sandy Barbu
barbu@cs.princeton.edu
CS Bldg. room 323, 258-4562


Lectures: MW 104 CS Building


Precepts: Monday or Tuesday, each lasts 50 minutes; all rooms and offices are in the CS Bldg.
First precepts 2/7 and 2/8.
Click on a precept number to get the list of students in that precept. If you are not in any list or if it is really impossible for you to attend the precept that you have been assigned to, please contact Xiaodong Wen and indicate the reason why.
Time Room Preceptors Office Phone Office Hours
1. Tue 4:30-5:30 p.m. 103 Elena Oranskaya or Spyridon Triantafyllis
eoranska@cs.princeton.edu , strianta@cs.princeton.edu
2. Mon 3:30-4:30 p.m. 102 Elena Oranskaya
eoranska@cs.princeton.edu 		217 8-0451 Thu 12:00-1:00 p.m.
3. Mon 7:30-8:30 p.m. 105 Yilei Shao
yshao@cs.princeton.edu 		415 8-1798 M 1-2 p.m.
4. Mon 3:30-4:30 p.m. 103 Spyridon Triantafyllis
strianta@cs.princeton.edu 		214 8-1793 Wed 3:00-4:00 p.m., Fri 1:00-2:00 p.m.
5. Tuesday 3:30-4:30 p.m. 102 Amit Chakrabarti
amitc@cs.princeton.edu
Ding Liu
dingliu@cs.princeton.edu 		313 8-6126 M or W, 3-4:30
Xiaodong Wen
wxd@cs.princeton.edu 		415 8-3946 W 7-8 p.m.
Lab TA coverage: Princeton has undergraduate lab assistants who are available to answer general computing questions in the labs and/or college clusters many days. These people should only be asked computer-related questions (e.g. unix, C, C++), not questions regarding course material or programming assignments. Please see the current schedule.

Text: The textbook is Algorithms, Third Edition, in C, Parts 1-4, Addison-Wesley, 1998. by Robert Sedgewick, ISBN 0-201-31452-5. Only the first half (Parts 1-4) of the new edition is currently available. You will get instructions on obtaining the second half of the text after the break. You may also find a book on C programming useful.

Prerequisites: The prerequisite for this course is COS 126. Students in the course should have an understanding of the basic principles of computer science and computer architecture, significant programming experience with a working knowledge of C and Unix (or some similar programming environment) and familiarity with elementary data structures such as arrays, stacks, queues, and trees. Most students registered for the course have this background; those who do not may have to work harder at the beginning.

The course will cover algorithms from a variety of applications areas, and several mathematical topics will be discussed. The course is intended to be self-contained with respect to such topics, but students are likely to find any mathematical experience helpful.

Attendance at lectures is expected.

Assignments and Exams: There will be nine programming assignments. Generally, they will be handed out on a Wednesday, with electronic submission due eight days later on Thursday (at 11:59 PM). Your submission must include a readme file which should not only provide details about your program, but also exhibit your understanding of performance characteristics and the general approach that you took to solve the problem.

There will also be nine weekly problem sets. These will be handed out on Wednesdays and due at precept the following week. These will consist of short questions on the material in the lectures, notes, and programs.

Midterm will be on March 8 at the usual time/place (104 at 11-11:50).

Do not, under any circumstances, copy another person's program. Writing code for use by another or using another's code in any form violates the University's academic regulations and will be dealt with harshly.

There will be a midterm exam on the Wednesday before break, which will cover all material up to and including the lecture on the previous Wednesday. The final exam will cover all material in the course.

Grading Policies: You will write some programs for the programming assignments, run them, and submit the code electronically. The code rarely speaks for itself, however, and it is your responsibility to hand in a separate printed writeup that describes what you did. This need not be verbose; indeed, you are better off making it terse. If we ask for a table, provide the table. If we ask to to run the program on some data, do it, then describe what happened. If you do extra credit work or something beyond what we've asked, explain what you did, thoroughly.

Do not refer in the readme file to any programming done after the electronic submission. We will be checking what you have said in your writeup by running your code. Discrepencies will lower your grade dramatically.

Grades on the programming assignments will be: 10(perfect in every way), 9(outstanding), 8(excellent), 7(very good), 6(good), 5(not bad), 4(poor), 3(minimal effort), 2(bad), 1(hopeless), or 0(not handed in). Grades on the problem set questions will be: 4(correct), 3(minor mistake), 2(major mistake), 1(poor try) or 0(all wrong).

The programming assignments, problem sets, and exams all contribute significantly to your grade. Specifically, your final course grade will be calculated as follows:

Late Policy: Assignments submitted late will be graded according to the following formula: S = .9 R exp(-t/3), where S is the grade given, R is the grade the work would have gotten if turned in on time and t is the amount of time (in days) the work was late. Thus, the value of a late assignment decays exponentially, with a half-life of just over two days. Examples: work turned in five minutes late gets 89.9% credit, one hour late gets 88.7% credit, six hours late gets 82.8% credit, one day late gets 71.7% credit, three days late gets 33.1%, and one week late gets 8.7%.

Assignments submitted more than a week late, or after the Dean's date, will receive no credit.

Keeping in Touch: The best way to contact the instructor, or preceptors is by electronic mail. To get help, you should try sending mail to your preceptor first, but you can also try the instructor or cs226@phoenix.


Important note: Please do not publish solutions to problem sets, exercises, and exams in a way that could compromise their utility as pedagogical tools. At Princeton, this is a violation of the basic rights, rules and responsibilities of members of the university community.

Rights and Responsibilities: Exams are closed book. This is change in policy from the past, so take that into account when studying past exams. You may bring a 8.5-by-11 sheet with handwritten notes to the exam. No calculators.

Problem sets should reflect your own work. Collaboration is inapproriate for the specific problems in the problem sets, though working with course assistants and other students in the class on similar problems is encouraged.

Programming, like composition, is an individual creative process. Individuals must reach their own understanding of the problem and discover a path to its solution. During this time, discussions with friends are encouraged. However, when the time comes to write the code that solves the problem, such discussions are no longer appropriate -- the program must be your own work (although you may ask teaching assistants or lab assistants for help in debugging). If you have a question about how to use some feature of C, UNIX, etc., then you can certainly ask your friends or the lab assistants or teaching assistants.

All rights reserved. None of this material may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise without prior written permission. Permission is granted to instructors who adopt Algorithms in C to use this supplemental material in conjunction with their course.

Copyright (c) 1999, Robert Sedgewick

Short history of credits: These course materials have been under development by R. Sedgewick since at least 1978. The index, course information and other .html files on this website were created by Ed Felten in 1993-95, adapting the course materials written by Sedgewick in 1991. The lecture notes and most assignments were rewritten by Sedgewick in 1996-1997 and are being further updated in 1998-1999. Problems in exams and problem sets are adapted from many sources, but primarily the new (third) edition of Algorithms in C.

cos226 Class Page
Last modified: February 2000