UNIVERSITY of HYDERABAD
DEPARTMENT OF COMPUTER AND INFORMATION SCIENCES

DATA STRUCTURES

Dr. Atul Negi


Office:      Room NumberE-221,   East Wing First Floor AI LAB
Phone:       23134031         
E-mail:                 atulcs@dcis.uohyd.ernet.in
                        atulcs@uohyd.ernet.in

Table of Contents

Course Description:

Topics covered in the course includes: data abstraction, a survey of linear data structures, nonlinear data structures, a discussion of more advanced internal and external sort and search algorithms, and the trade-offs involved in the use of different data organizations. The algorithm analysis and trade-offs study shall be done. Implementations and their efficiency in either C or C++ shall be considered in the Lab.

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. Internal and external sort and search techniques.

Textbooks:

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

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

Suggested References:

  1. Knuth, D. E. The Art of Computer Programming, Vol. I & III, Addison-Wesley, 1974. These books must be read by any serious student of computer science.

  2. Carrano, F. M., Data Abstraction and Problem Solving with C++, Benjamin Cummings, 1995.

  3. Horowitz, E., Sahni, S. and Mehta, D., Fundamentals of Data Structures in C++, W.H. Freeman, 1995.

  4. Standish, T. A., Data Structures, Algorithms and Software Principles in C, Addison-Wesley, 1995.

  5. Tenenbaum, A. M. , Langsam, Augenstein, M. J., Data Structures Using C++, Prentice Hall, 1996.

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

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

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

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

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

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

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

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

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

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

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

  17. Kruse, Tondo and Leung, Data Structures 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

Requirements:

Minor Exams
Comprehensive Final Exam
Programming Assignment problems (5 sets)

Copyleft © Atul Negi