COS 226 - Assignments (Spring 2000)

Computer Science 226
Data Structures and Algorithms
Bernard Chazelle

Spring 2000

Computer Science Dept.

General Information | Announcements | Assignments | Collaboration Policy | Lecture Notes

There are 2 problem sets 6 without names on them. The authors please send mail to Xiaodong Wen to claim them.

Contents of this page:

Policies
The Programming Assignments
The Problem Sets

Overview: 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). These programs may be developed on the computer of your choice. However, your finished programs must run on one of CIT's arizona machines or on the SparcStations located in CS 101. 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. It is your responsibility to describe how you have completed the assignment in the submission, not ours to glean this information from your code.

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. These are a very important part of the course and should be taken seriously. Not only do they contribute a substantial percentage to your grade, but also you can be sure that many of the questions will reappear on the midterm and final, but with different input data.

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:

programming assignments: 39%
problem sets: 26%
midterm exam: 13%
final exam: 22%

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.

There will no extensions due to scheduling conflicts, computer downtime, or other such factors, except under truly extraordinary circumstances. Extensions will be granted only for university-sanctioned excuses such as illness, and then only with the proper documentation. You are responsible for planning ahead and managing your time so that you can complete the assignments on time. You must either finish on time or accept the consequences of doing otherwise.

Unless prior arrangements are made, a grade of zero will be recorded for missed exams.

Computers: You may develop your programs on any machine that you like. However, your finished programs must run on one of CIT's SparcServers (phoenix, tucson, flagstaff) or on the SparcStations located in room 101 of the CS building. Programs may be written in any programming language, except that you may not use assembly language unless the assignment explicitly permits it. (Of course, your program cannot run on the Sparcs if the language you use isn't supported on the Sparcs.) Students who have already registered for this course should already have their accounts. Students who had accounts in past semesters will have the same login (userid) and password. Other students must go to the CIT Clinic at 87 Prospect to set their password.

Students taking several courses using CIT facilities will have one account and their disk quota will be the sum of the disk quotas for all courses.

Do not allow anyone else to use your accounts for any purpose. They are for your use alone, and you are responsible for any misuse. Your passwords control access to your accounts and should be kept secret.

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.

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.

Submitting Programming Assignments: Submit your solutions to the programming assignments electronically using the following command.

/u/cs226/bin/submit number files

number is the assignment number and files is the list of files for that assignment. For example,

/u/cs226/bin/submit 31 readme makefile main.c strings.c

submits the files readme, makefile, main.c, and strings.c for a fictitious assignment 31.

The submit command copies your files to the directory /u/cs226/submit/login/number and lists all the files that you have submitted for assignment number. login is your user account name. If you execute submit after the assignment deadline, your files are placed in directory number-late. You can run submit more than once, and you can submit partial lists of files.

There's also unsubmit, which allows you to `unsubmit' one or more files. For example,

/u/cs226/bin/unsubmit 31 main.c

would remove your main.c from the submission directory.

You can omit the /u/cs226/bin/ prefix if you add /u/cs226/bin/ to your PATH variable. You must execute submit on one of the SparcServers.

When appropriate, submissions may also include a file named makefile, written so that the command `make' builds your program, and the command `make clobber' removes all `derived' files, e.g., object files, executable files, and libraries. For details about make, see its man page.

The Programming Assignments:

2. Bin packing

6.Search for clusters

7.Convex Hulls

8.Euclidean Minimal Spanning Tree

9.Traverse a maze

The Problem Sets:

1: due in precept on Feb.14/15: ps file or pdf file.