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 rktimal! 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... .
For this assignment, you will write (and test!) your Racket code in two files:
To log in to the submission site, use your login id, which should be your first initial followed by your last name. Use the default password at first. After you log in the first time, be sure to change it to something you'll remember. Note that the site may ask you to re-login with your old password before asking for the new one.
You may submit your work multiple times -- only the file submitted latest (before the deadline) 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 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.
As for commenting, in each assignment we ask you to include
Computation in the form of software is useful 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 uncomputable!) 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,
Get to the Dr. Racket programming environment, either by downloading it to your personal computer or by using the CS lab. you can use CIS's labs, too -- they likely already have Dr. Racket, or you can download it to your local drive space.
On the CS department's Macs in BkB102 and BkB105, Dr. Racket can be found in the Additional Applications folder:
Once you have Racket running, go to the "Quick introduction" site:
The Racket quick-introduction site
which if 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 6.
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! Sections 7 and 8 are great to try, but not required. We will cover their ideas in detail next week. And we won't use enough Racket in CS 60 to cover sections 9-11 at all.
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.
What to add
To complete this problem, add two functions to your hw0pr1.rkt file:
(define (cboard n color1 color2)
(define (hcomb n color1 color2 color3)
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. 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 (number of eyes?)
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:
Be sure to submit hw0pr1.rkt at the submission site!
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 and/or
to reflect on their running times.
Remember that for each problem below, you
should include at least one additional test in your file, beyond what
we provide. Please be sure these additional tests are clearly
marked with comments. For example, for the erdos
function you might have in your code:
; provided tests
(check-expect (erdos 6) 3)
(check-expect (erdos 7) 22)
; additional tests
(check-expect (erdos 84) 42)
(check-expect (erdos 85) 256)
For this problem define a function, named erdos,
with one argument, N. Thus, your definition will
begin as follows:
(define (erdos N)
This function should compute the following:
Here are a couple of tests to try.
; provided tests
(check-expect (erdos 6) 3)
(check-expect (erdos 7) 22)
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-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.
Write erdos-count, a function of one positive integer argument:
(define (erdos-count N)where erdos-count should return the smallest number of times erdos must be iterated, when started with an input of N, in order to arrive at a value of 1. Let's use the symbol ==> to mean "evaluates to." Then, (erdos-count 3) ==> 7, because
(erdos (erdos (erdos (erdos (erdos (erdos (erdos 3))))))) ==> 1and there are 7 applications of erdos above.
Here are a few Racket tests:
; provided tests
(check-expect (erdos-count 1) 0)
(check-expect (erdos-count 26) 10)
(check-expect (erdos-count 27) 111)
Run-time
The erdos-count
function is said to iterate the erdos function.
As this
link suggests, it is still unknown
whether or not (erdos-count N)
halts for every positive integer N. It does halt for all of
the values of N for which it has been tried.
It is conjectured always to halt, but no one has proven it one way or
the other. Paul Erdos (roughly pronounced air-dish) famously
quipped that "mathematics is not ready for such problems."
The fact that a general-purpose "haltchecking" program would be
powerful enough to answer this century-old
conjecture hints at how strong a capability "haltchecking" actually
is! The state-of-the-art understanding of this 3x + 1
problem is available at this
link.
Given the above background on erdos and erdos-count, include a sentence or two in a comment at this point in your code that answers
Write count1bits, a function of one nonnegative integer argument:
(define (count1bits N)where count1bits should return the number of times the bit 1 appears in the binary representation of N. Remember that N will be a nonnegative integer. Feel free to review binary representation, if you have not seen it for a while - you might also try the tests below, by hand.
Here are a few Racket tests:
; provided tests
(check-expect (count1bits 6) 2)
(check-expect (count1bits 7) 3)
(check-expect (count1bits 42) 3)
Run-time
In a comment near your count1bits function, estimate
its big-O running time for an input whose value is N.
Count the number of times that count1bits is called
recursively as the "steps." Explain briefly.
Write power, a function of two integer inputs (it's OK to presume non-negative integers):
(define (power b p)where b is the base and p is the power: it should evaluate to bp. We also specify that, for this function, b0 should be 1 for any b. Note that using the built-in power function expt is not allowed here -- imagine you're implementing it for the Racket library... . Rather, you should implement power in terms of multiplication, addition/subtraction, and recursion using the formula bp = b*bp-1. If you know a fancier algorithm for computing powers, save it until the next problem!
Here are a few Racket tests:
; provided tests
(check-expect (power 2 5) 32)
(check-expect (power 5 2) 25)
(check-expect (power 42 1) 42)
Run-time
In a comment near your power function, estimate
its big-O running time in terms of b and p.
For this problem, consider multiplications as the "steps"
that are being counted. Explain briefly.
Write fast-power, identical in its inputs and outputs to power:
(define (fast-power b p)where b is the base and p is the power. This time, however, you should use the following idea:
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)
(check-expect (fast-power 42 1) 42)
Run-time
In a comment near your fast-power function, estimate
its big-O running time in terms of b and p.
For this problem, again consider multiplications as the "steps"
that are being counted. Explain briefly.
Then, at the prompt, use the timing command:
(time (fast-power 1 N))
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)These should compute the smallest ("first") factor of N and a list of all the factors of N, respectively. (See the tests.) Note that these add several challenges! First, you'll need to use Racket's lists (there are lots of references in its documentation). In addition, you'll need helper functions, and you'll need to be creative in what those helper functions will be!
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))
Run-time
In a comment near these two functions, estimate
the best-case and worst-case big-O running time of each, in terms of N,
the input.
For this problem, consider the "steps" to be calls to modulo
and/or quotient and/or the / operator.
Explain briefly.
Be sure to submit both hw0pr1.rkt and hw0pr2.rkt at the submission site!