TOWSON STATE UNIVERSITY
DEPARTMENT OF COMPUTER AND INFORMATION SCIENCES

COSC 600: ADVANCED FILE AND DATA STRUCTURES

Professor Ali Behforooz


Office:                 316L Stephens Hall
Phone:                  410-830-3035
Fax:                    410-830-3868
E-mail:                 alib@midget.towson.edu
                        behforooz-a@toe.iowson.edu

Table of Contents

Course Description:

Topics covered in the course includes: data abstraction, a survey of linear data structures, nonlinear data structures, file organization and access methods, memory management, a discussion of more advanced internal and external sort a nd search algorithms, and the trade-offs involved in the use of different data organizations. The emphasis will be on algorithm analysis and trade-offs study.

Course Objectives:

Upon completion of this course students should be able to fully understand and apply the following concepts in their computing related work environment.

  1. Data abstraction and information hiding.

  2. linear data structures and their applications in problem solving and programming.

  3. Nonlinear data structures and their applications in problem solving and programming.

  4. Different file organizations and their applications in system development and databases.

  5. Internal and external sort and search techniques.

Required Textbook:

Horowitz and Sahni, Fundamental of Data Structures, 4th Ed., CSP, 1994, (Pascal, C , C++ or Generic version)

Recommended Textbook:

Alan L. Tharp, File Organization and Processing, Wiley, 1988.

Suggested References:

  1. Rick Decker, Data Structures, Prentice-Hall, 1989.

  2. Nancy E. Miller, File Structures Using Pascal, Benjamin Cummings, 1988.

  3. Aho, Hopcroft, Ullman, Data Structures and Algorithms, Addison Wesley, 1983.

  4. T. A. Standish, Data Structure and Techniques, Addison Wesley, 1980.

  5. R. G. Claybrook, File Management Techniques, Wiley, 1983.

  6. R. L. Kruse, Data Structures and Program Design, 3rd ed., Prentice-Hall, 1994.

  7. Oven Hanson, Design of Computer Data Files, 2nd edition, CPS, 1988.

  8. T. A. Standish, Data Stuctures, Algorithms, and Software Principles, Eddison-Wesley, 1994.

  9. Mark Allen Weiss, Data Structures and Algorithm Analysis, Benjamin Cummings, 1993 ( Pascal, C, C++ and Ada versions)

  10. H. R. Lewis and L. Denenberg, Data Structures and their Algorithms, Harper Collins Publisher,1991.

  11. T. H. Cromen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill Book Company, 1992.

  12. Mary E. S. Loomis, Data Management and File Structures, 2nd ed., Prentice-Hall, 1989.

  13. Clifford A. Shaffer, A practical Introduction to Data Structures and Algorithm Analysis, Prentice-Hall, 1997.

  14. Kruse, Tondo and Leung, Data Structurs and Program Design in C, 2nd edition, Prentice-Hall, 1997.

Major Topics Covered in the Course:

  1. Data Abstraction and Algorithm Analysis ( 2 weeks)

    • Data types/objects/structures
    • Abstract definition of data structures
    • Representation and implementation
    • Time requirements of algorithms
    • Space requirements of algorithms

  2. Review of Linear Data Structures ( 3 week)
    • Array application and representation
      • Polynomials
      • Sparse matrices
      • String-pattern Matching
    • Stack and Queues
      • Needs and justification of the study of the structures
      • Representation and implementation
    • Multiple stacks and queues
    • Implementation of recursion using stack
    • Linked Lists
      • Needs for the structure and justification of the study
      • Representation and Implementation
      • Doubly linked list
      • Circular linked list
    • Linked list application
      • Memory Management
        • Static memory management
        • Dynamic memory management

  3. Nonlinear Data Structures ( 3 weeks)
    • Trees
      • Definitions, terminologies and properties
      • Binary tree representation ,traversals and applications
      • Threaded binary trees
      • Binary Search Trees
      • AVL Trees
      • M-way Search Trees
      • B-trees, B*-trees, B+-trees
      • Optimum binary search trees
      • Multidimensional binary search trees
    • Graphs
      • Definition, terminologies and properties
      • Graph representations
      • Minimum spanning trees
      • Depth-first search
      • Breadth-first search
      • Networks
    • Priority Queues
      • Heap Structures
      • Binomial Heaps
      • Leftist Heaps

  4. Sort and Search Algorithms (2 weeks)
    • Heap sort
    • Merge sort
    • Quick-sort
    • Hashing
    • General radix sort
    • Symbol tables
    • Sequential search
    • Binary search
    • Interpolation search
    • Tries

  5. File organization and processing (4 weeks)
    • Sequential files:
      • Organization, creation, update and maintenance
    • Relative files: Organization
    • Hashing techniques
      • Approaches to collision problem
      • Creation, retrieval and update
    • Indexed sequential files:
      • Organization , creation, update and maintenance
    • Multi-key files
      • Inverted file
      • Multi-list file
      • Alternate key
    • Tree structured files
      • B-trees
      • AVL-trees
      • Tries

Requirements:

Four programming assignments 100 points
Midterm Exam 75 points
Comprehensive Final Exam 75 points
Homework problems (5 sets)50 points

Grading Policy:

Let us assume X is the highest score achieved in this course and T is your total score. Compute Z = Max((X+300)/2, 270). Your grade is: 

		A  	if   0.9 * Z < T <= 1.0 * Z
		B  	if   0.8 * Z < T <= 0.9 * Z
		C  	if   0.7 * Z < T <= 0.8 * Z
		F  	if   0.0 * Z < T <= 0.7 * Z
There may be other adjustment on the grading scheme when the course is completed. However, the above formula should give you a good estimate of your grade in this course.

IMPORTANT NOTES

  1. Programs are due at the beginning of the class period.

  2. Late programs worth 10% less per week.

  3. Midterm exam will be a take-home exam.

  4. Final exam is given the last day of class and is open book and notes.

Copyright © Prof. Ali Behforooz