CIS 350 Review Fall 2000 Text: Horowitz 1.1-2.2,2.5-4.7.4.9-5.7,6.1-6.4, 5.1-9.1,10.1-10.4,10.9 Abstract Data Types in C++ attributes, operations, declarations, type checking, implementation Recursion data structures, algorithms and simulation Dynamic Data Structures attributes, implementation, operations, applications, stacks, queues, linked lists (singly linked, doubly linked, circular), header nodes, binary trees (threading, balancing, traversals), general trees, partially ordered trees (heaps), tries, B-trees, priority queues, directed graphs (shortest path, traversals), undirected graphs (minimum cost spanning trees, traversals, matching) Searching Algorithms sequential, binary, indexed, hash coding and collision handling Sorting Algorithms insertion, selection, bubble, heap, quick, shell, radix, merge, bin, topological Algorithm Analysis efficiency, big Oh notation, order arithmetic, worst case comparisons and methods of improving performance, solving recurrence relations Algorithm Design divide-and-conquer, dynamic programming, greedy algorithms Programming Expect to write 2 or 3 procedures/functions, and to trace several (including internal representations of data structures) Object-oriented Programming As an alternative means of implementing ADT's.