Courses

CS 342: Data Structures and Algorithms

Objective	To provide a basic understanding of fundamental algorithms and data structures, including several small programming assignments in the programming language as used in CS127b/CS227.
Pre-Conditions	[CS127b/CS227] Facility with medium-size programs (~ 100 - 200 lines) [CS127b/CS227] Recursion [CS127b/CS227] Pointers [CS127b/CS227] Passing parameters by value and by reference [CS127b/CS227] Basic data structures: multidimensional arrays, linked-lists, trees [Algebra1] Mathematical maturity, especially with functions like: y=log(n), y=exp(n), y=a^n, and others.
Post-Conditions (Topics)	[1 week] Introduction: Big O, sorting (review selection, insertion, bubble, quicksort, mergesort; introduce radix) [CS433] [CS445] [CS460] [1 week] Lists: stacks, queues, doubly-linked, sets [CS422] [CS433] [CS445] [1 week] Priority Queues: heaps, heapsort [CS433] [CS445] [2-3 weeks] Trees: review binary, balanced (e.g. AVL, 2-3, red-black) [CS422] [CS433] [CS445] [1 week] Hashing: dictionaries, radix search, hash functions, buckets, linear probing, double hashing [CS433] [CS445] [CS460] [3 weeks] Graphs: representation, directed graphs, DFS, BFS, connectivity, cycles, shortest path, spanning trees [CS422] [CS433] [CS445] [1 week] String searching [1 week] Parsing [CS453] [1 week] Compression [1 week] Optional Topics
Optional Topics (Examples)	Trees: threaded trees Graphs: transitive closure Geometric algorithms: convex hull, line intersection, interval ranges Math algorithms: pseudo-random number generation, large integers, integration, Gaussian elimination, polynomials, curve fitting

Last revised on 27 February 1997 by John Hartman