# Exam Prep 7: Scheme

Students from past semesters wanted more content and structured time to prepare for exams. Exam Prep sections are a way to solidify your understanding of the week's materials. The problems are typically designed to be a bridge between discussion/lab/homework difficulty and exam difficulty.

**Reminder:** There is nothing to turn in and there is no credit given for attending Exam Prep Sections.

We try to make these problems **exam level** , so you are not expected to be able to solve them coming straight from lecture without additional practice.
To get the most out of Exam Prep, we recommend you **try these problems first on your own** before coming to the Exam Prep section, where we will explain how to solve these problems while giving tips and advice for the exam. Do not worry if you struggle with these problems, **it is okay to struggle while learning**.

You can work with anyone you want, including sharing solutions. We just ask you don't spoil the problems for anyone else in the class. Thanks!

You may only put code where there are underscores for the codewriting questions.

You can test your functions on their doctests by clicking the red test tube in the top right corner after clicking Run in 61A Code. Passing the doctests is not necessarily enough to get the problem fully correct. You must fully solve the stated problem.

### Q1: Slice It!

**Difficulty: ⭐⭐**

Implement the `get-slicer`

procedure, which takes integers `a`

and `b`

and returns an *a-b slicing function*. An `a-b`

slicing function takes in a list as input and outputs a new list with the values of the original list from index `a`

(inclusive) to index `b`

(exclusive).

Your implementation should behave like Python slicing, but should assume a step size of one with no negative slicing indices. Indices start at zero.

**Note:** the skeleton code is just a suggestion. Feel free to use your own structure if you prefer.

**Your Answer**Run in 61A Code

**Solution**

```
(define (get-slicer a b)
(define (slicer lst)
(define (slicer-helper c i j)
(cond
((or (null? c) (<= j i)) nil) ((= i 0) (cons (car c) (slicer-helper (cdr c) i (- j 1)))) (else (slicer-helper (cdr c) (- i 1) (- j 1))))) (slicer-helper lst a b))
slicer)
; DOCTESTS (No need to modify)
(define a '(0 1 2 3 4 5 6))
(define one-two-three (get-slicer 1 4))
(define one-end (get-slicer 1 10))
(define zero (get-slicer 0 1))
(define empty (get-slicer 4 4))
(expect (one-two-three a) (1 2 3))
(expect (one-end a) (1 2 3 4 5 6))
(expect (zero a) (0))
(expect (empty a) ())
```

### Q2: Partition Options

**Difficulty: ⭐⭐**

First, write the procedure `combine`

, which takes in lists `lst1`

and `lst2`

, as well as a value `x`

, and outputs a new list with `x`

before each item of `lst1`

, and then all elements of `lst2`

unmodified. For examples, see the doctests.

Then write the procedure `partition-options`

, which takes in positive integers `total`

and `biggest`

and outputs a list of lists, in which each inner list contains numbers no larger than `biggest`

that sum to `total`

.

**Note:** The skeleton code is just a suggestion; feel free to use your own structure if you prefer.

**Your Answer**Run in 61A Code

**Solution**

```
; helper function
(define (combine lst1 lst2 x)
(if (null? lst1) lst2
(cons (cons x (car lst1)) (combine (cdr lst1) lst2 x))))
(expect (combine '((1)) '((3) (4 5)) 0) ((0 1) (3) (4 5)))
(expect (combine '((1) (2 3) (3)) '((4 5) (6)) 'a) ((a 1) (a 2 3) (a 3) (4 5) (6)))
(define (partition-options total biggest)
(cond
((= 0 total) '(())) ((or (< total 0) (= 0 biggest)) '()) (else (let
((with (partition-options (- total biggest) biggest)) (without (partition-options total (- biggest 1)))) (combine with without biggest)))))
(expect (partition-options 2 2) ((2) (1 1)))
(expect (partition-options 3 3) ((3) (2 1) (1 1 1)))
(expect (partition-options 4 3) ((3 1) (2 2) (2 1 1) (1 1 1 1)))
```

### Q3: Find It!

**Difficulty: ⭐⭐**

Implement the `find-in-tree`

procedure, which takes a Scheme tree `t`

, a target value `goal`

and returns a list containing the node values on a path from the root of `t`

to a node containing `goal`

. If no such path exists, `find-in-tree`

returns an empty list.

Complete `find-in-branches`

for ease of implementation. `find-in-branches`

takes a list of branches `bs`

and a value `goal`

and returns a list containing the node values on a path from any branch to a node containing `goal`

. If no such path exists, `find-in-branches`

returns an empty list.

The Scheme tree ADT is specified at the top of the skeleton code.

**Note:** The skeleton code is just a suggestion; feel free to use your own structure if you prefer.

**Your Answer**Run in 61A Code

**Solution**

```
(define (tree label branches) (cons label branches))
(define (label t) (car t))
(define (branches t) (cdr t))
(define (is-leaf t) (null? (branches t)))
(define (find-in-tree t goal)
(if (eq? (label t) goal) (list goal) (let ((path (find-in-branches (branches t) goal)))
(if (null? path) nil (cons (label t) path)))))
(define (find-in-branches bs goal)
(if (null? bs) nil
(let ((path (find-in-tree (car bs) goal))) (if (null? path) (find-in-branches (cdr bs) goal) path))))
; DOCTESTS (no need to modify)
(define t1 (tree 1
(list
(tree 2
(list
(tree 5 nil)
(tree 6 (list
(tree 8 nil)))))
(tree 3 nil)
(tree 4
(list
(tree 7 nil))))))
(expect (find-in-tree t1 7) (1 4 7))
(expect (find-in-tree t1 1) (1))
(expect (find-in-tree t1 12) ())
```