Bilkent University*
COMPUTER ENGINEERING DEPARTMENT

CS351: DATA ORGANIZATION and MANAGEMENT

Fall 2009
Section 1  (F. Can):        Mon.  10:40, 11:40, Thur.  08:40, 09:40; EB101  
Section 2  (F. Can):        Mon.  15:40, 16:40, Thur.  13:40, 14:40; EB101
Section 3  (F. Can):        Wed.  08:40, 09:40, Fri.    10:40, 11:40; EB204
Section 4 (E. Arkun):      Tue.   10:40, 11:40, Fri.     08:40, 09:40; EB203

INSTRUCTORS:

Dr. EROL ARKUN
Office:  EA G 10, Phone: 290-2748
Office Hours: Wed 10:40-11:30 and Fri. 10:40-11:30 or by appointment
E-mail: arkun at bilkent dot edu dot tr

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


Assistants: email address
CEM AKSOY: caksoy at cs dot bilkent dot edu dot tr
ANIL TÜREL: aturel at bilkent dot edu dot tr
AHMET YENİÇAĞ: yenicag at cs dot bilkent dot edu dot tr
Office:  EA231, Phone: not working (will be fixed)
Office Hours: Friday & Monday 9:40-11:30

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, K-d tress and Grid files for multidimensional retrievals.
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.

Week No. Topic
1

Overview. Secondary storage media and their physical characteristics.

2

Sequential file organization: creation, access and update.
Performance of sequential files operations.

3

External sorting/merging algorithms.

4

Direct file organization techniques.
Static hashing, address calculation and collision handling.

5

Dynamic hashing techniques: Extendible and Linear hashing techniques and their performance.

6

Indexed sequential file organization techniques.

7

B-trees and B+ trees: structure, organization, use and performance.

8

Secondary key retrievals. K-d trees and Grid files.
Midterm EXAM: Nov. 03, Tuesday
9

Introduction to database management systems.
Architecture, components and facilities of a DBMS.

10

Data Models. Data model classification.

11

Entity relationship data model. Entity-Relationship Data Model

12

Relational model of data.

13

Relational algebra.

14

Tuple and domain relational calculi.

15

Final EXAM: January 6, 2010; Wednesday.

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

Final exam study guide
Midterm 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

Midterm Exam : November 7, 2009; Saturday, 13:15
EB101: Ağaoğlu - Başeşme
EB102: Battal - Energin
EB103: Eraslan - Karakuzu
EB104: Kartal - Öz
EB201: Özçelik - Şahin
EB202: Şener - Zorer

Final exam (comprehensive)  : January 4, 2010; Monday, January 6, 2010; Wednesday , 12:15 (EB-101, 102, 103, 104, 201, 202)

GRADING POLICY

Midterm exam  20%
Final exam (comprehensive) 35%
Projects (comprehensive) 15%
Homeworks 15%
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

  • Solutions to hw4 & hw5 are available. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Solutions are by your classmates, please be critical of their solutions, typos and mistakes -if any- may have been left for your correction.) (Announcement Time: January 3, 2010; 3:12 am.)
  • Final exam study guide has been published . See ASSIGNMENTS & OTHER COURSE MATERIAL. (Announcement Time: December 31, 2009; 1:14 am.)
  • Programming Project 3: You can submit your assignment on December 25, 2009 (by 23:59); however the penalty of being one day late is 15 points. (Announcement Time: December 24, 2009; 4:10 pm.)
  • Class hours for this week (Dec. 21 - Dec. 25) all 4 hours (Announcement Time: Dec. 21, 2009; 3:30 pm.)
    Sec. 1: Monday 10:40-12:30, Thursday 8:40-10:30, EB101 (on Thursday extra hour at 8:40)
    Sec. 2: Monday 15:40-17:30, Thursday 13:40-15:30, EB101 (on Thursday extra hour at 14:40)
    Sec. 3: Wednesday 8:40-10:30, Friday 10:40-12:30, EB204     (on Wednesday extra hour at 8:40)
  • HW5 has been published (due date: Dec. 29, 2009): See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: December 18, 2009; 1:15 am.)
  • You can see your graded midterm papers on the following days (in office no. EA231)
    Dec. 14, Monday 10:30-11.30
    Dec. 15, Tuesday 13.40-14.40
    Dec. 6 Wednesday 13.40-14.30. (Announcement Time: Dec. 12, 2009; 1:48 pm.)
    •
  • Midterm questions and solutions have been posted. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: Dec. 10, 2009; 5:52 pm.)
    •
  • The 3rd programming assignment has been updated (minor updates). (Announcement Time: Dec. 7, 2009; 7:09 pm.)
    •
  • The 3rd programming assignment files have been published. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: Dec. 4, 2009; 8:20 am.)
    •
  • Deletion example for programming project no. 2 has been published. Announcement Time: Nov. 26, 2009; 8:21 am
  • The Final Exam date has been changed, new date time (place): January 6, 2010; Wednesday 12:15 pm (EB-101, 102, 103, 104, 201, 202). Announcement Time: Nov. 21, 2009; 1:57 am.
    •
  • Please see the new due date for the 2nd programming assignment, also see the new hw above. Announcement Time: Nov. 18, 2009; 8:50 am.)
  • The 2nd programming assignment new due date: Nov. 23, 2009; Monday, 23:59. (Announcement Time: Nov. 7, 2009; 1:38 am.)
  • The 2nd programming assignment files (Transactions, Students, Overflow, HashFile) have been published. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: Nov. 7, 2009; 1:29 am.)
    •
  • Solutions to hw3 are available. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Solutions are by your classmates, please be critical of their solutions, typos and mistakes -if any- may have been left for your correction.) (Announcement Time: Nov. 3, 2009; 3:59 pm.)
    •
  • Midterm study guide has been published . See ASSIGNMENTS & OTHER COURSE MATERIAL. (Announcement Time: Nov. 6, 2009; 10:33 am.)
    •
  • Solutions to hw1 & hw2 are available. See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Solutions are by your classmates, please be critical of their solutions, typos and mistakes -if any- may have been left for your correction.)
    (Announcement Time: Nov. 3, 2009; 3:34 am)
    •
  • You can see your graded homework & quiz papers on the following time slots:
    Nov. 3, 2009 Tuesday: 1:40-2:30 pm
    Nov. 3, 2009 Wednesday: 1:40-2:30 pm, at EA231.
    (Announcement Time: Nov. 3, 2009; 2:58 am)
    •
  • Learn your midterm place: See EXAM DATES above (Announcement Time: Nov. 2, 2009; 11:18 pm.)
  • The 2nd programming assignment has been published: See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: Nov. 2, 2009; ~ 7:30 pm.)
    •
  • See the modified version of HW3 (question no. 5): See ASSIGNMENTS & OTHER COURSE MATERIAL above. (Announcement Time: Nov. 2, 2009; ~ 7:30 pm.)
  • September 24 , '09: boring class video

Date/time of last update: January 3, 2010

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.