Assignment 1: ==Values==
------
This is a **solo, Gradescope assignment**—you will submit an individual submission of one written text file and one Racket file on Gradescope.
### Change log
I will avoid making changes to the assignment after it is posted, but any necessary changes will be added here:
- [9/13]: add more detail to `steamroll` description, add RackUnit link.
- [9/15] Clarify that you can write/use helper functions. Suggest `append` for `steamroll`. Add tail recursive `reverse` for `deep-rev-tail`.
# Setup
As with Assignment 0, I suggest you complete this assignment in DrRacket. For this assignment, your Racket file should start with `#lang racket`.
:::success
Create 2 files:
1.`README.txt` (or `README.md`) for your written answers.
2.`a1.rkt` for your Racket code.
:::
:::info
For the Racket problems, you should write Racket solutions using primarily the operators and functions we have seen so far in class. Do not use Racket library functions that accomplish the full task, even if they exist.
:::
## Testing
:::success
I suggest using the [RackUnit](https://docs.racket-lang.org/rackunit/quick-start.html) unit testing library with `(require rackunit)` to write `check-equal?` tests for your functions. Starting with the next assignment (A2: Functions), your tests will be an explicit part of your grade.
:::
---
# Problem 1: Pondering side effects
Answer the following questions in your `README` text or Markdown file.
In class, we described a side effect as “a behavior other than producing a value”.
**Written 1.1:** Write 3 individual Python (or Java) functions that exhibit different side effects. Use comments to label and explain each side effect. Try to make the side effects as distinct as possible.
**Written 1.2:** Do you think variable declaration in Racket is a side effect? Why or why not? _(Note: your explanation here matters more than the yes/no answer.)_
---
# Problem 2: Is that a value?
Answer the following question in your `README` text or Markdown file.
Does Racket allow lists to contain elements that are not values? Provide 2 example Racket expressions and their results from the interactions window to justify your answer (explain each example).
---
:::info
The following problems should all be completed in `a1.rkt`.
Note that for this assignment on, you can (and often should) write and call your own helper functions.
:::
# Problem 3: `contains-multiple?`
Write a function, `(contains-multiple? m ns)`, that takes an integer `m` and a list of integers `ns` and returns true if `m` evenly divides at least one element in the list; and otherwise false.
Beyond what we saw in class, you may find the following Racket functions useful:
- `modulo` : [documentation](https://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._modulo%29%29) (can be used to check divisibility)
For example:
```racket
> (contains-multiple? 5 (list 8 10 14))
#t
> (contains-multiple? 3 (list 8 10 14))
#f
> (contains-multiple? 5 null)
#f
```
---
# Problem 4: `all-contain-multiple?`
Write a function, `(all-contain-multiple? m nss)`, that takes an integer `m` and a list of lists of integers `nss` and returns true if all lists of integers that are elements in nss contain at least one integer that is a multiple of `m`; and otherwise false. You should use your prior function as a helper function.
For example:
```racket
> (all-contain-multiple? 5 (list (list 17 10 2) (list 25) (list 3 7 5)))
#t
> (all-contain-multiple? 3 (list (list 17 10 2) (list 25) (list 3 7 5)))
#f
> (all-contain-multiple? 3 null)
#t
```
If you are surprised by the result of `(all-contain-multiple? 3 null)`, consider that in general, "all" statements over an empty set (also known as [_universal quantification_](https://en.wikipedia.org/wiki/Universal_quantification)) are, by definition, true.
---
# Problem 5: `mergesort`
Implement a function that sorts a list of numbers using the merge sort algorithm. Define helper functions as appropriate.
:::info
As a reminder, the high-level algorithm for merge sort is:
- Consider the empty or single-element list sorted.
- For lists longer than 2, divide the list (roughly) in half. Recursively sort each half.
- `merge` the two sorted halves into a single list in a linear pass, making sure to keep the elements sorted.
For this problem, you can reference the [CS230 materials](https://docs.google.com/presentation/d/1f9FQzuL1hVJWyigZwsGsRLLYhzC_FhPr/edit#slide=id.p18), but please avoid looking at other implementations of `mergesort`.
:::
You should not use any library sorting functions, however, you may find the following Racket functions useful:
- `length` : [documentation](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._length%29%29)
- `floor` : [documentation](https://docs.racket-lang.org/reference/generic-numbers.html#%28def._%28%28quote._~23~25kernel%29._floor%29%29)
- `take` : [documentation](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._take%29%29)
- `drop` : [documentation](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Flist..rkt%29._drop%29%29)
---
# Nested lists
Racket has two core operators for adding items to the front of a list. `append` combines lists (while we did not see this in class, the built in `append` can take any number of argument lists). `cons` takes two arguments and produces a pair in the form of a `cons` cell (and canonically, `empty` represents the empty list). Because the subset of Racket we have been working with does not have mutation, neither can modify an existing list.
These Racket operators have a funny property: they do not always produce lists in the canonical sense. If their final argument is not a list, they produce an improper list, indicated with a period between the head and tail of the pair:
```racket
> (cons 5 empty)
`(5) ; <- a proper list
> (cons 5 6)`
`(5 . 6) ; <- improper list, but still a pair
```
:::warning
To access the first and second items of an improper list, use the following two functions we mentioned in class. These function names are historical artifacts from the original implementation of LISP, where they were shorthands access the two halves of an IBM 704 CPU registers.
- [car](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._car%29%29) returns the first element of a cons cell (or pair).
- [cdr](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28quote._~23~25kernel%29._cdr%29%29) returns the second element of a cons cell (or pair).
You can use these functions throughout the assignment.
:::
_As we'll see later, pairs can be useful in their own right_.
---
# Problem 6: `proper-append`
Consider a version of append called `proper-append` that is guaranteed to return a proper list (i.e., throws a dynamic error if its arguments are not proper lists). Think through the recursion involved in terms of efficiency. In your `README`, answer: do you think `proper-append` can have the same asymptotic (Big-O) running time as the `my-append` from the class notes? Why or why not?
Be sure to consider the case where the input lists have different sizes.
_(Note: you do not need to implement `proper-append`.)_
---
# Problem 7: `steamroll`
Write a function `steamroll` that takes a nested, potentially improper list and produces a list with all items within. There should be *no* `cons` cells in the final produced list: the final list should be a flattened proper list.
Helpful functions:
- The `cons?` function returns `#t` if its argument is a `cons` cell and `#f` otherwise.
- The `list?` function returns `#t` if its argument is a proper list and `#f` otherwise.
- `append`, either Racket's built-in version or the `my-append` helper we wrote in class.
Examples:
```racket
> (steamroll '())
'()
> (steamroll (list 1 (list 2)))
'(1 2)
> (steamroll (cons 1 2))
'(1 2)
> (steamroll
(list 1
(list 1 2 4)
(list (list (list 2 (list 5))))))
'(1 1 2 4 2 5)
```
---
:::warning
The following two problems will make sense after Monday's *Tail Recursion* lecture.
:::
# Problem 8: `dot-product-tail`
Using direct tail recursion, write a function `dot-product-tail` that calculates the [dot product](https://en.wikipedia.org/wiki/Dot_product) of two lists of numbers: the dot product of two lists $(x_1 ... x_n)$ and $(y_1 ... y_n)$ is the sum of products $x_1*y_1 + ... + x_n*y_n$. You can assume that the two lists have the same length and that the dot product of two empty lists is 0.
Examples:
```racket
> (dot-product-tail `() `())
0
> (dot-product-tail `(1 2 3) `(4 5 6))
32
```
---
# Problem 9: `deep-rev-tail`
Here is a tail-recursive function that reverses a basic proper list:
```racket
(define (reverse lst)
(letrec
((helper
(lambda (lst acc)
(if (empty? lst)
acc
(helper (rest lst) (cons (first lst) acc))))))
(helper lst empty)))
```
This will not necessarily be useful as a helper function, but its structure may help you approach this problem.
Write a new function, `deep-rev-tail`, that takes a proper list `x` and deeply reverses it using tail recursion. If `x` is an atom (any non `cons` cell value), `deep-rev-tail` should return it as is. If `x` is a `cons` cell, `deep-rev-tail` should assume it represents a proper list, reverses the list, and deeply reverse any lists that are elements in `x`.
Note that the most concise and efficient implementations of this function will need **both** tail recursion and natural recursion!
Examples:
```racket
> (deep-rev-tail (list 1))
'(1)
> (deep-rev-tail empty)
'()
> (deep-rev-tail (list 1 2 3 4 5))
'(5 4 3 2 1)
> (deep-rev-tail (list 1 (list 2 3) (list 4 5 (list 6 7 8))))
'(((8 7 6) 5 4) (3 2) 1)
```
---
# Grading
:::success
In your README, also report:
**Written:** Roughly how long did this assignment take you (in hours)?
:::
This assignment is worth 100 points, broken down by:
:::info
- 8: Problem 1
- 6: Problem 2
- 8: Problem 3
- 8: Problem 4
- 20: Problem 5
- 5: Problem 6
- 15: Problem 7
- 10: Problem 8
- 20: Problem 9
:::
# Submission
Submit the following 2 files on Gradescope:
:::success
- `a1.rkt`
- `README.txt` (or `README.md`)
:::
# Attribution
Some exercises adapted from previous CS251 versions by Ben Wood and Carolyn Anderson.