CS 60 – HW1

Homework 1: Recursion Practice and Racket & Java Style

We will ease into CS60 for this homework by practicing writing recursive code in Racket. In the process, you will have the opportunity to work on your fluency with Racket and practice the professional skills of testing, tracing, debugging, and documentation. It takes time to build the skills needed to learn new languages with ease and confidence, so remember that you have Piazza and fabulous grutors to help out when you have questions!

You will notice that, in CS 60, our homework assignments can be somewhat… verbose. We know that detailed descriptions can sometimes be a bit overwhelming. However, we think that you will find the extra detail to be helpful as you work through the content at your own speed. Get after it and have fun!

You are welcome (and encouraged) to buddy or pair program for all parts of this assignment! (The syllabus can remind you of the differences.) If you have not tried buddy or pair programming, give it a try! Feel free to use the “Search for Teammates” channel on Piazza to identify potential programming buddies, or ask the teaching team to help you find a partner during lab hours.

We are really excited to help people on Piazza - so please ask questions early and often! Some more tips:

• Please use the #hw1 tag on Piazza.
• Your code will be graded anonymously. Please do not include your name anywhere in your submission.
• If you choose to pair program, remember to add your partner to each Gradescope submission.

- Your profs & the awesome CS60 Grutoring team

Problem 0: Getting Started

Problem 1: Style in Racket

Problem 2: Recursion in Racket - erdos

Problem 3: Recursion in Racket - count1bits

Problem 4: Recursion in Racket - power

Problem 5: Conditionals, Booleans, and Math in Java

Rubric

Elements of Racket style:

Elements of Java style:

Problem 0: Getting Started

• Learning Goal: Know course policies, including where to ask questions and submit homework. Be able to organize your files for the course.
• Submit: Nothing to submit!

Make sure you are added to Piazza and Gradescope using your official school email address.

• Many students choose to let Piazza and Gradescope notify them of new posts via email. If you go this route, be sure to check your email regularly to stay up-to-date with the course.
• If you log into a site, and CS60 does not show up under your account, it is likely that you have multiple accounts (e.g. one under the address tinker@hmc.edu and another under tinker@g.hmc.edu). If so, you can merge your accounts by following the instructions for Piazza or Gradescope.
• Otherwise, please let us know so we can help get you set up.

Piazza: Find Resources and Ask Questions

We will use Piazza to distribute course material and for all Q&A in the class. You can ask questions that anyone in the class can answer. You can even post anonymously if you prefer! If you need to include code you have written, you can also post private questions so that only the instructors (professors and grutors) can see. Have a question already? Great; post it! See a question you can answer? Help a fellow student!

Gradescope: Submit your Work

This assignment (and everything for CS 60) will be submitted on Gradescope. We try to limit implicit bias by grading anonymously in CS 60, so be sure your submissions never include any information that might identify you.

The Honor Code, Pair Programming, and Collaboration

Please read the syllabus carefully if you have not already.

Organizing our Files

Clone the CS60 Git repository containing all of the starter files for this class.

With the advent of search utilities, it is all too easy to put files anywhere on our computer and then search for them as needed. But it turns out that your operating system has a structure in which files are organized into folders (aka directories), and folders can be nested inside other folders. We strongly strongly recommend that you create a folder specifically for CS 60, then subfolders for different components of CS 60.

Why is organization important? We have seen from experience that poor file organization often results in duplicate copies of the same file. Maybe you downloaded starter code in one place, then edited and saved it somewhere else. Then you accidentally submit the starter code version rather than the one you edited. Oops!

Feel free to use whatever folder structure makes sense to you. Here is one recommendation: Have a top-level folder on your desktop (or elsewhere) named “CS60”. Inside this folder, have a folder for “Week1”, and inside “Week1”, have a folder “Weekly1” that stores any notes or practice code from the weekly, and a folder “HW1” that stores any code from the homework.

Problem 1: Style in Racket

• Learning Goal: Describe elements of good and bad style generally and in Racket
• Submit: Use the textboxes on Gradescope assignment HW #1.1

Remember to check the CS 60 Convention and Style Guide!

There are many important aspects of style to consider when writing code. For example:

• Providing clear comments in the right quantity: not too many, and not too few
• As code is refined, making sure to delete unnecessary, obsolete, and/or misleading comments

