<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # Homework 1B-from-OO (Spring 2025) **Due: Sunday, February 2 at 11:59pm EST** :::info **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 Java. 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 future assignments will assume you can handle these sorts of problems independently. ::: **Need help?** Find us, as well as questions and answers from other students, on [EdStem](https://edstem.org/us/courses/69789/discussion)--**be sure to check our FAQ/reading list post before posting, since this contains helpful tips that may already answer your question!** Also, here’s our [office hours schedule](https://brown-csci0200.github.io/calendars.html). ### Learning Objectives In this assignment, you will: - practice writing recursive functions - practice annotating code for worst-case run time - implement a sorting algorithm ### Stencil Code and Assignment Setup Using **[this GitHub Classroom link](https://classroom.github.com/a/Rl3Q1Oxk)**, accept the assignment and create a repository for your code. **Be sure to follow the instructions in the [Java Stencil setup guide](https://docs.cs200.io/s/java-stencil-setup-guide)** for instructions on how to do this. This assignment requires that you have IntelliJ installed and set up for this course. For details on the setup process, please see the [IntelliJ Setup Guide](https://docs.cs200.io/s/intellij-guide). If you’re having trouble, the guide includes a [Common Bugs/FAQ](https://docs.cs200.io/s/intellij-guide#Common-BugsFAQ) section which might help. :::info <details><summary>Click here if you encounter errors about missing jar files when opening the stencil</summary> If you receive errors about this, you may need to add both the hamcrest-core-1.3.jar and junit-4.13.2.jar files as dependencies to your IntelliJ project. If you’re not sure how to do this, check out the [Adding Jars/Dependencies](https://docs.cs200.io/s/intellij-guide#Only-if-necessarynbsp-adding-JarsDependencies) section of the IntelliJ Setup Guide. </details> ::: ### Style Expectations While you may have seen references to the course style guide, for this first assignment **we’ll only be expecting the following style requirements**: - Basic Javadocs for all methods (you can look in the class notes for examples of these) - Method and variable names are in `camelCase` - Class names are in `UpperCamelCase` ### :rotating_light: Super important notes :rotating_light: Since this is part of our first assignment, our autograder needs to be set up a bit differently than usual and has a few extra requirements. To be consistent with our autograder, you must follow a few conventions (just for hw1): - **If we ask you to make fields in a class, make them `public`**: That is, if you were creating a field called `length`, you should declare it as `public int length`, similar to what we did in class. - **Naming**: If the handout asks you to create a field or method, give it with **exactly** the same names as listed in this handout. Our autograder will try and access fields with these names--if you don't use them, there will be errors! You are free to use whatever names you want if you make extra helper methods or other fields--so long as it's for something we didn't specifically ask you to write. :::success **What to expect in HW1**: The handout, and HW1 as a whole, guides you through developing the code in multiple stages. **You will turn in one set of files with your cumulative work on all tasks.** You do _not_ need to maintain versions of your code from each task separately. ::: ## Member Similarly to Homework 1A, we are having you write tests for your methods before you write the methods themselves. The `ListUtils` class has a static method called `member` that takes in a `FuncList` and an `Object` and returns true if and only if the object is in the `FuncList`. For example, “Patrick” is a member of the `FuncList` that contains “Mr Krabs,” “Patrick,” and “Sandy.” ### Task 1-A **Write some assertions to test `member` in the `testMember()` method of `Homework1BTest.java` Refer to the [Java Testing Guide](https://docs.cs200.io/java-testing-guide) for an overview of JUnit tests and assertion statements.** A good set of tests will include a reasonable sequence of progressively smaller examples (like we did in class). You should also test for special cases. :::info <details> <summary> <b> Note </b> </summary> In `Homework1BTest.java`, just like we saw in class, we have provided you with a `FuncList` constructor that will build a `FuncList` from the sequence of inputs you give it. Feel free to use it to save you some typing: new FuncList(“Mr Krabs”, “Patrick”, “Sandy”) And can be used like ListUtils.member(new FuncList(“Mr Krabs”, “Patrick”, “Sandy”), “Patrick”) </details> ::: ### Task 1-B **Complete the `member` method in the `ListUtils` class and make sure your tests pass.** :::warning Your method will be recursive, i.e. there will be at least one call to `member(list.rest(), …)` in the body of the method. ::: <br> ## Insert The `ListUtils` `insert` method should take in a sorted (from least to greatest) `FuncList` of`Integer` and an `int` and returns a new sorted `FuncList` that includes the new number and the elements of the original list, sorted from low to high. For example, calling `ListUtils.insert([FuncList containing 2, 4, 7], 5)` should return a `FuncList` containing 2, 4, 5, 7. <br> ### Task 2-A **Write some assertions to test `insert` in the `testInsert()` method of `Homework1BTest.java`.** <br> ### Task 2-B **Complete the `insert` method in the `ListUtils` class and make sure your tests pass.** :::warning Your method should be recursive. ::: <br> ## Spell Checking  The `ListUtils` `spellCheck` method should take in a `FuncList` of Strings and returns the list with any occurrence of the nonsense word “alot” to be two separate words “a” and “lot.” For example, calling` ListUtils.spellCheck([FuncList containing “alot”, “of”, “work”])` should return a `FuncList` containing “a,” “lot,” “of,” “work.” ### Task 3-A **Write some assertions to test  `spellCheck` in the `testSpellCheck()` method of `Homework1BTest.java`.** <br> ### Task 3-B **Complete the `spellCheck` method in the `ListUtils` class and make sure your tests pass.** :::warning Your method should be recursive. ::: <br> ## More Complicated Weather :::info <details> <summary> <b> Important Example </b> </summary> 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 (here we use the bracket `[...]` notation as a short-hand for representing lists, though your code will still use `FuncList`s): tempData =    [     [56, 58, 60, 64, 64, 58],     [62, 65, 65, 65, 65, 63, 60],     [45, 48, 50, 52, 53],     [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 doing this problem). Note that the inner lists can be of different lengths from one another. </details> ::: Our overall goal is to write a method `daysInRange` that counts how many days had all of their temperatures within a given range, inclusive. For example: - `daysInRange(tempData, 10, 100)` should return 4 (all days) - `daysInRange(tempData, 45, 60)` should return 1 (third day) - `daysInRange(tempData, 65, 80)` should return 0 (no day has all temperatures above 65) **The learning objective here is to see how you handle lists within lists using recursion.** <br> ### Task 4-A **Write some assertions to test  `daysInRange` in the `testDaysInRange()` method of `Homework1BTest.java`.** <br> ### Task 4-B **Think about what your code would look if you did this problem iteratively: 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. :::success <details> <summary> <b> Hint </b> </summary> In general, _each for loop turns into a separate recursive function_. If your iterative solution has one loop, your recursive solution has one function. If your iterative solution has two loops, your recursive solution needs two recursive functions. If your iterative 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. </details> ::: <br> ### Task 4-C **Write a method `allInRange`** that takes a`FuncList` of ints, a low value, and a high value, and determines whether all numbers in the list are between the low and high values, inclusive. As part of this task, **you should complete the `testAllInRange()` test and make sure all of the assertions pass.** For both parts, assume the `FuncList` is a non-empty list of integers. <br> ### Task 4-D **Use `allInRange` as a helper to write `daysInRange`.** As a reminder, `daysInRange` counts how many days had all of their temperatures within a given range, inclusive. **Run your tests and make sure they pass.** <br> ## Annotating Code with Worst-Case Run Time :::warning Do these tasks using the style shown in [lecture](https://brown-csci0200.github.io/lectures.html) and our [How to Compute Worst-Case Runtime](https://docs.cs200.io/runtime) document. ::: ### Task 5-A **Annotate your `allInRange` 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)_**. :::info <details> <summary> <b> Note </b> </summary> The term “recurrence relation” here refers to a formula such as T(N) = … T(N-1) …. This is the form we used in class when showing the formula version of the cost of running oddOnly. Just give this your best shot – don’t worry about the grade on task 5. Instead, give it a try and when you get stuck, write a sentence or two about what you aren’t sure about. </details> ::: <br> ### Task 5-B **Annotate your `daysInRange` 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.** :::warning **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.** ::: <br> ## Sorting 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. <br> ### Quicksort 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. :::success <details> <summary> <b> How the Algorithm Works (read this!) </b> </summary> 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.  Here’s a summary of the steps of the algorithm (which can be translated into the lines of code that need to be written for this task): 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. :::info **_Note:_** 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. ::: </details> ::: <br> ### Task 6-A **Write some assertions to test `quicksort` in the`testQuicksort()` method of `Homework1BTest.java`.** Annotate each with a brief comment saying why it is an interesting example for this algorithm. <br> ### Task 6-B **Complete the `quicksort` method in the `ListUtils` class and make sure your tests pass.** :::success You may use `map`, `filter`, or explicit recursion, as you wish. You may not, however, use any Java built-in sort methods. ::: *** <br> ## How to Hand In  To hand in your homework, **submit** the following files to the **Homework 1B-15: Implementation** assignment on Gradescope (make sure to exclude the `AutograderCompatibility.java` files from your submission): - `Homework1BTest.java` containing `public class Homework1BTest` - `ListUtils.java` containing `public class ListUtils` Once you have handed in your homework, you should receive an email, more or less immediately, confirming your turn-in. :::info <details> <summary> <b> Note on Autograder Compatability </b> </summary> There should be a class in the stencil code named `AutograderCompatibility`. Using this class is required to ensure that your submission is working correctly with the autograder. After we get past homework 1, you will lose points if your code does not work with the autograder (so you might want to use this file to help check for errors). If you get an error involving this file when you try to run your code, the problem is with your code, not this file. You should not edit the `AutograderCompatibility` file.  If Gradescope gives you the message _“Could not run your code (0.0/0.0),"_ uncomment the main method of `AutograderCompatibility` and check that it compiles and runs. If the Gradescope autograder still doesn’t work, come to hours or post on Ed for help. </details> ::: _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://docs.google.com/forms/d/e/1FAIpQLSfe9cDwpzv7xCbbevbrAZacuB4MB8yxer8jiK0SK-CQH3RXuQ/viewform?usp=header)_!_