Homework #1: Intro
Out: ? Thursday, September 14th, Due: ? Thursday, September 21st, 11:00pm

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, 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 and then the course plugin. When this is done (and you restart DrRacket), you will be able to register for homework submission, as described in the Software Section. (If you work in the lab, Racket should already be installed.)

Shortly after you install the plugin and register, you will be added to the course piazza group, which will allow you to post the required test message (see below). Note: do not email requests to be subscribed to the piazza group, 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 and the Class Notes before writing your code.

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 explicitely. Things that you should not use even if you know about them include lambda and letrec. (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 general 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.

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 a note.)

    Reminder: the piazza group is https://piazza.com/northeastern/fall2017/cs44005400/home, and see also the Piazza Group Section. Note that you will not be able to view or post on the piazza group until you are subscribed to it, and you will be subscribed to it only after you installed the course plugin and created an account — so make sure you do that first. Once you do this, you will get a notification when you’re on the piazza group. Again, do not try to subscribe to it by yourself.

  3. Define a function called bin4-to-num. It consumes four binary digits (0 or 1) ordered from the least to the most significant, and produces the corresponding decimal number. For example, here is a test case that demonstrates how it works which you can use:

    (equal? 13 (bin4-to-num 1 0 1 1))

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

    Note that for this homework, test cases are simple toplevel expressions that should all evaluate to #t.

  4. Define a gcd2 function which takes two non-negative integers a and b and computes their greatest common divisor. This must be done with the following algorithm:

    1. If a=0, return b.
    2. If b=0, return a.
    3. If a and b are both even, then gcd2(a,b) = 2*gcd2(a/2,b/2).
    4. If a is even and b is odd, then gcd2(a,b) = gcd2(a/2,b).
    5. If a is odd and b is even, then gcd2(a,b) = gcd2(a,b/2).
    6. If a and b are both odd, and a>=b, then gcd2(a,b) = gcd2((a-b)/2,b).
    7. If a and b are both odd, and a<b, then gcd2(a,b) = gcd2((b-a)/2,a).

    You should use even? and odd? to check if an integer number is even or odd. For example, the expected value of (gcd2 378 144) is 18 and (gcd2 216 612) is 36. Don’t forget to write a proper contract and purpose statement, and to properly test the code (the tests that are given here are useful, but you will need to get complete coverage, and it is always a good idea to make sure that you test potential corner cases).

    This is called the “Binary GCD” algorithm — if you’re interested, you can read more about it on Wikipedia.

  5. Implement an all-even? function, which consumes a list of integers, and returns #t if all integers are even.

    Hint: The common way to deal with an empty input in these kind of functions is to return #t since all of the empty list’s items are trivially even.

    Note that the function in this case returns a boolean, so you can simply call it in ways that expect a true result. In other words, write:

    (all-even? (list 2 4 6 8))
    (not (all-even? (list 1 3 5 7)))

    instead of

    (equal? #t (all-even? (list 2 4 6 8)))
    (equal? #f (all-even? (list 1 3 5 7)))

    (Note: do not use andmap to do this.)

  6. One of the most useful sorting algorithms is merge sort. Implementing it requires a merge function: a function that receives two sorted lists, and returns a single sorted list with all items from the two input lists. Implement such a merge-lists function. For simplicity, you are required to deal only with numbers, and assume that the input lists are (and the output list should be) sorted in ascending order.

    (Note: you cannot use sort for this.)

  7. In the definitions window, define my-picture — bind it to the number next to your picture in the pictures that were taken in class or the one from the university records if it listed there. If you appear in several pictures, choose the one that looks best and/or the one you like most, but please make sure that you are recognizable in your chosen picture. Also, define my-other-pictures as a list of numbers for all of the other picture numbers that you appear on (as the main person, ignore pictures that show you in the background of someone else). If there are none, bind it to null or '().

    Again, please make sure that you are recognizable — some of these pictures are barely visible, or you might have your nose burried in your phone, or your university picture is something that your mother took when you graduated kindergarten and dug out of the basement. If there is no good picture of you, please email us a good recent picture of yourself, or catch me after class so I’ll take a new one. If your university picture is not there, and you think that it’s better, then tell me about it and I’ll see if I can get it. If you send me one, then please choose something that is not tiny, and keep in mind that your name will appear at the bottom, so have some space under your face. Once you do that, I will add it to the above, and you will have a number to use. (As long as there is no picture, you can use 0, and say that there is no proper picture in a comment.)

  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.