Data Definitions and Program Schemas

Comp 210

50-minute in-class quiz

Please write your solutions in the space provided.

1. Sorting is one of the most common operations done by computers. One way to sort is to maintain a list of numbers in sorted order and develop a function for inserting a new number into its correct position in the sorted list.
   1. (15 pts) Give the program schema for a function Insert-5 that takes a single list l as input.

   2. (15 pts) If l is sorted in ascending order, complete your function Insert-5 to return a sorted list containing all the elements of l and the number 5. In other words, insert 5 in its proper location in l.
2. In class, we constructed family trees for ancestors. For this problem, we will construct family trees for descendants. A descendant tree consists of the name of an individual and trees for up to two children.

   <dtree> := (nochild name) |
              (onechild name only) |
              (twochild name first second)

   where name is a symbol and only, first, and second are dtrees.
   1. (5 pts) Give the define-structure statements that can be used to implement this data type in Scheme. List the constructors, predicates, and selectors created by these define-structures.
   2. (15 pts) Give the program schema for a function size that takes as input a descendant tree t.
   3. (15 pts) Complete your schema assuming that size returns the number of people in the descendant tree t.
   4. (15 pts) Use your constructors to build an instance of a descendant tree that consists of a person named Joe who has a first born son Grant and second born daughter named Beth.
3. In the process of writing a a controller for a stop light, we have defined the following types of data:

   <color> := (green) |
              (yellow) |
              (red)
   <condition> := (wet) |
                  (dry)

   1. (5 pts) Give the define-structure statements that can be used to implement these two data types in Scheme. List the constructors, predicates, and selectors created by these define structures.
   2. (15 pts) Give the program schema for a function proceed? that takes as input a variable signal of type color and a variable weather of type condition.