2604 - Fall 2004
Structures and File Management
CRN 91438, Tues/Thurs 2:00pm - 3:15pm, McBryde 126
Tues/Thurs 10:30am - 11:30am & by appt.
| Alain Fabian
| Ian Will
GTA Office hours:
TA Office Hours, McBryde 133
- Final course grades should be available through Hokie SPA.
- Final exam grades (and quiz #10 grades) are posted as a grade report announcement to your Curator accounts.
- The plan was to post your final exam grades to the Blackboard system, but it has been taken down for an upgrade and maintenance until January 9, so the Curator was used instead.
- Gradesheets for Project #4 are now posted to the Curator accounts.
- Grades for Project #4 and Homework #4 are listed in the Blackboard
The final exam for CS 2604 will be held in Davidson 3,
on Monday, December 13, from 7:00pm - 9:00pm.
- Solutions for Homework #4 have been posted on the
homeworks section of this website.
- The last quiz (which I had planned to give on Dec 2 but forgot)
will be given in-class on Tuesday, Dec. 7.
Quiz #10 will have two questions:
one to find a minimum spanning tree of a given graph,
and a second to identify if a subgraph induced by removing
some verticies of the given graph is a complete graph on four
After the quiz, I will go over the solutions to the quiz
since Dec. 7 is the last day of class.
- Also on Dec. 7:
I will go over the solutions for Homework #4 and hand out
I will also bring all the unclaimed, graded assignments
that I have to class, so if you are missing a quiz, homework,
or the mid-term you can pick it up then.
- Please see my post on the class discussion forum
for a clarification of the BST deletion example that
I talked about in class on Dec. 2:
- Gradesheets for project #3 have been posted to Curator accounts.
- Grades for project #3 have been added to the grade book
- On the class discussion forum, Dr. Shaffer has provided some
good advice and clarifications about Project #4.
I highlighted and discussed some of these at the end of class today.
Below is a list of message threads that discuss
some of the topics I mentioned.
These message threads proably give more specifics than
I was able to in the discussion in the last few minutes of
class today, so I recommend reading these:
- Homework #4 was handed out in class on Nov 18 and has now
been posted on the homework page of the web site.
- Homework #4 is due IN-CLASS at 2:00pm on Thursday, Dec 2.
- Some minor revisions to the Project 4 spec have been posted.
There are two changes. Below is a summary of the changes as
posted by Dr. Shaffer to the class forum and copied here:
- The number of buffers in the buffer pool will be
in the range 1-20.
- The question came up as to how the client
(the bintree) knows the length of the city name
when that is returned from the memory manager.
The layout for that message has now been specified
(it wasn't in the original spec) as follows:
"The city name will be sent to the memory manager
as a separate message. This message will contain
the length of the name in the first byte, followed
by the characters for the name. The null character
at the end of the city name string should not be
included in the message, nor stored on disk."
- Graded Homework #3 papers were handed back in class today.
- Grades for Homework #3 are posted on Blackboard.
- A solution key for Homework #3 has been posted.
- Project #4 has been posted to the programming projects
page of the website. Note that Project #4 is worth more points
than the prior projects -- it is worth 150 points total.
As such, the early bonus has been increased to 15 points and the
late penalty has been increased to 30 points.
Project #4 is the final programming project for the semester
and the on-time due date is December 7.
- Homework #3 is due IN-CLASS at 2:00pm on Thursday, Oct 28.
- A test data file has been posted for Project #3. Please read the class forum posting by Dr. Shaffer titled, "Project 3 test data", to help understand aspects of this test data file.
- Grades for Project #2 have been posted in the on-line gradebook on Blackboard. Gradesheets for Project #2 are available for download from the Curator.
- Homework #3 was handed out in class today and
is posted on the Homework section of this website.
This homework assignment will be
handwritten and turned in in-class,
at the start of class (2:00pm) on Thursday, October 28, 2004
Write your answers on the homework document in the space provided
for each question. Be sure to write your name on each page and
keep the pages stapled together.
No late assignments will be accepted.
- Project #3 has been posted and is due Nov 2.
- On page #2 of the project #2 specification, in the description of the debug command it refers to Figure 13.5(a) in Dr. Shaffer's textbook. I think this should be referring to Figure 13.15(b).
Figure 13.15(b) is included in section 13.3 of Dr. Shaffer's book that you can download from the projects page on the course website.
- Information about the search radius in Project #2
(copied here as it was posted by Dr. Shaffer
on the class forum):
- "Ideally, you would be comparing the search circle against the node's rectangle to decide whether to visit a node (subtree) during the regionsearch traversal. In practice, its just to hard to implement a circle vs. rectangle intersection operation, so we don't expect you to. Just compare the bounding box for the circle (i.e., a square) against the node's rectangle. When you get down to a leaf node, do a simple euclidean distance test. Actually, you don't even need to take the square root... just compare the sum of the squared differences in X and Y vs. the square of the radius."
- Grades for Homework #2 and Project #1 have
- The grade sheets have been
posted as announcements in your Curator
account and can be downloaded from the
- The scores have been entered into the
on-line gradebook on Blackboard.
You can review all your grades by
loging into Blackboard at
- On Homework #2, problems #2c and #2d
both had indicies that started at zero
and were multiplied by 2. This would
result in an infinate loop. Because
of confusion about these
two problems, we accepted either the
answer of infinity or the answer
that assumes that the loop starts at 1.
- The graded mid-term exams will be handed
back in class on Thursday (Sep 30).
The mid-term exam grades will be posted on
Blackboard after the exams have been
handed back in class.
- It is a good idea to check the grades
that appear on your graded work to make sure
that they match the grades stored in the
on-line gradebook on Blackboard. If you find
any discrepencies, please let Mr. Capra know
- Test data files have been posted for
Project #2 on the projects page.
- Files used by the graders to test
Project #1 have been posted on the projects
- A link has been posted on the projects
page to some example code from Dr. Shaffer's
book that shows an example of using
inheritance for separate internal and leaf
node representations for a binary tree.
Sep 21, 6:25pm
- Some of this was announced in class on Tuesday, but here is information about the mid-term for my section:
- The mid-term exam will cover material up to and including the BST material I covered in class on Tuesday, Sep. 21. Thus, BST properties and BST insert could be on the exam, but BST searching and delete will not.
- The exam will be closed book, closed notes and no calculators will be allowed.
- The exam will not take the entire class period. I will spend the non-exam time in class on Thursday talking about project #2.
- Solutions to Homework #2 have been posted.
- Because solutions have been posted, no late submissions
will be accepted for Homework #2.
- Two koofers for the mid-term exam have been posted.
- Keep in mind that:
- These koofers may have material that we have not covered yet and that may not be on the midterm this semester.
- There may be material that we have covered that is not on the koofers, but could be on the midterm this semester.
- Project #2 has been posted and is due at 11:00pm
on October 12.
- Homework #2 has been posted and is due at 5:00pm
on September 21.
- A reminder that the MID-TERM EXAM will be
in class on September 23.
- FOLLOW-UP ABOUT USED BLOCK LISTS
In my (Capra) section, the concept of a "used block list" was discussed as a possible way for the Memory Manager to keep track of the sizes of the blocks that it had allocated.
For my (Capra) section ONLY, if you have an implementation that uses the used block list approach, we will accept it.
Keep in mind that your implementation still must follow good design principles and that you should have comments that explain and justify your design decisions. Specifically, you should include in your comments an explanation of the pros/cons of the used block list.
- VERY IMPORTANT --
PROJECT #1 SPECIFICATION ADDITION/CLARIFICATION
Two important announcements about project #1:
- There is an ADDITION to the project specification:
When the memory manager is allocating space from a free block, it will allocate the FIRST bytes in that block. For example, lets say that the memory manager is given a request for 100 bytes. It chooses to satisfy this request from a block of 300 bytes. It is the FIRST 100 bytes of the 300 that get used, and the LAST 200 bytes are put back into the free block pool.
- Also, a CLARIFICATION has been posted to the Class
- A test data file has been posted for Project #1
on the "Programming Projects" section of this website.
- The TA office hours have been posted in a PDF
document linked to in the "Teaching Assistants" section
of the main course webpage.
- Correction: The mid-term will be on THURSDAY, Sep 23.
- The course notes have been dropped off at A-1 Copies and
should be available by Monday (they may be available over the
week-end, you might want to call before you go over).
- Curator accounts have been set-up and you should be
receiving an automated email message from the Curator system.
- The TAs will begin holding their office hours starting
Aug 30. There will be a CS 2604 TA in McBryde 133 from
10:00am - 6:00pm, Monday through Friday.
- Several important changes have been made
to the Syllabus and Course Policies:
- The mid-term exam will be on
Thursday, September 23
(this will allow the mid-term to be graded before
the last day to drop courses).
- The late penalty for programming projects will be 20%.
- Several topics have been re-ordered on the
- These three changes are reflected in a revised version
of the CS 2604 Syllabus and Course Policies document
posted in the Information section (see above) of this web page.
- Programming Project #1 has been posted and is due Sep 14.
- The early bonus for Project #1 will be 10%
and the late penalty will be 20%.
- A section from Dr. Shaffer's book has been posted
on the Programming Projects page that you can read
for background on the project.
- Homework #1 has been posted and is due on Sep 2.
- Please note that Mr. Capra's office hours are listed incorrectly
on the handout given in class. The correct hours are:
Tues/Thurs from 10:30am - 11:30am and by appointment.
- Welcome to CS 2604!
- Attendance on the first day of class is mandatory. If you
do not attend class on the first day, you will be dropped from the
- Important announcements will be posted here throughout the
semester. It is the responsibility of each student to check these