CMU 15-112: Fundamentals of Programming and Computer Science
Check7 Practice
Due in Autolab by 10:30am Tue 11-Oct

• You must work collaboratively (no solo!) in groups of 3-6 students
• There are no lecture-topic videos to watch this week, instead you must actually attend lecture! If you did not attend lecture (according to our attendance records) on Thu 6-Oct, then you need to attend one of the make-up lectures that we will also provide. We will post those lecture days, times, and locations on piazza.

1. Week6 time report and brief reflection
   First, fill out this week6 time report and brief reflection. Thanks!


2. Review Thursday lecture notes
   As a group, review and discuss the notes from Thursday's lecture. In particular, be sure you understand:
   1. What (approximately) 2¹⁰, 2²⁰, and 2³⁰ equal.
   2. What approximately log₂1k, log₂1m, log₂1b 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, bubbleSort, 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.
   12. These class notes on sorting (in detail!) -- just the sorting section. Be sure to really read these notes, including for example watching the videos of the sorting animations.


3. Review xSortLab
   Still as a group, install xSortLab (see link in course notes mentioned above), and run it, and...
   1. Do a visual sort of bubbleSort, and predict each step before confirming it visually.
   2. Do a visual sort of selectionSort, and predict each step before confirming it visually.
   3. Do a visual sort of mergeSort, and predict each step before confirming it visually.
   4. 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.
   5. 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. Rewrite (from scratch, ultimately without notes) sorting.py
   Still as a group, rewrite the code from scratch from sorting.py as we covered in class and as written here. You are responsible for all the code in that file, including bubbleSort, 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 Tuesday's lecture!


5. What to Submit
   We recommend you finish by Monday night though the deadline is 10:30am Tuesday (for everyone, regardless of which lecture you are in, with no late submissions and no grace days):
   • Submit check7.py, a Python file that contains your sorting code as you wrote it (definitely do not just copy-paste the code from the course website! write it yourself, even if it is extremely similar to ours.)
   • At the top of check7.py, also include:
     1. Your name and andrew id.
     2. The names and andrew id's of everyone you collaborated with on check7.
     3. Confirmation that you attended lecture or a make-up lecture (list which one, day/time/location/lecturer).
     4. Confirmation that your group studied the lecture materials and that you wrote the sorting code from scratch.