At this point, we expect that you have had some practice in CS 5 writing good, concise comments:

• Remove “TODOs” from starter code
• Provide insight into the code structure, for example, by identifying base cases rather than simply repeating in comments what a code fragment does

But code style is more than just comments. Good style should also:

• Be formatted in a way that emphasizes code structure, for example, by utilizing white space, parentheses, and brackets effectively and consistently
• Use meaningful names for variables and methods
• Avoid redundancies, not only for computational efficiency, but also because it improves clarity and readability

Because these three elements of good style may be less familiar to you, we would like to provide a one-time only opportunity to earn points for writing code with terrible style! For this question, we would like you to:

1. Pick two of the above: {formatting, meaningful names, and avoiding redundancy}.
2. For each of your choices:

• Write some badly-styled Racket code that showcases why this is important.
• Explain briefly why the code you wrote is bad.

3. Pick one of your examples. Improve it so that it now demonstrates good style!

We hope you have fun with this and really come up with something spectacularly confusing/bad/terrible! You will submit your bad style examples, explanations of badness, and improvements.

Problem 2: Recursion in Racket - erdos

• Learning Goal: Write recursive functions in Racket (without lists)
• Prerequisites: Racket syntax (not lists) & testing in Racket
• Starter files: erdos.rkt and erdos_tests.rkt
• Submit: erdos.rkt anderdos_tests.rkt

Note that there are two Gradescope assignments labeled HW #1.2. One is for just your Erdos implementation file and the other one is just for your test cases file.

Examine the starter files, and follow along with the problem description.

This problem explores the erdos function. erdos takes in one argument, a positive integer N, and computes the following:

In the starter file erdos.rkt, notice how the function has a top-level comment that matches this description:

The erdos-count function takes in one argument, a positive integer N, and computes the smallest number of times erdos must be applied, starting with an input of N, to arrive at a value of 1.

Let us use the symbol ==> to mean “evaluates to.” Then, (erdos-count 3) ==> 7 because it takes 7 applications of erdos to reach 1:

(erdos (erdos (erdos (erdos (erdos (erdos (erdos 3))))))) ==> 1,

Or thinking recursively, (erdos-count 3) is 7, because (erdos 3) is 10 and it takes 6 more applications of erdos to get from 10 to 1.

The starter file erdos_tests.rkt includes some provided test cases for each function. You can choose to work through these cases to help you understand the intended functionality. (If a test case seems too complex to work through by hand, then you can go ahead and skip working through it manually, i.e. use it only to test your code.)

Tips as you work through this problem:

• You can click on the drop-down menu labeled (define ...) in Racket to jump to any of your definitions. Check out this animated GIF.
• Remember that, in the interactions pane, you can access previous expressions either (PC) press the Ctrl key at the same time as the up arrow, or (Macs) Press the escape key and the letter P.

Part A: Write function comments and test cases

• Once you understand what each function should do, write a top-of-function comment for erdos-count.

• The aim of this description is to be helpful and informative to another person reading the code for the first time. For example, you should include a brief summary of what the function does, and describe the inputs (arguments) and outputs (return values).

• Write at least two simple test cases for each function in erdos_tests.rkt.

Why do we write tests first? To ensure we understand what a function is supposed to do before we try to implement it! Writing tests first is so important there is even a name for it in software development: test-driven development.

Things to keep in mind:

• You will see that we have provided complex test cases for each function.

• These are not very helpful for debugging your code! This is because complex test cases can only tell you if your code works or does not work. They do not provide insight into the ways in which code does and does not work.
• You will be graded on the extent to which your “simple” test cases are simple. For example, if we did not provide a test case that checks only the base case of the function, you should do that. If there are two possible base cases, you should have one simple test case for each of these. In general, if there are different “paths” for your code depending on the input, you should test each of those inputs.
• Writing these test cases can be really helpful for thinking through the behavior of the code, and we want you to start seeing how good test cases help you debug! If you are unsure of whether your test cases are “good enough”, feel free to talk with course staff.

• To make it easy for us to identify your additional test cases, you are required to include this comment before your test cases:

; student tests

This comment is provided in the starter file for this problem.

