Data Structures
Computer Science 410
Fall 1997
ANNOUNCEMENTS
- Final has been graded. You can find out your grade on the
final, the mean of the final, and your grade in the course by
either
- You can see the graded final if you come by 4105 during the
day.
- The grades of all previous assignments (including also the
extra credit for pointing out mistakes in the book) are posted in
front of 4105 Upson. Let us know if there is a mistake.
- All Graded Assignments are available in the undergrad office
303 Upson .
- Previous prelims can be picked up in 4105 Upson.
Time and place:
- Tuesday, Thursday 2:55-4:10 pm.
- Kimball B11.
Pointers to General Information:
Instructor
Teaching assistants
A separate page has information
about office hours for the staff.
Please make sure to include your email address in your signature
whenever you send email using the Web.
A very distressing error relevant to all projects:
-
There should be a typecast in the malloc statement in
the function link NEW (), as:
link x = (link) malloc (sizeof *x);
(Dan Ryazansky). This is a fairly consistent error in the text, and
in general, if you're not familiar with C, you should either come
talk to us about how one should use malloc, or
look at page 142 of the Kernighan and Ritchie reference on C, which
discusses why this typecast is necessary. (Also, dan objects to the
use of *x here in the sizeof expression--while it is true
that sizeof doesn't evaluate its expression, it's still rude to
make reference to objects like *x that don't yet
exist.)
The separate page has information about
all other errors in the text, that have been found so far.
Please send email to Amit
Kumar if you find other errors.
- Prelim 1: Thursday, October 9
- Prelim 2: Thursday, November 6.
- Final: Thursday, December 11, 12-2:30.
Prelims will be given in class.
Y ou should be comfortable with programming in C or C++. The
official prerequisites for the course are CS211 or CS212, and
CS280. You can take the course without CS280, as long as you are
familiar with programming with recursion and pointers (see CS211 or
CS212), and you can do simple proof by induction. If you have any
doubts about being prepared for the course, see the instructor.
-
- Written assignment 1 due September 9,
at the beginning of class.
Solution for written assignment 1
- Project 1 due September 18, at the
beginning of class.
The code for 10 random coin
flips.
The solution to Project 1 consists of the header files queue.h and printqueue.h and the program files queue.c and printqueue.c .
- Written assignment 2 due September 25,
at the beginning of class.
Solution for written assignment 2
- Project 2 due October 7, at the
beginning of class.
The code is an example of opening,
reading and closing a file.
The file primes.txt is a list of
useful primes. The text files short1.txt, and short2.txt are for testing your code. The
file long.txt is for producing the
statistics.
The solution to Project 2 consists of the header file hashTable.h and the program files hashTable.c and prog2.c .
- Written assignment 3 due October 23,
at the beginning of class.
Solution for written assignment 3
- Programming Project 3 due November
4, at the beginning of class. The sample code filewrite.c shows how to write to a file.
You will need to use the better random number generator newrand.c for the project.
The solution to Project 3 consists of the header file bst.h and the program files bst.c and main.c .
- Programming Project 4 due November
25 (not November 20 as before), at the beginning of class.
Optional part can be submitted any time until classes end.
The codes you need are lz.h , bits.h , bits.c , dict.h , dict.c
, encode.h , encode.c, decode.h , and decode.c.
The files you need to compress are prog4.tex and prog4.ps .
- solution for project 4.
- Written Homework 4, due December 4, at
the beginning of class.
- Solution to written Homework
4.
- There will be weekly assignments. They will be due at the
beginning of class: 4 written assignments and 4
programming projects.
- Graded homework is available in a self-service stack in the
Undergrad Office, 303 Upson.
- If you prefer that we hold onto your homework until you pick it
up then you should clearly mark HOLD at the top of the first
page of the homework.
- Homeworks will only be accepted in class and on time.
Late homework will receive decreased grade. However, to cover cases
of emergency or illness, one assignment will be accepted one
lecture late without penalty. You do not need to inform me about
late homeworks in advance or to give me any excuses. Excuses for
late homeworks beyond the first one will only be accepted under
exceptional circumstances.
- Some of the problem sets will involve programming. It is
expected that these assignments will compile and execute correctly.
We will also expect you to use good programming practices such as
structured code and comments.
P rinted handouts are available on the Web. In addition, extra
copies of these handouts will be dropped off at the Undergraduate
Office, 303 Upson, immediately following class.
I will use some transparencies for the lectures. Copies of the
transparencies will be available at the lecture, but will
not be available afterwards.
Current handouts for the course:
- Programs can be written in either C or C++.
- There are 50 PC's running Windows NT in the labs available for
your use. There is Visual C++ on the PC's. The homework solutions
we post will be written in C using Visual C++. Information on how
to use the labs, and how to use Visual C++ (assuming you do know C
or C++) will be distributed later in the course.
H omeworks and exams will be weighted roughly as follows.
- Written assignments: 20% in total
- Programming assignments: 25% in total
- Two midterm exams (10/9 and 11/6): 35% in total
- Final exam (12/11): 25%
-
You can only use PC's in the Lab. The HP machines from
last year are gone this year.
-
If you did send us email by Wednesday, as requested, you account
information is available in 4105 Upson from Kelly McCarthy between
8:30 and 4 Monday -- Friday.
-
If you did not send us email requesting an account so far, then
do so ASAP. Send email to Amit Kumar with the following
content. The subject of your message should be "CS410 Lab account".
The content of the message should be a single line of the
format:
6-digitCUID# tab netid tab Lastname,
Firstname
Students are allowed to collaborate on the homework to the extent
of formulating ideas as a group. Each student is expected to write
up the homework by himself or herself. Students may not copy any
part of someone else's written homework or code.