Harvey Mudd College
Computer Science 60
Assignment 0, Due Tuesday, September 9, by 11:59 pm

The 3Rs: Racket, recursion, and run-time!

In this homework you will have the chance to familiarize yourself with the Racket programming language. Racket is considered a very "clean" language, with a minimal syntax: few punctuation and formatting rules. In fact some might argue it's too minimal! As a result, Racket is one of the best examples of a language whose focus is supporting computation itself, as opposed to intricate data structuring.  In the first problem of this assignment you'll work through Racket's "Quick start" tutorial; in the second problem, you'll implement some mathematical functions in Racket, remind yourself about recursion, and reflect on a few running times... .

Pair and individual problems

• Every 30 minutes, the pair must switch off the roles of driver (at the keyboard) and navigator (looking on, perhaps with "maps," e.g., browser, slides, or notes).
• The whole problem should be completed by the pair, together, in these roles.
• The work should reflect an equal effort by both of the pair.

Submitting Your Work

For this assignment, you will write (and test!) your Racket code in two files:

• hw0pr1.rkt,
• hw0pr2.rkt,

To log in to the submission site, use your login id, which you can look-up here. Use the default password at first. After you log in the first time, change it to something you'll remember.

You may submit your work multiple times -- only the file submitted latest will be graded, but all of them will be saved in case you or we need to access them for any reason. The submission site is a convenient way to access your latest copy of a HW assignment if you work on multiple computers.

Design, commenting, and formatting

Design and formatting account for roughly a quarter of the credit for each function or program you complete. Correctness, supported by careful testing of your code, accounts for the rest.

Design, here, means algorithm design, that is, how you break a problem down into smaller pieces and then compose those pieces into an overall solution. Large, convoluted functions are difficult to understand (and debug!). Use small, clear functions with lots of small helper functions, as necessary. Formatting includes coding style: clean and clear structure, meaningful variable and function names, ample use of spacing, and indenting that reflects code structure.

Here are specific formatting features the graders will look for:

• there must be at least one blank line between functions
• indentation must accurately reflect the structure of the code
• variable names should be meaningful and consistently formatted
  • common single-letter idioms are absolutely ok, e.g., n for a generic integer, x for a generic floating-point number, i or j for generic loop indices, r and c for generic row and column indices, etc.
• whitespace should be used within lines and within expressions to reflect the visual structure of those expressions/statements. To give a Python-based example, (x2-x1)**2 + (y2-y1)**2 (with spaces) would be better than (x2-x1)**2+(y2-y1)**2
• use subexpressions to avoid unnecessarily complicated code, e.g., the above example would be better as xdiff**2 + ydiff**2 after defining xdiff and ydiff appropriately
• Factor out code when possible. Defining xdiff and ydiff as in the above example would be a matter of choice if those values were only used once. If those values had to be used again, however, your code should define those names and reuse them, rather than carrying around lots of (x2-x1)'s. This holds for computation that could be factored out into separate functions, as well as separate variables.
• above all, your use of whitespace, variable names in your code, and your formatting choices should reflect the meaning of the code and should be consistent and neat throughout

As for commenting, in each assignment we ask you to include

• a top-of-file comment with
  • your login and your partner's login (when applicable)
  • Note: You should not include your name ANYWHERE within your homework submission. Your homework assignment will be graded anonymously and you will lose 10 points if your name appears within your submission.
  • the assignment and part number
• a comment for each function describing
  • the function's input(s) and output(s)
  • briefly, in English, what it does. Feel free to omit this if it's provided.
• comments within functions or data definitions are welcome, but not required unless something tricky is going on.

Testing your code

Computation in the form of software is useful only to the extent that it works. But it only works (for sure) to the extent that it has been tested! Testing your own software thoroughly is important -- we use test cases to check how well your functions work, and you will certainly want to do the same!

It's impossible to programmatically guarantee that your code is correct. In fact, it's provably impossible to make such a guarantee! In practice, however, creating and running a set of tests for each of your functions, called unit-testing, is vital to producing useful, maintainable software. Unit testing is also a standard industry practice. In particular,

