**Assignment 02: Divide and Conquer, the Master Method, and Randomness** *Due Thu Feb 18 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Determine the running time of an algorithm using the Master Method. - Determine the running time of an algorithm using recursion trees. - Compute the expected value of a variable by analyzing code. - Implement Quicksort in Python and consider performance characteristics. # Overview This assignment includes two parts: 1. Answer the [question in this PDF](resources/recursion-quicksort.pdf). 2. Code the Quicksort algorithm in Python (must be compatible with Python 3.8). You may work on this assignment alone or with a partner. Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit a both parts to [gradescope](https://www.gradescope.com/). Three key points: 1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade), 2. ensure that the uploading partner adds the other partners after submission, and 3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**. # Example Execution I always like to start by showing you the end result. If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/359040 **You can copy and past from the above animation!** # Input File Format Here is an example input file: ~~~text 10 5 3 8 6 7 4 9 2 1 10 ~~~ **The first line in the input file denotes the size of the input** (the number of things to sort). The remaining lines contain the elements that you will be sorting. Here are the files you will need to fill out the table in the PDF ([all files zipped together](resources/test-files.zip target="_blank")): - [ordered-10.txt](resources/ordered-10.txt target="_blank") - [ordered-100.txt](resources/ordered-100.txt target="_blank") - [ordered-10000.txt](resources/ordered-10000.txt target="_blank") - [randomized-10.txt](resources/randomized-10.txt target="_blank") - [randomized-100.txt](resources/randomized-100.txt target="_blank") - [randomized-10000.txt](resources/randomized-10000.txt target="_blank") # Main Your program will take two program arguments: (1) a filename and (2) a string denoting the Quicksort variant. You can assume that any provided file will not contain any repeated values, and that each value is provided on a separate line. Depending on the second program argument you should execute one of your three Quicksort variants. Possible values for the second user input are `first`, `median3`, and `random` (I will not feed your program invalid input). Your program will output the total number of comparisons performed by all calls to the `Partition` procedure. # Partition **NOTE: It is very important that you implement your partitioning procedure exactly as described here.** You should only need to write your partitioning procedure once (it will be used by all Quicksort variants), and it should assume that the pivot value is the first element of the given subarray (from `left_index` up to but not including `right_index`). ~~~text linenumbers # Partition the subarray array[left_index ..< right_index] # around the value at left_index. # # Args # array : an input array # left_index : the index of the leftmost value (the pivot) # right_index : one beyond the index of the rightmost value # # Return # Index of the pivot after partitioning # # Note: to calculate the total number of comparisons you may need to # add an additional output or modify a global variable # FUNCTION Partition(array, left_index, right_index) pivot_value = array[left_index] i = left_index + 1 FOR j IN [left_index + 1 ..< right_index] IF array[j] < pivot_value swap(array, i, j) i = i + 1 swap(array, left_index, i - 1) RETURN i - 1 ~~~ # Quicksort, First In your first version of Quicksort, you should always use the first element of the current subarray as the pivot. This means that you do not need to do anything special before calling partition (except checking the base case). You can check the last page of [these lecture slides](https://cs.pomona.edu/classes/cs140/pdf/l09-quicksort-implementation.pdf) for implementation details. # Quicksort, Median3 In the second version of your algorithm, you should select your pivot as the median of three values: the *first element*, the *last element*, and the *middle element* **of the current subarray**. For the middle element, if the subarray has an even length then you should take the left-middle element. From these three values, you should take the median. Since the `Partition` procedure requires the pivot to be the leftmost element of the subarray, you must swap the median value and the first element of the current subarray before you call `Partition`. For example, let `array=[6, 17, 11, 5, 13, 25, 0, 25]`, `left_index=2`, `right_index=8` (remember that `right_index` is an exclusive bound), and `middle_index=4` ($\lfloor\frac{2+8-1}{2}\rfloor$) (indices start at `0` for this example, and the index of *last* is `right_index - 1`). The three values that you will compare are `first=11`, `middle=13`, and `last=25`. From these three values, the median is `13`. So, we need to swap the `13` and the `11` before calling the `Partition` procedure (`array=[6, 17, 13, 5, 11, 25, 0, 25]`). # Quicksort, Random In the final version of your Quicksort algorithm, you will select the pivot at random. Essentially, you will pick a random index in the interval from `left_index` (inclusive) to `right_index` (exclusive) and swap the element at the random index with the element at `array[left_index]`. # Generating Test Cases If you are interested in testing your code on more inputs, here is the script that I use to generate test input files: ~~~python linenumbers #!/usr/bin/env python3 import random import sys n = int(sys.argv[1]) r = True if len(sys.argv) > 2 else False print(n) l = [str(i) for i in range(1, n + 1)] if r: random.shuffle(l) print("\n".join(l)) ~~~ It can be executed like this: ~~~bash chmod u+x generate_array.py ./generate_array.py 112 > test_ordered.txt ./generate_array.py 256 random > test_randomized.txt ~~~ # Submitting Your Assignment You will submit your PDF assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. You will also submit your code to gradescope. Your file must be named `quicksort.py`. **Only one partner should submit your code.** The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file. To pass the autograder, your output must exactly match the expected output. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do). I've enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you'd like for the leaderboard. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)