Before you move on, verify that you can run the tests. For now, they will all fail because the function stubs in the starter code return the wrong answers! If you want added security before moving on, submit erdos_tests.rkt on Gradescope. The autograder will run our implementation of erdos and erdos-count against your test cases, which should pass.

Part B: Write erdos

Hints:

• Racket's built-in integer-division function is quotient, not the / symbol. If you try (/ 3 2), you will get the rational number three-halves, instead of the floating-point number 1.5 or the integer 1. But (quotient 3 2) evaluates to 1, as expected with integer division.

Be sure your function passes the provided test cases and your additional test cases.

If you want added security before moving on, submit erdos.rkt on Gradescope. The autograder will run your implementation of erdos against our test cases, which are likely more exhaustive than your set.

Part C: Write erdos-count 

Be sure to use recursion when writing erdos-count. Do not forget that every recursive definition needs at least one base case that does not result in a recursive call!

Here are a few more tests in the starter file:

These are relatively complicated test cases — if the second test fails because your (erdos-count 27) produces 119 instead of 111, you will know there is a bug, but there are so many reasons this complicated computation could have gone wrong that it does not provide any hints for finding and diagnosing the problem.  That is why we asked you to add two super simple test cases in part A, which should be much more helpful for debugging.

For this assignment, you do not have to worry about inputs that are less than 1 (which will likely produce an infinite loop). It would be best practice to add some input checks to return a little error message rather than infinitely looping, but we think the problem is hard enough without worrying about this right now, so we do not require input checking. :-)

If you are having trouble, try using the methods in the weekly to reason about recursion. In particular, we recommend using trace on erdos and/or erdos-count.

Important: Remember to (re)submit your final versions oferdos.rkt and erdos_tests.rkt on Gradescope.

Part D (optional): The Collatz Conjecture

No matter the value of N, will applying erdos always reach 1? Read more about the Collatz Conjecture! (We suggest at least reading the introduction, including the quote by Paul Erdős.)

More fun: Erdős was such a prolific mathematician that academics measure our “distance” to him through the Erdős number. Former HMC President Klawe has an Erdős number of 1!

Problem 3: Recursion in Racket - count1bits

• Learning Goal: Learn about the structure of Racket files (and write some code)
• Prerequisites: Racket syntax (not lists) & testing in Racket
• Submit: count1bits.rkt and count1bits_tests.rkt under the two Gradescope assignments for HW #1.3 (one for your implementation file, and one for your tests file)

This problem asks you to implement and test the count1bits function, a recursive function that takes in one non-negative integer argument N, and returns the number of times the bit 1 appears in the binary representation of N.

Here is the function signature of count1bits, which tells us the function name and its argument.

To understand the functionality of count1bits, you might need to review binary representation. (In particular, CS 5 Gold/Black cover base conversions, but CS 5 Green does not.)  If you have not seen it, you might also try the tests below (by hand). Feel free to use the internet to research binary representation; there are a lot of great resources out there!

Here are a few Racket tests, to complement the simpler test cases you will write.

Part A: Prepare your solution files

• Create Racket files named count1bits.rkt and count1bits_tests.rkt
• Double-check that both files start by specifying the correct language (i.e. Racket):

#lang racket

• Add Racket code to the tests file (only) to allow you to use the testing framework and your (future) function from count1bits.rkt:

• Add Racket code to the definitions file (only) that will mark your count1bits function as “public”:

• Note: We are providing these detailed instructions here, but in the future you will need to remember these steps (OR remember to look back at these steps).
• Don’t forget the provide statement -- without it, our autograders cannot see your code!

Part B: Write function comments and stubs, and test cases (before you write any code!)

• Write a function comment for count1bits. (See the previous problem to review the instructions for what goes in a function comment.)
• Write a function stub for count1bits.

• A function stub allows us to start writing test cases before we have implemented the function being tested.
• A function stub should consist of (1) the function signature and (2) a function body that returns a temporary result. For example, let us say you were writing tests for a function that did a bunch of calculations and eventually returned a boolean value. You might write a stub for this function that always evaluates to “False” (or equivalently, always evaluates to “True”). You would eventually replace the stub with your real code, but having a trivial implementation allows you to run your tests (which will initially fail).

