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.
You 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.
Printed 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.
Homeworks 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.