CS421 - Advanced Data Structures and Algorithm Development Spring 1999 Test 2 Study Guide

Test Format (You may bring in one index card with notes but no books)
Matching (2 pts each)
Short Answer Questions and Problems

Study Material

1. Chapter 2 - Searching
   • Define upper bound, lower bound, worst cost, average cost, instance, optimal, aymptotically optimal, probabilistic algorithm, randomized algorithm, greedy strategy, balance strategy, simplicity strategy
   • Know formulas for worst cost, average cost, worst cost lower bound, average cost lower bound, expected cost, worst expected cost, average expected cost (pp. 139-140)
   • Be able to look at code fragments and find its worst cost (Appendix B)
   • Know worst & average costs of Linear, Jump, and Binary Searchs in terms of recurrence relations and their corresponding closed form solution
   • Be able to trace Linear, Jump, and Binary Searchs and determine the number of comparisons
2. Chapter 3 - Selecting
   • Define selection, median, asymmetry, transitivity, partial order, linear order, poset, binomial tree, randomizing algorithms
   • Be able to trace Algorithms 3.2, 3.3, 3.4 and be able to determine the number of comparisons
   • Be able to trace algorithm 3.5 and determine the number of comparisons
   • Be able to trace Split (algorithm 3.7) and dtermine the number of comparisons
   • Understand and be able to trace SELECT (algorithm 3.9) and determine the number of comparisons
   • Be able to determine the median of medians