CISC 220: Data Structures

Catalog Description:
Review of data type abstraction, recursion, arrays, stacks, queues, multiple stacks, and linked lists. Emphasis on trees, graphs, tables, sorting and searching.

Current Texts:
Data Structures: A Pseudocode Approch with C++
Richard Gilber and Behrouz Forouzan
Brooks/Cole 2001

Goals:
Thorough understanding of the basic data representation techniques and standard algorithms for manipulating those representations. Understanding of the functionality and efficiency considerations that dictate the selection of representation in a specific application. Proficiency in writing C++ programs which implement and use stacks, queues, lists, hash tables, trees, and graphs (using both static and dynamic storage allocation). Familiarity with a variety of searching and sorting techniques.

Content:
Using problem sets and individual programming assignments in C++, covers the following key topics:

• asymptotic analysis (average, worst case)
• storage management-- free lists
• binary trees-- contiguous, linked, child-sibling
• binary search trees, tree traversal, AVL trees
• depth and breadth first search
• chained, perfect hashing
• priority queues-- heapsort
• sorting -- insertion, quicksort, merge, radix, shellsort, lower bound for comparison based sorting
• graph representation, elementary graph

Prerequisites: A minimumm grade of C- in CISC 181 or CISC 120 .

Corequisites: MATH 210 (Discrete Mathematics) or MATH 242 (Analytic Geometry and Calculus B).