• Write at least two simple but useful test cases for count1bits. (See the previous problem to review the instructions for what we mean by “simple”.) Mark your tests with the comment ; student tests
• Copy-and-paste the tests provided above into your file. Mark these tests with the comment ; provided tests

If you want added security before moving on, submit count1bits_tests.rkt on Gradescope. The autograder will run our implementation of count1bits against your test cases, which should pass.

Part C: Write count1bits 

Hints:

• You do not need to actually convert N to binary. (In fact, do not use this approach.)
• Consider if the input is odd - What does that say about its rightmost bit? What if the input is even?

• Racket provides helpful functions odd? and even? that you can use

• What arithmetic operation will “get rid of” that rightmost bit, thereby “shifting” all the bits to the right by one place?
• As with all things Racket, recursion will be key!

Optional: Add input checking to gracefully handle unexpected input.

Important: Remember to (re)submit your final versions of count1bits.rkt and count1bits_tests.rkt on Gradescope.

Problem 4: Recursion in Racket - power

• Learning Goal: Reason about the runtime of code
• Prerequisites: Racket syntax (not lists) & testing in Racket

• Submit: power.rkt and power_tests.rkt under the two Gradescope assignments for HW #1.4

power is a recursive function that takes in two non-negative integer arguments base and pow, where pow is the power to raise the number base to. power should evaluate to basepow. Note that base0 should evaluate to 1 for any value of base. fast-power is identical to power (same inputs and outputs), but, as its name implies, just does things faster (details on how later).

Function signatures:

Here are some things to notice about the variable names we chose:

• We did not use b and p for the variables because they are not descriptive. (Even worse, these particular letters could make your code especially difficult to understand for people with some reading disorders!)
• We used pow instead of power because we are currently defining the function power, and we cannot reuse that name.

Here are a few Racket tests, to complement the simpler test cases you will write.

You should use these same test cases for fast-power too.

On this problem, using good style may require the most effort! If you would like feedback on your commenting style, please ask a grutor or instructor. See also the detailed rubric of bad style elements.

Part A: Prepare your solution files and write simple test cases

• Create Racket files namedpower.rkt and power_tests.rkt

• Try to add setup your files without peeking at the instructions above (but go ahead and peek as needed)

• Write function comments and stubs for power and fast-power
• Write at least two simple but useful test cases for power and fast-power. Mark your tests with the comment ; student tests
• Copy-and-paste the tests provided above into your file. Then copy-and-paste it again, and modify the name from power to fast-power. Mark these tests with the comment ; provided tests

If you want added security before moving on, submit power_tests.rkt on Gradescope. The autograder will run our implementation of power and fast-power against your test cases, which should pass.

Part B: Write power 

The built-in function expt is not allowed here -- imagine you are implementing it for the Racket library. Rather, you should implement power in terms of multiplication, addition/subtraction, and recursion:

(If you know a fancier algorithm for computing powers, please save it until the next problem!)

Part C: Write fast-power

In Problem 1, we discussed how redundant calculations can be a symptom of badly-styled code. Next, we will improve our implementation of power by using an algorithm to reduce redundant calculations.

To implement fast-power, use the following idea:

• If the power is 0, you are done (yay for the base case!)
• If the power is odd, compute the result recursively as before. That is, “peel off” one factor of base.
• If the power pow is even, compute (using recursion) the value of basepow/2. Then, use the fact that the value you need to produce is:

Hints:

• Your solution must use recursion.
• You are free to use Racket functions odd?, even?, and/or quotient.

• Double check that you have written fast-power to actually make it fast! In particular, you will need to be sure you do not repeat computation unnecessarily. For instance, consider how you can use let or let* to avoid computing basepow/2 twice.

Part D (optional): Compare!

We claimed that fast-power is faster than power. Let us see if that is true using Racket’s time function.^[1] You do not have to understand the details of the syntax below; in brief, we are calling power and fast-power and telling Racket to ignore printing the output using void. (The actual value of base^pow can be huge for large powers, and printing that value might take longer than computing it!)

(time (power 2 100000) (void))

(time (fast-power 2 100000) (void))

Optional: Add input checking to gracefully handle unexpected input.

Important: Remember to (re)submit your final versions of power.rkt and power_tests.rkt on Gradescope.

