CSci2111 Data and File Structures

Instructor

Nathalie Japkowicz, Room 214, CS Building, x3157, nat@cs.dal.ca

Meeting Times and Locations

Time: Tuesdays and Thursdays, 10am-11:30am;
Location: Auditorium, CS Building

Office Hours and Locations

Times:
- Mondays, 10:30am-12:30pm
- Tuesdays, 1-2pm
Location: Room 214, CS Building

Markers

Kirk Brown, kbrown@cs.dal.ca
Yongcun Hu, YHu@cs.dal.ca
Yan Wang, yan@cs.dal.ca

Overview

Although secondary storage such as disks, magnetic tapes and CD-ROMs allow us to store thousands of megabytes, access to such storage is very slow as compared to other kinds of computer operations. A file structure is a combination of representations for data in files and of operations for accessing these data, and the study of file structure design is geared at improving the efficiency of data access. The topic of file structure design is closely linked to that of advanced data structures as a number of interesting data structures (including AVL Trees, B Trees, B+ Trees and Hash Tables) are useful for achieveing high efficiency in file operations. This course will provide a solid introduction to the topic of file structure design and will discuss, in detail, the data structures necessary for achieving its efficiency objectives.

Pre-Requisites

Computer Science III (CSci2110) and Topics in Applied Computer Science (CSci2131). Knowledge of C++ or Java.

Evaluation

Students will be evaluated on:

A series of 5 written or programming assignments (20%)
A programming project that will be implemented incrementally over the semester
(and incorporated in the assignments)(30%)
A Midterm (20%)
A Final Exam (30%)

Timetable

Thursday, January 20: Assignment # 1 handed out (Due on February 3)
Thursday, February 3: Assignment # 2 handed out (Due on February 17)
Tuesday, February 22: Midterm Review
Thursday, February 24: Midterm
Monday February 28-March 6: Study Break
Tuesday, March 7: Assignment # 3 handed out (Due on March 23)
Tuesday, March 21: Assignment # 4 handed out (Due on April 4)
Thursday, April 6: Final Review
Wednesday, April 12, 9am, DUNN117: Final Exam

Assignments

In order to print a postscript file, first save the file onto your borg directory by pressing the ESC key and the right-mouse button simultaneously. Call it, say, assignment1.ps. Then you can print this file by typing "lw -Pprinter-name -ps assignment1.ps" from borg (unless you own a postscript printer, you will not be able to print the file at home).

Assignment # 1
Assignment # 2
Assignment # 3 , Court Cases , Solution
Assignment # 4 (Old Version), Assignment # 4 (New Version [April 2, 2000]), Solution available from my office door (If copies run out, please send me mail at nat@cs and cc it to all-cs2111@cs [A single message will suffice])..

Late Policy

Late assignments will receive a 10% penalty per day (Saturdays and Sundays count as late days as well) unless a Doctor's note is provided.

Required Textbooks

File Structures, An Object-Oriented Approach with C++, by Michael J. Folk, Bill Zoellick and Greg Riccardi, Addison Wesley.

Preliminary Syllabus (the lecture slides can be retrieved by clicking on the links attached to each topic):

Week	Topics	Readings
1	Preliminaries Slide Viewer Powerpoint File & Introduction to File Structures Slide Viewer Powerpoint File & Basic File Processing Operations Slide Viewer Powerpoint File	Chap. 1 & 2
2	Secondary Storage and System Software (Part I) Disk Slide Viewer Powerpoint File & Tape Slide Viewer Powerpoint File	Chap. 3 (Begining of chapter to Section 3.5 (excluded))
3	Secondary Storage and System Software (Part II): CD-ROM and issues in Data Management Slide Viewer Powerpoint File Chris Maxwell's Presentation on the Unix File System	Chap. 3 (Section 3.5 (included) to end of chapter)
4	Fundamental File Structure Concepts & Managing Files of Records Slide Viewer Powerpoint File Organizing Files for Performance Slide Viewer Powerpoint File	Chap. 4, Chap. 5 & Chap. 6
5	Indexing Slide Viewer Powerpoint File	Chap. 7
6	Cosequential Processing and the Sorting of Large Files Slide Viewer Powerpoint File	Chap. 8
7	MidTerm Week (Review + Exam)	Chaps. 1, 2, 3, 4, 5, 6, 7 & 8
8	Multilevel Indexing and B Trees Slide Viewer Powerpoint File	Chap. 9
9	Indexed Sequential File Access and Prefix B+ Trees Slide Viewer Powerpoint File	Chap. 10
10	Hashing Slide Viewer Powerpoint File	Chap. 11
11	Extendible Hashing	Chap. 12
12	Extendible Hashing; Final Review	Chap. 12; All Chapters

Note: We may not have enough time to cover all the topics discussed in the textbook. Announcements will be made in class regarding the section that we skipped.