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 2012generated with Racket