Problem 5: Conditionals, Booleans, and Math in Java

Before going any further, please get the Java plug-in of VSCode set up by following the Java VSCode instructions on the class web page. This guide covers everything from installing VSCode to getting the right Java version and uses JavaBasics_starter from the GitHub repository as the example.

Stop by grutoring or office hours if you have questions up to this point!

• Learning Goal: Write the body of Java methods using booleans, conditionals, and Math-class methods
• Prerequisites: Java conditionals, booleans, Math; JUnit testing in VSCode
• Starter files:Basics.java and BasicsTests.java
• Submit: Basics.java (only)

This problem will familiarize you with the Java programming language – or, at least, its syntax. Later in CS 60, we will consider Java’s object-oriented design and the capabilities that make it a popular industry/enterprise language.

One of CS 60’s goals is to help you feel confident that you can use any new computational language effectively and efficiently – all you need is a syntax reference. This problem practices this skill using problems from CodingBat, which has many small one-function challenges and some succinct references.

We have also included a few problems that use the Java class Math. It has helpful constants like PI and helpful methods that do things such as return the max of two numbers or calculate the absolute value of a number.

Part A: Read how to tackle this problem

Your task is to complete the methods in Basics.java. Here is what you should do for each method:

• Read the comment above the method in the file.
• Try writing a draft of the solution code in Java.
• If your code works, yay! You are done!
• Otherwise, practice these steps to improve your solution:

• Use your favorite search engine to look up the exact text of the error messages Java gives you. What do they mean?
• Look for relevant tutorials or examples that use Java. For example, you might Google: java if statement example. (Note: It is helpful to use the word “Java” and the word “example” when looking for this kind of information.)
• Check out resources provided by CodingBat.

• For this problem, we recommend Java If and Boolean Logic.

• As a last resort, follow the link in the function comment and look at the solution.

• The link shows the “Source” of the coding problem. Click on “Show Solution”, which gives the correct answer!
• Caveat: Our solutions have the word static in the function signature. You will need to add this modifier to the solution after you copy-paste. Alternatively, just copy the body of the method when you copy the solution. (We need to add the word static because of how we set up our test cases.)

• Remember that an overarching learning goal for CS 60 is to become better practitioners of computer science. That means using good style (which we have talked about already) and knowing how to look for help (within course staff and beyond course staff).

We ask that you make an earnest try to answer each question on your own. If you need to use the solutions, you are free to do so. But, if you do, please include a comment in your code for that function explaining what facet of the problem you had trouble with.

Example: Imagine we needed to look at CodingBat’s solution for the sleepIn problem. In that case, it is okay to use their solution as long as we include a comment such as the one below.

Notice that single-line comments in Java are indicated by //. Multi-line comments in Java are indicated by /* at the start and */ at the end.

Remember, the goal is that you become comfortable with Java and its syntax – articulating what was new or surprising in a comment will help you do just that!

Part B: Write code to pass all the tests

Complete the methods in the file Basics.java to make the tests in BasicsTests.java pass.

We recommend working iteratively. That is, after you complete one function, test it by opening the tests file and clicking on the green “Run” button to run the tests.

Before you submit, be sure to go over the checklist in How to Submit.

Rubric

We want to be as transparent as possible in our grading system.

Problem 1 (12 points): 4 points for each bad style example, 4 points for correction and explanation.

Problems 2-4 (16 points each):

Problems 2 and 3:

Tests (4 points): You write 2 tests. 1 point each for correctness. 1 point each for being good/simple.

Function implementation: (12 points):

1 point for correct recursive approach

3 points for style (15 elements of style below. Minus 0.5 points for each violated to min of 0.)

8 points for autograded functionality

        Problem 4:

                Tests (4 points): You write 2 tests. 1 point each for correctness. 1 point each for being good/simple

                (fast-)power implementation (12):

 3 points for style (15 elements of style below. Minus 0.5 points for each violated to min of 0.)

 1 point for correct recursive approach to power

 2 points for using let or let* correctly in fast-power

 1 point for correct recursive approach to fast-power (calls itself rather than power)

 5 points for autograded functionality

Problem 5: 11 points functionality and 6 points for style

Elements of Racket style:

We will check for the following elements of bad style on Problems 2-4:

