If you need help reviewing Scheme, take a look at these resources:

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

## What would Scheme print

### Question 1

For the following questions, write the value that the expression
evaluates to if you type it into `scm`

. If the expression contains a
function (or multiple), write "FUNCTION" in place of that function. If
the expression causes an error, write "ERROR".

```
scm> (cons 1 (cons 2 (cons 3 (cons 4 nil))))
______(1 2 3 4)
scm> (cons (cons (cons 3 2) 1) (cons 4 nil))
______(((3 . 2) . 1) 4)
scm> (cdr (cons (cdr (list 1 2)) (cons 3 (cons 4 nil))))
______(3 4)
scm> (define lst (cons (lambda (x) (cons x x)) nil))
scm> ((car lst) lst)
______((FUNCTION) FUNCTION)
scm> (define (x) (lambda (x) (list x x)))
scm> (((car ((x) x))) 4)
______(4 4)
```

## Code-Writing questions

### Question 2

Implement a function `count-stairways`

, which takes a number `n`

as an
argument. Assuming you can only take 2 or 3 steps at a time, return the
number of ways you can reach the top of a staircase with `n`

stairs.

This is different than the usual `count-stairways`

— notice that this
time, we can only take 2 or 3 steps, rather than 1 or 2.

```
(define (count-stairways n)
; YOUR CODE HERE
)
; Tests
scm> (count-stairways 1)
0
scm> (count-stairways 4)
1
scm> (count-stairways 5)
2
scm> (count-stairways 8)
4
```

```
(define (count-stairways n)
(cond ((= n 1) 0)
((or (= n 2) (= n 3)) 1)
(else (+ (count-stairways (- n 2))
(count-stairways (- n 3))))))
```

### Question 3

Implement a function `count-serpinski`

, which takes a numbero `depth`

as an argument. The function calculates how many triangles are
contained in a Serpinski's triangle with the given depth. See the tests
for examples.

How can you use recursive calls on *n-1* to build your answer for *n*?

```
(define (count-serpinski depth)
; YOUR CODE HERE
)
; Tests
scm> (count-serpinski 1)
1
scm> (count-serpinski 2)
5
scm> (count-stairways 3)
17
scm> (count-stairways 4)
53
```

```
(define (count-serpinski n)
(if (= n 1)
1
(+ 2 (* 3 (count-serpinski (- n 1))))))
```

The recursive call can be derived as follows:

- There are three smaller
*n-1*serpinski triangles at each of the corners - There are two additional triangles drawn — the triangle in the center, and the overall triangle.

## Fill-in the blank questions

Fill in the blanks for the `construct`

function. It takes a value and a
list of lists as arguments. It returns a new list of lists, where each
element is a list from the old list, but with the value added to the
front.

```
(define (construct value lists)
(if ______
______
(cons _____________
_____________)))
)
; Tests
scm> (define lists '((10) () (4 3) (2 5 3)))
lists
scm> (construct 6 lists)
((6 1) (6) (6 4 3) (6 2 5 3))
scm> (construct 6 '())
()
```

```
(define (construct value lists)
(if (null? lists)
nil
(cons (cons value (car lists))
(construct value (cdr lists)))))
```