Homework 1 is due Monday, April 12, 2021 at 11:59pm (Chicago Time)

Preliminaries

You will submit your work in a file called hw1.rkt, which should be located in a directory called hw1 in your repository. Unlike Lab 2, you will need to create the directory and file on your machine and then add, commit, and push it to GitLab. Be careful to get the directory and file names right.

To get started, make sure that your local repository is up to date.

cd cs151
git pull

assuming that cs151 is the name of your local repository.

The following shell commands, will get you started. Note the second command (the touch) creates an empty file in the hw1 directory and the third command adds the hw1 directory, which includes the hw1.rkt file (so it will be added too).

mkdir hw1
touch hw1/hw1.rkt
git add hw1
git commit -m "getting ready for homework 1"
git push

At this point, you have added, committed, and pushed an empty file named hw1.rkt and the hw1 directory to your repository on the server. It is important that this file has exactly this name and location, since we will be looking for your work under this name at collection time.

Open the hw1.rkt file in DrRacket. Once you have opened your hw1.rkt file with DrRacket, go to the Language menu, then select Choose Language…​, and then choose "Determine language from source" from the popup menu on the lower left edge of the application window.

Adding boilerplate

The first step is to add the standard comments, require directives, and testing command to the file. Copy the following code into the file and save it.

#lang typed/racket

;; CMSC15100 Spring 2021
;; Homework 1
;; <YOUR NAME HERE>

;; include CS151-specific definitions
(require "../include/cs151-core.rkt")

;; include testing framework
(require typed/test-engine/racket-tests)

;; YOUR CODE HERE

;; run tests
;;
(test)

You should replace "<YOUR NAME HERE>" with your name and your solution to the questions below should replace the

;; YOUR CODE HERE

comment.

Homework Problems

For every function you write, you must preface the function definition with a type signature and a purpose comment. You must also follow the function with tests with check testers (check-expect, check-within, etc.). Write helper functions where it seems like a good idea to do so. All functions need contracts, purposes and tests, even if they are "only" helper functions.

Problem 1

In the game tic-tac-toe, the board is a 3x3 grid and players (starting with the "X" player) alternate placing pieces on the board until either there is a winner or the board is full. Thus a board with \(n_X\) X’s and \(n_O\) O’s is valid if \(n_X + n_O \leq 9\) and \(n_X\) is either equal to \(n_O\) or one greater.

We can generalize the game of tic-tac-toe to arbitrary board sizes (e.g., a \(5\times 5\) board) and, likewise, generalize the notion of a valid board. Write a function valid-board? that takes three arguments: a board size, the number of X’s on the board, and the number of O’s on the board, and returns true if the number of pieces on the board is possible in a game.

Problem 2

Write the following functions

eval-cubic

This function evaluates a cubic function \(f(x) = a x^3 + b x^2 + c x + d\) at a specified x value. Specifically, eval-cubic takes five arguments — a, b, c, d, and x — and returns the value of \(f(x)\). The function should have type Real Real Real Real Real -> Real.

within?

This function tests if two numbers \(x_1\) and \(x_2\) are within a given epsilon of each other (i.e., \(|x_1 - x_2| < \epsilon\)). This function takes three arguments — \(\epsilon\), \(x_1\), and \(x_2\) — and returns #t or #f. It has the type Real Real Real -> Boolean.

on-cubic?

This function takes the a, b, c, and d coefficients of a cubic function, followed by an x value, a y value, and a tolerance epsilon, and determines if the point \((x, y)\) is within epsilon of the point \((x, f(x))\). Its type is

Real Real Real Real Real Real Real -> Boolean

Problem 3

The British income-tax system currently has four brackets. Income in the first bracket (£0–£12,570) is not taxed; income in the second bracket (£12,571–£50,270) is taxed at 20%; income in the third bracket (£50,271-£150,000) is taxed at 40%; and income in the top bracket (above £150,000) is taxed at 45%. Thus, the tax on £75,000 of income is computed by \(0.2 * (50270 - 12570) + 0.4 * (75000 - 50270)\). Taxes are rounded up to the nearest pound.

Write a function income-tax that given an integer income value returns the amount of tax owed. You can use the function

(: exact-ceiling : Real -> Integer)

to round up to the nearest pound.

Problem 4

The Leonardo numbers are the sequence of numbers 1, 1, 3, 5, 9, 15, …​, which are defined by the recurrence:

  • \(L(0) = 1\)

  • \(L(1) = 1\)

  • \(L(n) = 1 + L(n-1) + L(n-2)\) for \(n > 1\)

Write a recursive function leo that takes an integer argument \(n\) and returns 0 if \(n < 0\), and otherwise returns \(L(n)\).

Note that while it is possible to implement this function using tail recursion, that is not required.

Submission Instructions

Your solution to the assignment must be pushed to the GitLab server by Monday, April 12, 2021; we do not accept late work. Remember that to submit your work you will have to add and commit it to your local repository, and then push your changes to the server. You can verify that your work has been submitted by using the web interface to the server.

We strongly recommend pushing your code after you write and test each function; do not wait to the last minute to discover that you cannot commit your work for some reason!! Only your last commit before the deadline will be evaluated by your graders. Note, however, that you should not submit code that has syntax or type errors in it. If you cannot figure out how to fix a particular type error, comment out the offending code and include a note for the grader.

For the present, do not worry about functions being passed bogus inputs, e.g., a negative income. We will deal with erroneous arguments to functions later in the quarter.