• Comments

• Complicated lines of code are not explained.
• Too many comments can be just as confusing for a reader as no comments at all. We want to save inline comments for particularly tricky pieces of code and do not need one for every line.
• Missing a function-level comment, or the function-level comment is missing a description of the function and its inputs and outputs.

• Naming

• Variable or method names are not helpful or do not follow language-specific conventions.

• Formatting

• Function(s) are written in a way that makes it hard to read (e.g. lines too long so text wraps, missing meaningful indentation).
• Racket convention is to put all closing parentheses on the same line.

• Redundancy

• Function(s) have copy-pasted code rather than using helper functions.
• Function(s) explicitly returns true/false rather than returning predicates directly.
• Function(s) have redundant predicates rather than using else.
• Recursive function(s) have an “extra” base case that is covered by the recursive case.

• Helper Functions

• Code is not “self-documenting”, e.g. does not use built-in Racket functions where possible. (Exception is if the assignment instructions specifically forbid the use of such functions.)

• Control Structures

• Good style uses if over cond for single predicates (plus possibly an else case), and uses cond over if to avoid nested ifs (unless doing so would repeat predicates).

• Miscellaneous

• Files contain startup notes such as “TODOs” or “delete this”.
• Files contain debugging statements, including unnecessary print statements or output trace statements.
• Files contain student name(s). We grade everything anonymously in CS60 so that things are graded as fairly as possible.

Elements of Java style:

We will check for the following elements of bad style:

Notable differences from Racket noted in blue!

• Comments

• Complicated lines of code are not explained.
• Too many comments can be just as confusing for a reader as no comments at all. We want to save inline comments for particularly tricky pieces of code and do not need one for every line.
• Missing a function-level comment, or the function-level comment does not conform to Javadoc style.

• Naming

• Variable or method names are not helpful or do not follow language-specific conventions.

• Formatting

• Function(s) are written in a way that makes it hard to read (e.g. lines too long so text wraps, missing meaningful indentation). Your code might look reasonable in VSCode but show up much differently in Gradescope. You should make a habit of formatting the whole document
• Curly braces should follow style guide (opening braces same line as function declaration / control structure, closing braces on own line except when followed by else or else if, function and control structure bodies enclosed in curly braces).

• Redundancy

• Function(s) have copy-pasted code rather than using helper functions.
• Function(s) explicitly uses true/false rather than using predicates directly.
• Function(s) have redundant predicates rather than using `else`.
• Function(s) are overly complicated, e.g. include extra base case or other unnecessary code. 

• Helper Functions

• Code is not “self-documenting”, e.g. does not use built-in Java functions where possible. (Exception is if the assignment instructions specifically forbid the use of such functions.)

• Control Structures

• Good style uses `for` loops over `while` loops whenever possible.
• Please use the syntax `if (condition) { body } else { alternate }` rather than using the ternary operator.

• Miscellaneous

• Files contain startup notes such as “TODOs” or “delete this”.
• Files contain debugging statements, including unnecessary print statements or output trace statements. (Exception: Okay in `main` method.)
• Files contain student name(s). We grade everything anonymously in CS60 so that things are graded as fairly as possible.

• Miscellaneous Java

• Be sure to use the logical operators `||` and `&&` rather than the bitwise operators `|` and `&` when testing `true/false` conditions. Using the bitwise operators may sometimes lead to unexpected values.

How to Submit

Let VSCode help!

• We strongly encourage you to allow VSCode to organize your Java files in its own preferred directory structure. That is, do not move around files either within VSCode or in a File Manager (e.g. Windows Explorer or Mac Finder).
• VSCode will show you syntax errors (e.g. missing semicolons or braces) and compilation errors (e.g. unknown variable name, type mismatch). Check and fix red Xs. (See more in table below.)

Do NOT use the autograder as a debugger!

• Even though it is tempting to upload to the autograder over and over again as you go, please get into the habit of running your code locally to look for runtime errors (e.g. null reference exceptions) and logic errors (e.g. failed test cases). If your code does not work locally, it will not pass the autograder. And even worse, because the autograder is a black-box, you will not know why the code failed ☹️

• To give you credit for your work, you will need to follow the submission instructions! Please carefully review the instructions below.