CS-244 Data Structures

Mathematics, Statistics & Computer Science Department

COURSE NO./TITLE: CS-244 DATA STRUCTURES (Previously CS-341 (354-341) DATA STRUCTURES)

CREDITS: 4

COURSE DESCRIPTION: Concepts and foundations of data structures and algorithms.
Introduction to analysis of algorithms, linear structures, vectors, linked lists, stacks, queues and
priority queues. Non-linear data structures such as trees, tree traversals, binary trees, binary
search trees and graphs. Advanced sorting and searching techniques. Hashing, heaps.

Prerequisites: CS-145

TEXTBOOK:

  • Data Structures with C++ Using STL, 2nd Ed. by Ford (adopted Fall 2003)
  • (Adopted F99: Data Structures, Algorithms & Applications in C++, 1st Ed., by Sahni)
  • (Adopted 8/95: Data Structures & Algorithm Analysis in C++, 1st Ed., by Weiss)
  • (Prior to Fall 95: Data Structures and Program Design in PASCAL, 2nd Ed., by Nyhoff)

COURSE OBJECTIVES: By completing the course, the student will be able to:

  1. Understand the structure, purposes and methods of the most commonly occurring data
    structures.
  2. Analyze the data structure needs of particular problems as well as the appropriate
    associated algorithms.
  3. Compare the efficiency of various implementations and algorithms, as well as the pros
    and cons of each implementation and algorithm.
  4. Recognize the mathematical aspects of discrete structures.
  5. To learn and apply object-oriented design principles for the purposes of data abstraction
    and encapsulation.
  6. Master the standard data structure library of a major programming language (e.g.
    standard template library in C++).
  7. Develop the ability to effectively implement collections and containers in modern
    software engineering applications.
  8. Be familiar with several sub-quadratic sorting algorithms including quick sort, merge sort
    and heap sort.
  9. Comprehend the theoretical aspects and practical applications of the non-linear structures
    and searching algorithms for these structures.

COURSE OUTLINE:

  1. Introduction to Data Structures
  2. Object Design Techniques and Methodology
  3. Review of Inheritance, Polymorphism and Abstract Classes
  4. Introduction to Algorithms
  5. Introduction to Containers, Iterators and Standard Library
  6. The Vector Container
  7. Dynamic Memory Management
  8. Stacks
  9. Queues and Priority Queues
  10. Singly, Doubly and Multiply Linked Lists
  11. Binary and Other Trees
  12. Search Trees
  13. Associative Containers (Sets, Maps, Multisets and Multimaps)
  14. Advanced Associative containers (Hash Tables and Hashing)
  15. Sorting and Searching Algorithms
  16. Heap Structures and Heap Algorithms
  17. Recursive Algorithms and Other Non-linear Structures

Revised 1/05