►COMP 115:   How to Design Programs
▼Problem Sets
►Problem Set 10:   Abstraction
On this page:
1 Review
2 Removing
3 Tabulating
4 Having
5 Non-empty lists
6 Trees
    ← prev  up  next → 

Problem Set 10: Abstraction

Submit this assignment to ps10 on Handin.

This problem set is due Tuesday at 10PM EST.

Note: Whenever you write a function in this class, follow the design recipe. You will be graded accordingly.

Whenever you are asked to abstract from some functions, follow the abstraction recipe for functions. For Step 5, you do not need to submit the original versions of the functions. (Instead, submit the redefined versions.)

1 Review

Here is the abstraction recipe for functions:

  1. Design at least 2 similar functions.

  2. Identify inessential differences and revise functions to remove them.

  3. Identify essential differences and pick input names for each of them.

  4. Design the abstraction by replacing differences with input names.

  5. Redefine the original functions using the new abstraction.

A few more reminders:

  • Remember to change the language in DrRacket to Intermediate Student.

  • Step 2 often involves designing helper functions.

  • Step 4 requires writing a new signature and purpose statement. Make sure that the signatures and purpose statements of the original functions are instances of the signature and purpose statement of the abstraction.

2 Removing

Problem 1. Abstract from remove-even and remove-negative in Problem Set 9: Similarities. Call your new abstraction remove-because.

3 Tabulating

Problem 2. Abstract from tab-sin and tab-sqrt and tab-sqr in Problem Set 9: Similarities. Call your new abstraction tabulate.

4 Having

Problem 3. Abstract from has-< and has-string=? in Problem Set 9: Similarities. Call your new abstraction has.

5 Non-empty lists

Problem 4. Abstract from NEListOfNumbers and NEListOfBooleans and NEListOfStrings and NEListOfPosns in Problem Set 9: Similarities. Call your new abstraction [NEListOf X].

Problem 5. Write the template for processing a [NEListOf X].

Problem 6. Abstract from shortest-string and closest-posn in Problem Set 9: Similarities. Call your new abstraction most.

Problem 7. Using your new abstraction most, design a function shortest-list that takes a nonempty list of lists of images as input and returns the shortest list. (If multiple lists are equally short, return any of them.) Caution: Do not confuse NEListOf with ListOf.

6 Trees

Problem 8. Abstract TreeOfNumbers and TreeOfStrings in Problem Set 9: Similarities into a single data definition [TreeOf X] for trees of any kind of data.

Problem 9. Write the template for processing a [TreeOf X].

Problem 10. Abstract sum-tree and prod-tree and count-tree into a single function named reduce-tree.

    ← prev  up  next →