Homework 1B (CS 15): Recursion

--- tags: hw, spr22 --- # Homework 1B (CS 15): Recursion ### Due: Monday, February 7th, 2022 at 11:59pm ET **Collaboration Policy:** *You may collaborate as much as you want on this assignment* (this is more flexible than the normal course policy). The goal is to get everyone up to speed on functional programming. You are required to turn this in, but it will be weighted lightly in final grades. That said, we strongly encourage you to actively try writing these on your own while collaborating, as assignments after we come back together will assume you can do these sorts of problems on your own. **Topic:** This assignment has you practice writing functions using recursion ([song, anyone?](https://youtu.be/CduA0TULnow)), including a functions to sort lists. Some problems also ask you to annotate code to compute the total run-time of your program. ## Learning Objectives * practice writing recursive functions * practice annotating code for worst-case run time * implement a sorting algorithm ## Setup * Go to [code.pyret.org](https://code.pyret.org/); this requires logging in with any Google account (like your Brown account). * Make a new file in code.pyret.org called `hw1b-15-code.arr`. * Do not put your name anywhere in the file. Before you start, paste this statement at the top of your code. ``` provide {my-member: my-member, insert: insert, spell-check: spell-check, days-in-range: days-in-range, quicksort: quicksort} end ``` ### Documentation Once you have opened the editor, the Pyret documentation is accessible from the Pyret logo button in the top left corner of code.pyret.org. ### Staff Assistance Your friendly TAs and Professors are here to help with this assignment! We monitor [Ed](https://edstem.org/us/courses/16807/discussion/) regularly, and it's a fantastic resource! You can find our schedule for office hours [here](https://brown-csci0200.github.io/calendars.html). ## Member **Task:** [Is Nick still in the Jonas brothers?](https://www.youtube.com/watch?v=HSry5-qfVFs) Write a recursive function called `my-member` that takes in a list and an element. It should return `true` if that element is a member of the list and `false` otherwise. - `my-member([list: "Kevin", "Joe", "Nick"], "Nick")` is `true` - `my-member([list: 2, 4], 1)` is `false` **Task:** Write tests for `my-member` using a `check` block in Pyret. ::: spoiler *Hint*: How can my function take in both strings and numbers? In many languages (Pyret, Java, etc.), there is the ability to have a function take in any arbitrary type as an input. In Pyret, we use the datatype known as `Any`. For example: ``` fun conjoin(a1 :: Any, a2 :: Any) -> List<Any>: doc: "joins any two elements together in a single list" [list: a1] + [list: a2] end ``` This allows us to use any datatype we want as inputs. For instance, valid uses of this function would be 1. `conjoin("Burnin'", "Up")`, 2. `conjoin(200, false)` ::: ## Insert **Task:** Write a recursive function called `insert` that takes a number and a sorted list (sorted from low to high) and produces a new sorted list that includes the new number and the elements of the original list, sorted from low to high. - `insert(5, [list: 2, 4, 7])` is `[list: 2, 4, 5, 7]` - `insert(3, [list: 1, 2, 3])` is `[list: 1, 2, 3, 3]` **Task:** Write tests for `insert` using a `check` block in Pyret. ## [Drop it like it's "alot"](https://youtu.be/GtUVQei3nX4)! ![The alot monster wants you to have proper grammar](http://i0.kym-cdn.com/photos/images/original/000/180/046/Untitled-1.png =300x300) **Task:** Oh no! It's the alot [monster](https://www.youtube.com/watch?v=EHkozMIXZ8w)! Write a recursive method called `spell-check` that takes in a list of strings and returns the list with any occurence of the nonsense word "alot" to be two separate words "a" and "lot." - `spell-check([list: "alot", "of", "work"])` is `[list: "a", "lot", "of", "work"]` - `spell-check([list: "alot", "alot", "of", "code"])` is `[list: "a", "lot", "a", "lot", "of", "code"]` **Task:** Write tests for `spell-check` using a `check` block in Pyret. Annotate each test with a brief comment that describes which interesting behavior it tests. ## [Cooler Than Me](https://www.youtube.com/watch?v=mqWq_48LxWQ) Does the weather think it's cooler than you? Let's say you're given weather readings across several days. Each day is captured as a list of temperature readings. This is an example of data for four days: ``` temp-data = [list: [list: 56, 58, 60, 64, 64, 58], [list: 62, 65, 65, 65, 65, 63, 60], [list: 45, 48, 50, 52, 53], [list: 53, 53, 51, 48, 45, 42] ] ``` These data feature lists inside of lists, which you haven't worked with before (that is the point of our doing this problem). Note that the inner lists can be of different lengths from one another. Our overall goal is to write a function `days-in-range` that counts how many days had *all* of their temperatures within a given range, inclusive. For example: - `days-in-range(temp-data, 10, 100)` is `4` (all days) - `days-in-range(temp-data, 45, 60)` is `1` (third day) - `days-in-range(temp-data, 65, 80)` is `0` (no day has all temperatures above 65) The learning objective here is to see how you handle lists within lists. **Task:** Write tests for `days-in-range` using a `check` block in Pyret (don't write the code first. Just write the tests). **Task:** Think about what your code would have looked like to do this problem in Java: would you use one loop? Two loops? More loops? Would you have nested loops or one after the other? There's nothing to write down or submit for this, but take this step seriously as it will help you with the structure of the recursive solution. In general, *each for loop turns into a separate recursive function*. If your Java solution has one loop, your recursive solution has one function. If your Java solution has two loops, your recursive solution needs two recursive functions. If your Java solution nests loops, then one recursive function will call another as a helper. The pattern of how you walk across/traverse the data is the same in both approaches. **Task:** Write a function `all-in-range` that takes a list of numbers, a low value, and a high value,and determines whether all numbers in the list are between the low and high values, inclusive. **Task:** Use `all-in-range` as a helper to write `days-in-range`. As a reminder, `days-in-range` counts how many days had all of their temperatures within a given range, inclusive. ## Annotating Code with Worst-Case Run Time :::info Updated Friday, 2/4, at 6:45 pm ::: Do these tasks using the style shown in lecture and our [How to Compute Worst-Case Runtime](https://hackmd.io/@csci0200/H1yai8SCF) document. **Task:** Annotate your `all-in-range` function with the run-time calculations per line. Under the code, include a computation showing the overall worst-case run-time of this function, assuming a max of $M$ readings for any one day. **You should write this time, T-air(M) as a recurrence relation. For example, if each recursive call is done on an input that is 1 smaller, you should write T-air(M) in terms of T-air(M-1).** **Task:** Annotate your `days-in-range` function with the run-time calculations per line. Under the code, include a computation showing the overall worst-case run-time of this function, assuming $D$ days and a max of $M$ readings for any one day. **You should also write this time, T-dir(D,M), as a recurrence relation. You do not have to expand T-air(M), and can just leave it as T-air(M). For example, `T-dir(D,M) = 20 + T-dir(D-3) + T-air(M)`, while wrong, is an example of the sort of format we are looking for.** :::success You should not be solving for the closed-form of the recurrence relations for this homework! ::: ## Sorting [right round, right round](https://www.youtube.com/watch?v=CcCw1ggftuQ) Sorting collections of data is a common task in computing. Most programming languages provide built-in operators for sorting. As a programmer, you need to know how to use these built-in functions. As a computer scientist, however, you should understand the underlying algorithms as well. There are many ways to sort a list. You'll see `mergesort` in lecture. For homework, you'll implement a different algorithm called `quicksort` and use it to sort a list of numbers into ascending (increasing) order. ### Quicksort ([here it goes again :D](https://www.youtube.com/watch?v=dTAAsCNK7RA)) Quicksort takes a single element (called the "pivot"), and splits the list into two sublists: one sublist of items that are smaller than the pivot, and one of items that are greater than or equal to the pivot. The algorithm sorts each of these sublists, then appends the sorted lists with the pivot in the middle. Here's an image showing how the algorithm works. The pivot is the first element in each list (shaded in blue). The purple arrows show the lists of smaller and larger elements that get used in recursive calls. The green line shows how the elements end up ordered in the final list. ![quicksort illustration](https://i.imgur.com/hxjwAv5.png =700x240) Here's a summary of the steps of the algorithm: 1. **If the input list is empty:** Return the empty list. 2. **If the input list contains a single element:** Return a list containing just that element. 3. **Otherwise:** 1. Choose the first element of the list to be the "pivot". 2. Split all of the elements in the rest of the list into two separate lists: one containing all elements less than the pivot, and one containing all elements greater or equal to the pivot. 3. Run `quicksort`(recursively) on each of the new lists. 4. Join elements into a new list in the following order: first the one with elements less than the pivot, then the pivot, then the one with elements greater than or equal to the pivot. ::: warning If the algorithm isn't yet clear to you, work out a couple of examples on paper, along the lines of the diagram we provided above. Don't try to write the code until the hand-drawn examples make sense to you. *You do not have to turn in the hand-drawn examples*. ::: **Task:** Write the `quicksort` function with header ``` quicksort(lst :: List<Number>) -> List<Number>: ``` You may use `map`, `filter`, or explicit recursion, as you wish. You may not, however, use Pyret's built-in `sort` function. To concatenate two lists, you can use either the `append` method on lists or the `+` operator: ``` # both of these expressions produce [list: 2, 3] [list:2] + [list: 3] [list:2].append([list: 3]) ``` **Task:** Write tests that cover a good set of inputs for `quicksort` using a `check` block in Pyret. Annotate each with a brief comment saying why it is an interesting example for this algorithm.  ## Handing In For this homework, you MUST submit your solutions in a file called: `hw1b-15-code.arr` For autograder compatibility, please check that all required function names exactly match the functions named in this handout. To hand in your solution, you must upload them to Gradescope. Do not zip or compress them. Read our [Gradescope Submission Guide](/oTbF1IUuRs27VgVJF4z2rA) for help on submitting to Gradescope. --- *Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out the [anonymous feedback from](https://forms.gle/JipS5Y32eRUdZcSZ6)!*