ICS4U-Test Review-Recursion & Sort

Test #3

1. Recursion
   • What are the three criteria for a problem to have a recursive solution?
   • Give two benefits and two problems with using recursion.
   • Trace through a limited recursive routine.
   • Definitions :iterative solution, base case, depth of recursion, preconditions
   • Chapter 11, exercises 11.3 #2-3, 11.4 #1(a), 2, 3, 5-9
   • Chapter 70, 72 on-line quizzes
2. Searching and Sorting Theory
   • What are the four factors that affect sorting routines?
   • What does Big-O notation mean? Give an example.
   • Compare the efficiencies of o(n2) and O(n log n) algorithms
   • What is the basic algorithm for the merge sort? quick sort?
   • If you were given the code for either, would you recognize it?
   • How do worst case times compare?
   • Given a scenario, what type of sort would you use.
   • Binary Search - recursive version