Teaching 2500 F '12 Assignments The Hand In Set 1 Set 2 Set 3 Set 3h Set 4 Set 4h Set 5 Set 5h Set 6 Set 6h Set 7 Set 7h Set 8 Set 9 Set 8h Set 10 Set 9h Set 11 Set 12 Set 10h

### Problem Set 9

Due date: 11/7 @ 11:59pm

Programming Language: Intermediate Student Language with lambda

This problem set has two main goals: first, to practice the use of abstractions; second, to learn how to edit programs that you have already written, an essential skill for any programmer.

Problem A1:

#### Part 1:

Complete the following parametric data definition for a non-empty list:

```    ; an [NEListof X] is one of...
```

#### Part 2:

Design the function `all-int-squares` which takes in a non-negative integer n and returns a `[NEListof Number]` with the squares of all integers from 0 to n, inclusive (i.e. including both 0 and n).

#### Part 3:

Write down the parametric data definition for a `UOP` (unary operator) which is any function that takes in a Number and returns a Number. Then abstract `all-int-squares` to `all-int-results` which takes in a non-negative integer n and a `UOP` o and returns a ```[NEListof Number]``` with the results of applying o to all integers from 0 to n, inclusive. Redesign your `all-int-squares` to use `all-int-results`.

#### Part 4:

Design `all-int-doubles` which uses `all-int-results` and a helper `UOP`, defined with `local` inside `all-int-doubles`, that multiplies its input by two.

Problem A2:

#### Part 1:

Write a function `find-string` that takes in a `[Listof String]` and a `String` and that reuturns a Boolean, true if and only if the given string was in the list.

#### Part 2:

Abstract `find-string` to `generic-find-string` so that the string comparison operation it uses is a parameter. Then use this abstraction to define `find-string-case-sensitive`, which should operate the same way as the original `find-string`, and `find-string-case-insensitive`, which has the same contract as `find-string` but which ignores the case of alphabetic characters when comparing strings (i.e. the character `a` is considered the same as `A` and so on; non-alphabetic characters must still match exactly).

Problem A3:

Revise your Missile Defense project. Be sure to fix any and all problems that your graders have (or would have) discovered. Note: the ambiguities in the original assignment regarding whether bullets should explode when they hit missiles and the possible angular paths of missiles have been corrected in the text of the assignment. Your revisions should implement the correct functionality.

Next, you are to use `local` and "loops" (abstractions such as `map`, `foldr`, `filter`, etc.) wherever your functions may benefit from them, especially for the lists of objects in your project.

You should notice that the length of your program decreases considerably.

If you have a new partner you actually have two different code bases from which you can start. You are free to pull code from both.

Problem A4:

#### Part 1:

Develop data definitions for binary trees of Symbols and binary trees of Numbers. The numbers and symbols should occur at the leaf positions only.

Create two instances of each, and abstract over the data definitions.

Design the function `height`, which consumes any binary tree of either type and computes its height. That is, the maximum number of nodes from the root of the given tree to any leaf (including the leaf, but not including the root node in the count). Here's some tests to further explain:

```      (check-expect (height 5) 0)
(check-expect (height (make-node 'yes (make-node 'no 'maybe))) 2)
```

#### Part 2:

A leafy binary tree is a binary tree with the symbol `'leaf` at its leafs.

Design a function that consumes a natural number `n` and creates (a list of) all leafy binary trees of height `n`.

Hint: Design a function that consumes a natural number `n` and creates (a list of) all leafy binary trees of height equal or less than `n`.

Note: this is not about abstraction; it's just a reminder that more interesting (and complex) programs are around the corner.

 last updated on Sun Dec 2 14:52:34 EST 2012 generated with Racket