CMU 15-112: Fundamentals of Programming and Computer Science
Collab 10 (Due Friday 6-Nov in your assigned recitation)

1. Discuss Linear Search and Binary Search
   Discuss linear search and binary search from here.


2. Review Efficiency lecture notes
   Review the notes from the Efficiency lecture. In particular, be sure you understand:
   1. What (approximately) 2¹⁰, 2²⁰, and 2³⁰ equal.
   2. What approximately log₂(1 thousand), log₂(1 million), and log₂(1 billion) equal.
   3. The fact that logn is much, much smaller than n.
   4. Why we ignore lower-order terms and constants in Big-O.
   5. Why we ignore the base in logs in Big-O.
   6. How selectionSort and mergeSort work.
   7. The proof that selectionSort is O(n²).
   8. The proof that, for selectionSort (or any quadratic algorithm), when you multiply the input size by c, you multiply the runtime by c².
   9. The proof that mergeSort is O(nlogn).
   10. The fact that, for mergeSort (or any nlogn algorithm), when you multiply the input size by c, you multiply the runtime by a value slightly larger than c but quite a bit smaller than c².
   11. The fact that O(nlogn) is theoretically optimal for any comparison-based sort, and consequently that mergeSort is within a constant time as fast as any possible comparison-based sort.


3. Review xSortLab
   Run xSortLab, and...
   1. For each of selectionSort and mergeSort:
      1. Do a visual sort and predict each step before confirming it visually. Do this for several steps. In particular, if shown a picture of a given sort at any stage, be sure to be able to answer which two values are the next to be compared, and which values are the next to be swapped (for selectionSort) or copied (for mergeSort).
      2. Be able to explain what constitutes one "pass" for each of these sorts.
   2. Do a timed sort of selectionSort, and confirm that doubling the input size increases the runtime by about 4x, and that this prediction grows more accurate as the input size increases.
   3. Do a timed sort of mergeSort, and confirm that doubling the input size increases the runtime by more than 2x, but just barely, and well under 4x, and that this prediction grows more accurate as the input size increases.


4. Short Answers
   
   1. For each of these functions, note the closest family it belongs to (big O notation).

      A. T = 2N + 5
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      B. T = N + logN
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      C. T = N**3 + 45N**2 + 100logN
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      D. T = 10N * 3N
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      E. T = 10N + 3N
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      F. T = number of steps merge sort takes to sort a list of N numbers
          O(logN)     O(N)     O(NlogN)     O(N**2)     O(N**3)
      

   
   
   2. Briefly describe how a hashtable works for a set, and in particular explain why checking if a value is in a set is O(1).
   
   
   3. Answer the following questions.
      Wherever it is relevant, assume that all the functions run in one of O(1), O(logN), O(N), O(NlogN), O(N**2), O(N**3), or O(2**N).
      1. Your code takes 5 seconds to run on an input of length 1000. How long does your code take to run on an input of length 3000 if it runs in O(n**2)?
      2. Your code takes 5 seconds to run on an input of length 1000 and 10 seconds to run on an input of length 2000. What is the most likely big oh?
      3. Your code takes 5 seconds to run on an input of length 1000 and 11 seconds to run on an input of length 2000. What is the most likely big oh?
      4. Your code takes 5 seconds to run on an input of length 1000 and 40 seconds to run on an input of length 2000. What is the most likely big oh?
      5. Which grows faster, log(N) or N**0.5 (square root of N)?
      6. SubsetSum(L) is a famous problem where we try to find some values in L such that they sum to zero. The naive solution to subsetSum runs in O(2**N) time. That is, exponential time. This is awful. To see how awful, if your code takes 1 second to solve subsetSum on an input of size 10, how many years would it take to solve subsetSum on an input of size 50 (yes, just 50)?
   
   
5. Rewrite (from scratch, without notes) Selection and Merge Sort
   Note: in recitation, you will all just discuss the implementations of selectionSort and mergeSort from the notes here. Sometime soon after recitation, though, students are all expected to finish this task, and to rewrite the code from scratch for both of these sorts. You are responsible for all the code in that file, including selectionSort, mergeSort (and merge), and the timing and testing code. Be sure to study our implementations, and not others online (and be sure not to use recursion!). You need to know this code very well by the upcoming quiz!