Bilkent University*
COMPUTER ENGINEERING DEPARTMENT

CS351: DATA ORGANIZATION and MANAGEMENT
Fall 2011
Section 1:        Mon.  10:40, 11:40, Thur.  08:40, 09:40; EB201  
Section 2:        Wed.  08:40, 9:40, Fri.  10:40, 11:40; EB201
Section 3:       Wed.  13:40, 14:40, Fri.    15:40, 16:40; EB201

Hours "not" underlined are reserved for possible makeups.

INSTRUCTOR

Dr. FAZLI CAN
Office: EA431, Phone: 290-2613
Office Hours: Wed. 10:40-11: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: EA501, Phone: 290-????
Office Hours: Wed. 10:40-11:30, and by appointment
E-mail: hayrettin at cs dot bilkent dot edu

BİLGE KÖROĞLU
Office: EA511, Phone: 290-1945
Office Hours: Fri. 13:40-14:30, and by appointment
E-mail: koroglu at cs dot bilkent dot edu

ÇAĞRI TORAMAN
Office: EA511, Phone: 290-1945
Office Hours: Fri. 14:40-15:30, and by appointment
E-mail: ctoraman 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.

Students will practice and apply data organization and processing techniques through programming projects.

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

COURSE SCHEDULE

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

Week No.: Day/Month Topic
1: 26/9

Course overview. Secondary storage media.
2: 3/10

Secondary storage media and their physical characteristics.  Sequential files.
3: 10/10

Sequential file organization: creation, access and update. Performance of sequential files operations.
4: 17/10

External sorting/merging algorithms.
5: 24/10

External sorting/merging algorithms. Static hashing, address calculation and collision handling.
6: 31/10

Static hashing, address calculation and collision handling. Dynamic hashing techniques.
7: 7/11

Kurban Bayramı Haftası - No Classes.
8: 14/11

Dynamic hashing techniques.
9: 21/11

Indexed sequential access method (ISAM). B-trees and B+ trees. Midterm EXAM: Nov. 26 Saturday (tentative).
10: 28/11

B+ trees.  Secondary key retrievals. Introduction to database management systems.
11: 5/12

Architecture, components, and facilities of a DBMS.  
12: 12/12

Data model principles. Entity relationship data model.
13: 19/12

Entity relationship data model. Relational model of data.
14: 26/12

Relational algebra.
15: 2/1

Relational algebra and relational calculus.

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, 3rd ed. McGraw Hill, 1997.

ASSIGNMENTS & OTHER COURSE MATERIAL

Fall 2011
Final exam study guide
Midterm study guide Midterm (Nov. 26, 2011) questions/solutions

Homeworks
HW5: ER Model, Relational Algebra. (Due Date: January 11, 2012)
HW4: Extendible hashing, B and B+ trees. (Due Date: January 4, 2012), solutions (solution to Q4 is updated)
HW3 (updated): Static hashing and linear hashing (Due Date: Nov. 14, 2011), solutions
HW2: Heap sort, replacement selection sort, merging (Due Date: Nov. 16, 2011), solutions (typo is corrected)
HW1: Disk storage characteristics and Unsorted Sequential Files (Due Date: Oct. 31, 2011), solutions

Programming Projects
Project3: External p-way merging
Project2: External sorting with heap sort with limited amount of memory
Project1: Union of two unsorted sequential files with limited memory space

Quizzes
Quiz 5 (Sec. 1-2-3): B+ tree (by Bilge Koroglu)
Quiz 4 (Sec. 1-2-3): Extendible hashing and linear hashing (by Hayrettin Erdem)
Quiz 3 (Sec. 1-2-3): Heap sort and linear hashing (by Cagri Toraman)
Quiz 2 (Sec. 1, Sec. 2, Sec. 3): Secondary Storage/Disk Medium (by Cagri Toraman)
Quiz 1: Database and DBMS - general concepts at the beginning of the course (by Bilge Koroglu)

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   

EXAM DATES

Final Exam : January 13, 2012 (12:15-14:15)
Exam Locations:
           EB101-For students: Acarlar -- Bellisoy           Proctor: Bilge Köroğlu
           EB102-For students: Bıçak -- Dikmen             Proctor: Bahaeddin Eravcı
           EB103-For students: Dinç -- Kalem                 Proctor: Berkan Ercan
           EB104-For students: Kandiş -- Mumcu           Proctor: Can Telkenaroğlu
           EB201-For students: Nazlım -- Şişman           Proctor: Çağrı Toraman
           EB202-For students: Terzi -- Yücel                 Proctor: Özge Uyanık
           Libero Proctor: Hayrettin Erdem
  
