CS 2604 Data Structures and File Management
Summer II 2003
Instructor
John Paul C. Vergara, PhD
Email:
jpv@cs.vt.edu
Office: McBryde 625, 540-231-9367
Office Hours: M 1pm - 3pm, TWR 11am - 12pm, and by appointment
GTAs
Brandon Berry,
brberry@vt.edu
- Office hours: 11am - 1pm MTWRF
Kiran Kumar Indukri,
kindukur@cs.vt.edu
- Office hours: 2pm - 3pm TWR, 2pm - 4pm F
Tony Allowatt,
aallowat@vt.edu
- Office hours: 1pm - 2pm MTWRF
All office hours are in McBryde 133.
Announcements
-
Final grades will be available on Hokie Spa on Wednesday, August 13, 2003.
- 8/7: Program 3 grading input files posted
- 8/6: Final exam coverage posted (under Schedule)
- 8/5: Remaining schedule posted
- 8/4: HW 3 posted (Extra Credit)
- 8/1: Hashing handout posted
- 7/31: Sample file posted for Program 2, more to come
- 7/29: HW 2 note added
- 7/26: Radix sort posted
- 7/26: Program 3 posted
- 7/25: Program 2 deadline extended
- 7/24: HW 2 posted
- 7/22: Sorting applet added
- 7/18: Schedule posted
- 7/16: Correction to Simulation Handout posted
- 7/16: Program 2 posted with sample files
- 7/9: Program 1 and HW 1 deadline extended to 11:59 pm
- 7/8: HW 1 posted
- 7/6: Test files for Program 1 added
- 7/1: Program 1 posted, link to forum added
- 7/1: Added pledge link
- 6/30: Prereq clarification posted
- 6/30: Welcome to CS 2604
Schedule
- July 22: Midterm Exam (Coverage is Chapters 1 through 6 and section 7.2)
- July 25: Programming Assignment #2 due
- July 28-30: Demo for Programming Assignment #2
- July 30: HW 2
- August 5: Programming Assignment #3 due
- August 6: Exam review
- August 7: HW3 due by noon, optional
- August 7: No class, Dr. Vergara office hours: 10:00am - 12:00pm
- August 8: Final Exam, 10:30am, McB 126
- Final exam coverage
- The final exam is closed-notes and multiple choice. It will cover all topics in the course although around 80% of the questions will come from the last 3 week of classes.
Programming assignments
- Project 1 - due July 9, 11:59 pm
- Project 2 -
due July 25, 11:59 pm
- Project 3 - due August 5, 11:59 pm
- NOTE: When counting the number of hash table accesses, be sure to count when you try to access a non-existent overflow slot. For example, consider when bucket size is 1 and all buckets are full, with no overflow. If you try to find a non-existent record, you would first check the bucket it hashes to, then check overflow. That is 2 accesses, even though no overflow slots actually exist in the file. While for this program you can keep track of how many overflow slots there are and therefore avoid actually performing that final access, it is still considered an access because you are retrieving information about the hash table. An example in the sample files is the command "find 123456789" used for out_s.txt.
- Curator (for program submission)
- Required pledge for all programs
Homework assignments
- HW1.pdf - due July 14, 11:59 pm
- HW2.pdf - due July 30, 11:59 pm
- Some notes on item 4 of the HW:
In case of ties for the LFU policies, select the lowest numbered block.
You do not have to show the state of the buffer pool at every step; just show
the contents of the buffer pool at the end of the simulation AND indicate the
number of the LAST block that was swapped out of the pool.
- HW3.pdf - due August 7, noon
- Submission template: HW3temp.doc
- This homework is extra credit and is worth 2% of your final grade. No late submissions accepted. You must use the submission template.
Textbook
- A Practical Introduction to Data Structures and Algorithm Analysis,
2nd Ed, by Cliff Shaffer, Prentice-Hall 2001.
- Notes are available at A1 Copies, University Mall.
Pointers to other information
Prerequisites clarification
- A grade of C or better for CS 2704 and CS 2204 if you are a CS major or
minor
- A grade of C- or better for the CS prerequisites if you are a CPE major
- A *passing grade* for MATH 2534 or MATH 3034
Please note that you only need a passing grade for the MATH course.