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 8

Due date: 10/29 @ 11:59pm

Programming Language: Intermediate Student Language

Problem A1:

We grade your exams in batches, where we (i.e. your Professors and Teaching assistants) are each assigned one or more problems to grade and a pile of exams. When we're done with that pile we turn in a list of the grades for those problems. At the end we add up the grades for each batch to get the total score for each student, and then we make a single pile of all exams sorted in alphabetical order by student name.

Here is the data definition for an exam grade and lists thereof:

``` ;; An ExamGrade is a (make-grade String String Number)

;; A LOEG (list of exam grades) is one of:
;; - empty
```
Each exam grade records the first and last name of the student and that student's points on the part of the exam that was graded. Before the grade-adding phase these will correspond to the problems graded in each batch. After the adding phase they will represent the total exam scores.

Exercise 1: Design a function, `sum-grades`, that takes two equal-length lists of exam grades as input, both containing the same names in the same ordering, and produces a list of exam grades that sum up the grades in the input lists. Your function should produce a helpful error message if the input lists were not of the same length or did not contain the same names in the same order.

Here is an example (you should develop more to fully test your code):

```(define b1 (list (make-grade "Seth" "Alexander" 10) (make-grade "Johnny" "Rad" 15)))
```

Exercise 2: Design a function, `merge-sorted`, that takes two lists of exam grades as input, this time with different student names in each list. Both input lists are already sorted in alphabetical order of student last name. Your function should combine the two lists into one that is also sorted in alphabetical order of last name.

Hint: the built-in function `(string<? a b)` checks if the string `a` comes before the string `b` in alphabetical order. If two students have the same last name then their relative order doesn't matter.

You should first develop a helper function `insert` that takes a list of exam grades already in sorted order and also another exam grade, and inserts that grade at the correct place in the list so that the output list is in sorted order.

Here is an example (you should develop more to fully test your code):

```(define g1 (list (make-grade "Seth" "Alexander" 10) (make-grade "Johnny" "Rad" 15)))
(check-expect (merge-sorted g1 g2) (list (make-grade "Seth" "Alexander" 10)
```

Problem A2:

Here is a data definition for a binary tree of numbers:

``` ;; A BTN is one of
;; - Number
;; - (make-node BTN BTN)
(define-struct node (left right))
```

Exercise 1: Design a function, `btn-height`, that takes in a binary tree of numbers and computes the maximum distance from the root to any leaf. Here "distance" is measured by adding 1 for each internal node on the way from the root to the leaf, plus 1 for the leaf itself. The root node is at height 0.

Here are some examples (you should develop more to fully test your code):

```(check-expect (btn-height 42) 0)
(check-expect (btn-height (make-node 2 (make-node 4 9)) 2))
```

Exercise 2: Design a function, `btn-sum`, that takes in a binary tree of numbers and computes the sum of all leaves.

Here are some examples (you should develop more to fully test your code):

```(check-expect (btn-sum 42) 42)
(check-expect (btn-sum (make-node 2 (make-node 4 9)) 15))
```

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