Bilkent University*
COMPUTER ENGINEERING DEPARTMENT

CS351: DATA ORGANIZATION and MANAGEMENT

Fall 2010
Section 1:        Mon.  10:40, 11:40, Thur.  08:40, 09:40; EB104  
Section 2:        Mon.  15:40, 16:40, Thur.  13:40, 14:40; EB101
Section 3:        Tues.  15:40, 16:40, Fri.    13:40, 14:40; EB204

Hours not underlined are reserved for possible makeups.

INSTRUCTOR

Dr. FAZLI CAN
Office: EA505, Phone: 290-2613
Office Hours: Mon. 14:40-15:30, Thu. 10:40-11:30 and by appointment
E-mail: canf at cs dot bilkent dot edu dot tr

ASSISTANTS

HAYRETTİN ERDEM
Office: EA126, Phone: 290-3019
Office Hours: Wed. 9:40-11:30, and by appointment
E-mail: hayrettin at cs dot bilkent dot edu

ÇAĞRI TORAMAN
Office: EA126, Phone: 290-3019
Office Hours: Wed. 13:40-15:30, and by appointment
E-mail: ctoraman at cs dot bilkent dot edu

EMRE VAROL
Office: EA531, Phone: 290-1451
Office Hours: Thu. 13:40-15:30, and by appointment
E-mail: evarol at cs dot bilkent dot edu

COURSE OBJECTIVES

Structure, organization and processing of files. Physical characteristics of storage media. Sequential file creation, access, and update. Sort/merge algorithms.
Direct file processing techniques. Dynamic hashing techniques: Extendible, Linear and Dynamic hashing. Indexed and Relative files: creation, processing and update.
B trees and  B+-trees as index structures and their maintenance.  File inversion, secondary key retrieval techniques. Introduction to database management systems. Three level system architecture. Entity-Relationship Modeling. Relational Model of Data.  Relational Algebra and Relational Calculus.

Prerequisite: CS 202-Fundamental Structures of Computer Science II.

COURSE SCHEDULE

The following program is subject to change throughout the semester. (Syllabus)

PREREQUISITE

CS 202 - Fundamental Structures of Computer Science II.

TEXTBOOK AND REFERENCES

Ramakrishnan, R., Gehrke, J. Database Management Systems, 3 ^rd ed. McGrawHill, Boston, MA, 2003. (Current Textbook).
Tharp, A. L. File Organization and Processing, John Willey & Sons, New York, NY, 1988. (QA76.9.F5 T48 )
Salzberg, B. File Structures: An Analytical Approach, Prentice Hall, Endlewood Cliffs, NJ, 1988. (QA76.9.F5 S25)
Korth, H. F. Sllberschatz, A. Database System Concepts, 3^rd ed. McGraw Hill, 1997.

ASSIGNMENTS & OTHER COURSE MATERIAL

Fall 2010
Fall 2010: Homeworks (Please be critical of the published solutions.)
HW4: ER Model and Relational Algebra (Due Date: January 5, 2011) solutions
HW3: ISAM, B and B+ trees, Searching Sorted Sequential Files (Due Date: December 15, 2010) solutions
HW2: (minor revision on Oct. 24) External sorting/merging (Due Date: Oct. 27, 2010) solutions
HW1: (minor revision on Oct. 11) Disk storage characteristics and Unsorted Sequential Files (Due Date: Oct. 18, 2010) solutions, solution to Q6.

Programming Projects (How to submit)
Project3, FAQ: DNS server simulation using linear hashing file structure (Due Date: January 3 9, 2011; 11:59 pm) The two highest grades of three projects will be used to determine your total project grade.
Project2 (Dec. 16 version) , FAQ: Linear hashing file structure (Due Date: December17 19, 2010; 11:59 pm) (Resubmission Due Date: January 8, 2011; 11:59 pm)
Project1 (updated) , FAQ, Test Case: Intersection of two sequential files (Due Date: November 10 12, 2010; 11:59 pm)

Fall 2010:
Quizzes
Quiz 6 : Relational Algebra (Dec. 27 & 28, 2010)
Quiz 4 : B+ trees (Dec. 2 & 3, 2010)
Quiz 3 : Dynamic hashing (linear hashing, extendible hashing) (Oct. 25 - Nov. 1, 2010)
Quiz 2 : External sorting (heap sort, replacement selection sort, p-way merge) (Oct. 18 - Oct. 19, 2010)
Quiz 1 : Sequentail file processing (bucket vs. block concept), Disk concets (cylinder track, etc.) (Sep. 28 - Oct. 1, 2010)

Midterm (Nov. 6, 2010) questions/solutions

Fall 2010
Final (Jan. 7, 2011) Question 8 solution
Final exam study guide
Midterm study guide

Fall 2009
Final exam study guide

Fall 2009: Homeworks (Solutions are by your classmates, please be critical of their solutions, typos and mistakes -if any- may have been left for your correction.)
HW5: ER (E/R) Model, Relational Model, Relational Algebra (Due Date: Dec. 29, 2009), solutions
HW4: B-trees and B+ trees (Due Date: Dec. 4, 2009), solutions
HW3: Sorting, merging, static hashing, linear hashing, extendible hashing (Due Date: Nov. 5, 2009) solutions, alternative solutions
HW2: Sequential file processing, sorting (Due Date: Oct. 16, 2009)solutions, alternative solutions
HW1: Disk tape storage characteristics (Due Date: Oct. 6, 2009) solutions

Programming Projects (How to submit)
Project3 (pdf, docx, Records.txt): Replacement selection sort (Due Date: Dec. 24, 2009; 23:59)
Project2(pdf, docx): Static hashing file transaction processing (Due Date: Nov. 16, 2009; 23:59, Nov. 23, 2009; 23:59, Dec. 2, 2009; 23:59), Deletion example
Project2 Files (all txt): Transactions, Students, Overflow, HashFile
Project1: Static hashing file creation, FAQ (Frequently Asked Questions) , sample input file (Due Date: Oct. 26, 2009; 23:59) <== new due date

Fall 2009:
Quizzes
Quiz 1: Sec.1-3 : Sequential file processing: Tf, Ty, Tcopy etc.(Sep. 28-Oct. 2, 2009)

Midterm (Nov. 7, 2009) questions/solutions

Course Material From Previous Years   

• Handouts
       Midterm exam study guide
       Midterm exam with solutions (October 27, 2005)
       Final exam study guide (posted on December 16, 2005)
       Final exam with solutions
  
  
• Sample Quizzes (due to Pelin Angin)
      Quiz1 (tape drives)
      Quiz2 (sorted files)
      Quiz3 (B+ trees)
      Quiz4 (k-d trees)
      Quiz4' (attribute selectivity)