CISC-235/3.0 Data Structures

Original Authors: Mary McCollam and David Rappaport
Last Revised: October 15, 2009

Calendar Description

Design and implementation of advanced data structures and related algorithms, including correctness and complexity analysis. Efficient implementation of lists, sets, dictionaries, priority queues, trees, graphs, and networks using arrays, hash tables, heaps, and hierarchical linked structures. String and graph problems, such as string matching and shortest path. External storage and input-output complexity.

Prerequisites: CISC 124/3.0, CISC 203/3.0
Learning Hours 120 (36L;84P)


This course is designed to teach students about ways that data can be structured and about algorithms for accessing and updating these structures efficiently.

After completing the course, students will have a toolkit of data structures and algorithms that they can select from and implement when solving programming problems and developing software, and they should know how to analyze problems in order to judge which of these are most efficient and appropriate for use in a particular situation. They should also be able to develop their own variations and combinations of data structures to fit new situations and be able to analyse their efficiency and usefulness.

Assignments will require implementation of data structures and related algorithms; the instructor should specify whether Java or Python (or either) is to be used for these implementations (starting in 2009).

The courses to which this course is a direct prerequisite are:

  • CISC-322/3.0 (Software Architecture)
  • CISC-324/3.0 (Operating Systems)
  • CISC-325/3.0 (Human-Computer Interaction)
  • CISC-352/3.0 (Artificial Intelligence)
  • CISC-365/3.0 (Algorithms I)
  • CISC-432/3.0 (Advanced Database Systems)
  • CISC-454/3.0 (Computer Graphics)

This course is required in all Computing programs.


Complexity Analysis

  • Identities for logs and exponents
  • Evaluating sums and recurrences
  • Asymptotic notation
  • Basic probabilistic analysis
Review of Basic Data Structures and Recursion
  • Arrays, lists, stacks, queues, linked structures
  • Recursive algorithms
  • General trees, binary trees
  • Binary search trees
  • Balanced binary search trees, such as AVL, (2,4), red-black, AA, skip-list
Priority Queues
  • Heap implementation
  • Insert, Delete, Bottom-up Heap construction
  • Heap-sort
  • Unordered and ordered dictionaries
  • Hash table implementation
  • Basic hash functions
  • Collision resolution
  • Load factors
External Searching and Sorting
  • (a,b) and B-Trees
  • Multi-way merge sort
  • Input/output complexity
Text Processing
  • Pattern matching
  • Tries
  • Simple graphs, directed graphs, weighted graphs
  • Graph representation (edge list, adjacency list, adjacency matrix)
  • Graph traversals
  • Shortest paths and other graph problems, such as minimum spanning trees
Possible Text Books
  • Adam Drozdek: Data Structures and Algorithms in C++, 3rd edition, Thomson Course Technology (2004).

  • Mark Allen Weiss: Data Structures and Algorithm Analysis in C++, 2nd edition, Addison Wesley (1998).

  • Michael T. Goodrich, Roberto Tamassia, and David M. Mount: Data Structures and Algorithms in C++, Wiley (2004).