Midterm Exam : November 26, 2011 (13:40-15:30)
Exam Locations:
           EB101-For students: Acarlar -- Bellisoy          Proctor: Bilge Köroğlu
           EB102-For students: Bıçak -- Dikmen              Proctor: Berk Koçuroğlu
           EB103-For students: Dinç -- Kalem                 Proctor: Berkan Ercan
           EB104-For students: Kandiş -- Mumcu           Proctor: Cansın Yıldız
           EB201-For students: Nazlım -- Şişman            Proctor: Çağrı Toraman
           EB202-For students: Terzi -- Yücel                 Proctor: Mirun Akyüz
                                                                                  Libero Proctor: Hayrettin Erdem

GRADING POLICY

Midterm exam  25%
Final exam (comprehensive) 35%
Homeworks & Projects 25%
Quizzes  15%
---------------------------------
Total  100%

GENERAL POLICIES

  1. Your work (homeworks and project) should be turned in on due date, no late work will be accepted. 
  2. If individual review is needed due to a question on the grade this should be no later than one week after receiving your work or exam.  This time limit is for consistency in grading.
  3. Plagiarism is defined as the action of using or copying someone else's idea or work and pretending that you thought of it, or created it. Bilkent University requires that you be aware of the concept and dangers of plagiarism. In order to conform to international academic standards, you must respect the individual thoughts, ideas, and expressions of other authors in sources.

    In the homeworks and projects in this course, occurrences of plagiarism will be seriously dealt with, leading to a zero grade for the work concerned and upon repetition to a failure in the course, even to punishment through disciplinary procedures which call for a term or two terms of dispelling from the university. (Ogrenci Disiplin Ilke ve Kurallari, Madde 8).

    You may discuss and exchange ideas related to homework problems and the various aspects of the term project among yourselves, you may consult to relevant books and other forms of written material, but the final work must be your own, with references to the sources utilized.

OFFICE HOUR POLICIES

In case I am not able to be in my office during any office hour period, I will announce alternate hours to make up for them. Please do not assume that I am available to answer your questions any time you may barge into my office. During office hours, you are welcome to stop by and discuss your questions with me. If you cannot make it during my hours, you are further welcome to contact me and make an appointment for a more suitable time.

ANNOUNCEMENTS

  • HW4 solutions (solution to Q4 is updated). have been published. January 12, 2012 (7:06 pm)
  • Quiz 5 solutions. have been published. January 12, 2012 (7:06 pm)
    HW4 solutions have been published. Solutions are mostly due to Hilal Güler. January 10, 2012 (10:54 pm)
  • Final exam study guide January 10, 2012 (5:47 pm)
  • A book that may change your life: The Art of Doing Science and Engineering: Learning to Learn pdf (or "Luck favors the prepared mind.") by Richard W. Hamming. January 5, 2012 (1:51 am)
  • HW5: ER Model, Relational Algebra. January 4, 2012 (5:53 pm)
  • HW4: Extendible hashing, B and B+ trees has been published. December 24, 2011 (5:26 pm)
  • Writing papers with no effort random paper generator link has been published. December 23, 2011 (12:47 pm)
  • Project 3 external p-way merge has been published. December 23, 2011 (12:47 pm)
    Quiz 4 questions/solutions have been published. December 19, 2011 (6:37 pm)
  • Midterm (Nov. 26, 2011) questions/solutions published. December 11, 2011 (11:50 pm)
  • Project2: External sorting with heap sort with limited amount of memory has been published. December 4, 2011 (9:18 pm)
    Quiz 3 solutions     have been published. December 3, 2011 (11:46 pm).
  • HW3 solutions have been published. Solutions are due to Sefa Şahin Koç (Övünç Sezer's solutions are used for double checking). November 25, 2011 (5:59 pm).
  • HW2 solutions (updated version) have been published November 24, 2011 (5:44 pm).
  • HW2 solutions have been published. Solutions are due to Övünç Sezer and Sefa Şahin Koç. November 24, 2011 (2:47 pm).
  • Midterm study guide has been published (11:35 pm).
  • HW3 has been published. November 20, 2011 (4:49 pm).
  • HW1 solutions (due to Övünç Sezer) have been published. November, 19, 2011 (8:06 pm).
  • HW2 has been published. October 30, 2011 (11:21 pm).
  • HW1 has been published. October 19, 2011 (10:29 pm).
  • Class pictures are up. October 15, 2011 (8:37 am).
  • October 11, 2011:course syllabus
  • October 11, 2011: Follow the links to find the flow concept of Mihaly Csikszentmihalyi in programming, and future of disk drives
  • October 11, 2011: boring class video

Date/time of last update: January 12, 2012; 7:06 pm

Send comments to the author: canf@cs.bilkent.edu.tr

* The announcements section may change every day throughout the semester. There can be some errors on this page and I keep the right of making corrections without any notice.