Administrative

The purpose of this homework is to familiarize yourself with the various tools that will be used throughout the course, and to get a feeling of basic programming in Racket. Note that the submission system will not allow you to submit your code if it does not follow certain requirements. For example, you will not be able to submit code that doesn’t have the required definitions, or doesn’t bind them to appropriate value types, or code that contains lines that are longer than 79 characters. In addition, you are required to have tests that completely cover your code, otherwise your submission will be penalized severely (the server will tell you about it when you submit, and resubmissions are always fine).

In this particular homework, the server will perform additional tests over your code, which will require you to come up with correct solutions to be able to submit. This means that you will generally be graded on contracts and purpose statements (both in comments), other comments, style, test quality, etc. Correctness will play a very small role here, since everyone is expected to be able to solve these questions.

The first thing you will need to do is to download and install Racket, then the course plugin, and then create a handin account. This is described in details in the Software section. (Note that if you use department machines in the lab, then Racket is probably pre-installed.)

Shortly after you install the plugin and register, you will be added to the course piazza, which will allow you to post the required test message (see below). Note: do not email requests to be subscribed to the piazza, it will be done after you register with the handin server. (It’s done manually, so “shortly” can mean a number of hours, maybe even a day.)

You might want to consult How to Design Programs (2nd Edition) and the Class Notes before writing your code. Specifically, if you haven’t done fundies, or if you did, but forgotten most of it, then you might be confused about how to make up lists and what are symbols. In this case, you should really read this HtDP page about symbolic data.

For this problem set (and only for this), you are required to set the language level to “Intermediate Student”. This will allow you to use the Stepper to debug your code, and more importantly: learn how Racket evaluates it. However, this language includes a bunch of things that we do not know about — not until we learn about them explicitly. Things that you should not use even if you know about them include lambda, letrec, and require. (If you don’t know about them then you have no problems, if you do, then pretend that you’ve never heard about them.)

This homework is for individual work and submission.

Submitted code should have comments that describe each function and its type, as well as enough test cases for complete coverage (DrRacket indicates covered expressions with colors for covered and uncovered source code, unless your code is completely covered). Your tests should have the form of (equal? <expected> <expression>), except for boolean functions (predicates) where they should be either <expression> or (not <expression>). (Note that this is different from what you’ve used in the past; in the next homework we will switch to the course language that has its own testing facility.)

Important reminder: Your tests should cover your whole code, otherwise the server will penalize your submission heavily. You should not have any uncovered expressions after you hit “Run” — it should keep the same colors, indicating complete coverage. Furthermore, the server will run its own tests over your code, which means that you will not be able to submit code that does not work.

General note: do not duplicate code! If there is an expression that is used in multiple places, then you should use let.

Another important note: remember we’re using a computer system for submission. You don’t need to write any meta information at all. Examples of things that we don’t want to see in the submissions because the system already has them: the homework number, your name, your id, the submission date and/or the time, the due date and/or the time. Also, examples of things that we don’t want to see in the submissions because they’re obvious: the course name and/or number, the instructor name, the grader names, the department name, the university name, etc. Again, all of these are things that we don’t need. Save your bits.

Furthermore: grading is done anonymously, so please do not write your name in your submission code!

Questions

1. Read the Academic Integrity page, and indicate your agreement as specified on the page.

2. Once you’re subscribed to the course piazza group, you will see a test post for this homework. Post a followup note to this post. Make sure that it actually appears, otherwise you will not get the credit for posting. (You only need to make some post, so if you’ve already posted a question, a reply, or a note, then you don’t need to post another followup.)

   See the Piazza Section for further information. Note that you will not be able to view or post on piazza until you are subscribed, and you will be subscribed to it only after you install the course plugin and create your account — so make sure you do that first. Once you do this, you will get a notification when you’re on the piazza. Again, do not try to subscribe to it by yourself.

3. For the purpose of getting to know your names better, I use the picture you have on record with the university. These pictures are often outdated which makes them not so helpful. If you think that your university picture falls under that category, I would appreciate an up-to-date selfie which you can upload here. If you do, make sure to fill-in your name before you upload the image file, and please use something recognizable (eg, a high-enough resolution phone selfie is good; nice profile pictures can often be as bad as an outdated picture when it comes to recognizing you). To be clear, this is not required, and these pictures are not made public in any way — not even in the class context (so other students will not see it too). The goal is to recognize you and learn your name, nothing more.

4. Define a near? function that consumes three integers and determines whether they are all “near” each other, where near means that they are at most within an interval of 2. For example, (near? 1 2 3) would return #t because all of the numbers are within the 1–3 interval. Note that the numbers might not be sorted, and they might not be unique. (Hint: you can use the min and max functions.) Here are three more examples, written in a form of a test that you can use:

   (near? 1 -1 1)
   (not (near? 2 -2 2))
   (not (near? 0 2 3))

   Don’t forget to write a proper contract, a purpose statement, and sufficient tests that cover the whole code and also verify corner cases.

   (See above for how test cases should be written.)

5. Remember that lists are defined inductively as either:

   • An empty list — null
   • A cons pair (sometimes called a “cons cell”) of any head value and a list as its tail — (cons x y)

   A “Listof T” would be similar, except that it will use T instead of “any”.

   With this in mind, define a count-xs function that consumes a list of symbols and returns the number of occurrences of the symbol x in the list. (The actual symbol x, not some input argument.)

   (Do not use filter or length.)

6. Define an ascending? function that determines whether a list of numbers is sorted in ascending order. This means that each element is smaller than or equal to the next one in the list. Again, make sure that you write a proper contract, purpose statement, and tests.

   (Do not use sort or apply.)

7. Finally, implement a zip2 function that does the following:

   • It consumes two arguments that are lists of equal length, say (Listof A) and (Listof B) for some types A and B. (Note that you cannot express the fact that they are equal-length lists with the way we write contracts, so make sure you mention that in the purpose statement.)

   • The result is a list that contains two-element lists from the first and the second lists respectively. Use (List ? ?) to specify “a two-item list of ? and ?” in your contract. (You need to replace the ?s with appropriate types.)

   You can assume here too that the input is always valid. Do not use map.

   For example, here is a use of this function, in a test form (note that we’re now using equal? to compare a nested list structure):

   (equal? '((1 a) (2 b) (3 c))
           (zip2 '(1 2 3) '(a b c)))

   (This can be used as a test, and it will probably even cover your code completely, but you need more tests. Specifically, you need to test corner cases.)

   Make sure that you write a correct contract!

8. Define minutes-spent as the number of minutes you spent on your homework. Please specify a reasonable estimate here and in future homework, since these values help in determining homework weights.