• test each function individually (unit-testing) with both the tests we provide and ones of your own design
• you should write your test cases BEFORE writing your code. This is a standard practice, which is used by big tech companies, called "test driven development." These tests should help you think about WHAT your function should do (before you think about HOW it should do it.)
• use the testing interface that is built-in to Racket (it's nice!)
• create at least one test (more, where appropriate) for each helper function you create. In the long run, this will save you time! More importantly, it will prompt you to be thinking about those "corner cases" (tricky situations) that you'll want to check.
• make sure you test before submitting!

Problem 0: Getting Started with Piazza

We will use Piazza for all Q&A in the class. You can ask questions that anyone in the class can answer, or (if you need to include code in your question) you can post a private question that only the Profs and Grutors will see.

Sign in to Piazza and check it out. If you have a question - post a question! If you can answer a question - answer a question!

Problem 1: hw0pr1.rkt (45 points)

A quick tour of Racket

Get to the Dr. Racket programming environment, either by downloading it to your personal computer or by using the CS lab.

On the CS department's Macs in BkB102 and BkB105, Dr. Racket can be found in the Additional Applications folder:

• Click on the desktop (to bring up the finder menu)
• From the top of the screen, choose the "Go" menu
• Choose "Applications"
• From the Applications window, double-click "Additional Applications"
• Among the choices, select "Programming"
• Within that Programming folder, there should be "Racket" and then "Dr. Racket" within it.

Once you have Racket running, go to the "Quick introduction" site:

The Racket quick-introduction site

which is a fun guide through a small piece of the language that uses images.

What to do    Work your way through those examples, at least up to section 8.

Do NOT worry if things start seeming crazy as you get into the later sections -- or, perhaps, the whole time! This problem is to start getting used to learning new computational interfaces, and they always seem crazy at first! You won't learn everything at once, but start to keep a list of some questions you have about the Racket language.

We will examine the ideas in sections 6-8 in more detail next week. As for sections 9-11, they are Racket-specific, rather than CS-specific, and we won't use enough Racket in CS 60 to warrant worrying about those.

Do type (or copy) the functions from sections 4-6 into the definitions pane of Dr. Racket's interface. Run them as you go. Also, save those definitions as the file hw0pr1.rkt. This is the file you will submit for problem 1.

To complete this problem, add these two functions and your answer to Question #1 to your hw0pr1.rkt file.

Question #1: Reflect (0 points - encouraged!)

Make a list of at least three notes about Racket. These can include:

• Things about Racket that seem awesome, intuitive, or crazy
• Questions you have about Racket
• Ways you think Racket might be working the same or differently than a language you know
• Other thoughts/experiences learning the language

Function #1: cboard (24 points)

Using the provided checkerboard function as a guide, create a function named cboard. But cboard should take three inputs, so that its definition will begin

(define (cboard n color1 color2)

Here is a screenshot of four examples:


Be sure to have a header comment for your function! Also, if you'd to add features, consider trying the extra credit, below...!

Function #2: hcomb (21 points)

Write another function, named hcomb, whose definition will begin

(define (hcomb n color1 color2 color3)

Here are two examples (Bears and Packers colors, perhaps...):


Again, add a header comment for your function... .

Extra-credit! alien and extra

As completely optional extra-credit (of up to +5 points each), create functions named alien and/or extra that composes Racket's graphics primitives into artistic images of your own.

alien

The alien function should output a picture of an alien, broadly interpreted, and should take one input: (alien input) - you may choose what input does, e.g., it can control size, color, or some other feature such as number of eyes... .

• You should include a comment that describes what your alien does -- and you should include at least three example invocations of extra that you would like the graders to try out!

extra

You have almost complete leeway in designing extra, e.g., it can create abstract, geometrical pictures or even more elaborate representations of aliens. It has only two constraints:

• extra should take at least two input arguments -- and it should use those input arguments, so that it creates not only one picture, but a family of pictures. You may choose what the input arguments mean.
• You should include a comment that describes what your extra does -- and you should include at least three example invocations of extra that you would like the graders to try out!

Be sure to submit your hw0pr1.rkt at the submission site without including your name!

Problem 2: hw0pr2.rkt (55 points)

Running with racket

For this problem, you will want to start with this starter file

hw0pr2.rkt

which includes a few examples of Racket syntax and its testing interface, along with the functions we wrote in class this week. As with human languages, lots of examples are the most efficient way to start feeling comfortable with a new programming language! This problem asks you to write a number of mathematical functions.

Testing (10 points)

For each problem below, you should include at least one additional test in your file, beyond what we provide. In this assignment we will provide complicated test cases. Before you write code, you should write out some simple test cases (because complicated test cases aren't very helpful for initial debugging).

Please be sure these additional tests are clearly marked with a comment above them. For example, for the erdos function you might have in your code:

; provided tests
(check-expect (erdos 84) 42)
(check-expect (erdos 85) 256)

; additional tests
(check-expect (erdos 6) 3)
(check-expect (erdos 7) 22)

Problem 2.1:    erdos (6 points)

For this problem define a function, named erdos, with one argument, N. Thus, your definition might begin as follows:

;; erdos: the "3N+1 function"
;;   inputs: an integer, N
;;   output: 3N+1, if N is odd
;;           N/2, if N is even
(define (erdos N)

; provided tests
(check-expect (erdos 84) 42)
(check-expect (erdos 85) 256)

Warning: Racket's built-in integer-division function is quotient, not the / symbol. If you try (/ 3 2) you will get the rational number three-halfs (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. The "mod" function in Racket is modulo, so that (modulo 12 7) evaluates to 5. See Prof. Keller's Racket Reference Card for a listing of the most important library functions.

Problem 2.2:    erdos-count (8 points)

Write erdos-count, a function of one positive integer argument:

(define (erdos-count N)

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

Here are a few Racket tests:

; provided tests
(check-expect (erdos-count 26) 10)
(check-expect (erdos-count 27) 111)

These are relatively complicated test cases. BEFORE writing code you should write out 2-3 exceptionally simple test cases, which will be helpful fo debugging. Here's one you might consider including:

(check-expect (erdos-count 1) 0)

Be sure to use recursion when writing erdos-count. As a starting point, consider how we wrote half-count in class.

Problem 2.3:    count1bits (8 points)

Write count1bits, a function of one nonnegative integer argument:

(define (count1bits N)

Here are a few Racket tests (you should write a few simpler test cases before writing your code):

; provided tests
(check-expect (count1bits 6) 2)
(check-expect (count1bits 7) 3)
(check-expect (count1bits 42) 3)

Problem 2.4:    power (8 points)

Write power, a function of two integer inputs (it's OK to presume non-negative integers):

(define (power b p)

Here are a few Racket tests (you should write a few simpler test cases before writing your code):

; provided tests
(check-expect (power 2 5) 32)
(check-expect (power 5 2) 25)

Experimental Run-time

Run the timing command:

(time (power 1 N))

;; time trials
(time (power 1 (expt 10 3))) ;; 1^1000
(time (power 1 (expt 10 4)))
(time (power 1 (expt 10 5)))
(time (power 1 (expt 10 6))) ;; 1^1000000

• The number of CPU-time milliseconds needed for the computation (to the closest millisecond)
• The number of wall-clock-time milliseconds needed for the computation (this is less accurate and can include other processes that might be running).
• The number of milliseconds spent freeing up memory that was used in the computation ("garbage collection").
• The return value, 1.

Problem 2.5:    fast-power (15 points)

Write fast-power, identical in its inputs and outputs to power:

(define (fast-power b p)

• If the power is 0, you're done (you're at the base case)
• If the power p is odd, compute the result recursively just as before. That is, "peel off" one factor of b.
• If the power p is even, compute (using recursion) the value of b^p/2. Again, use quotient, not /! Then, notice that the value you need to produce is b^p/2 * b^p/2. Use this fact!

Warning!    Just writing fast-power using the above technique will not necessarily make it fast! In particular, you'll need to be sure you don't repeat computation too much. One helpful construct in Racket is let, which is used for defining local variables. (You saw let in the graphics examples of problem 1.) Here is an example:

(define (f x)
  (let* (
         (y (+ x 1))
         )
    (* y y)))

Experimental Run-time In a comment in your code, run timing tests for fast-power that are analogous to the above tests for power, report the results for fast-power. You might see how big an exponent you can raise 1 to before things start slowing down... .

The test values will be the same as for power:

; provided tests
(check-expect (fast-power 2 5) 32)
(check-expect (fast-power 5 2) 25)

Extra! Problem 2.6:    factor

For completely optional extra credit of up to +5 points each, write two functions: first-factor and factor, each of which take one integer input, N, which will be greater than 1.

(define (first-factor N)

(define (factor N)

Here are two tests for each:

; provided tests
(check-expect (first-factor 41) 41)
(check-expect (first-factor 42) 2)

(check-expect (factor 41) '(1 41))
(check-expect (factor 42) '(1 2 3 6 7 14 21 42))

Submit!

Be sure to submit both hw0pr1.rkt and hw0pr2.rkt at the submission site!