CS 3240 DATA STRUCTURES AND ALGORITHMS (4) 2005

Catalog Description:

Definition, design, implementation of abstract data structures, including stacks, queues, generalized lists; implementation of contiguous or linked structures. Structures include tables and hashing, trees, graphs. Algorithms for manipulating structures, searching, sorting; introduction to the analysis of these algorithms. Prerequisite: Math 2150, CS 2360, CS 2430

Abstract data types (ADT)

Lists:
insertion/deletion of nodes, ordered lists, header nodes cursor lists, cover if desired

Stacks: postfix expressions

Queues: circular queues

Trees:
general trees, binary trees, binary search trees recursive traversals (preorder, inorder, postorder) expression trees B-trees, cover if desired AVL trees, cover if desired breadth-first search using queues, cover if desired

Priority Queues: min/max heaps

Hashing:
open, closed, rehashing, linear and quadratic probing

Searching: binary search

Sorting:
bubblesort, heapsort, quicksort, mergesort

Graphs:
simple introduction, cover if time

Analysis: simple analysis of average and worst-case Big-Oh

Implementation Issues:

• array-based and pointer-based structures
• recursion, pointers, debugging, memory management, (advanced) object
• oriented techniques.

Texts:

• Weiss: Data Structures & Algorithm Analysis
• Horowitz, Sahni, Mehta: Fundamentals of Data Structures
• Aho, Hopcroft, Ullman: Data Structutes and Algorithms
• Thomas Standish, Data Structures, Algorithms & Software Principles in C
• Shaffer, Practical Intro. to Data Structures & Algor. Analysis C++,
• Prentice Hall
• Dale, C++ Plus Data Structures, Jones & Bartlett