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)
(define-struct grade (first last points))

 ;; A LOEG (list of exam grades) is one of: 
 ;; - empty 
 ;; - (cons ExamGrade LOEG) 

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)))
(define b2 (list (make-grade "Seth" "Alexander" 12) (make-grade "Johnny" "Rad" 8)))
(check-expect (sum-grades b1 b2) (list (make-grade "Seth" "Alexander" 22) (make-grade "Johnny" "Rad" 23)))

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)))
(define g2 (list (make-grade "Bob" "Foal" 14) (make-grade "Patricia" "Klossner" 18) (make-grade "Radha" "Vijaykumar" 12)))
(check-expect (merge-sorted g1 g2) (list (make-grade "Seth" "Alexander" 10)
                                         (make-grade "Bob" "Foal" 14)
                                         (make-grade "Patricia" "Klossner" 18)
                                         (make-grade "Johnny" "Rad" 15)
                                         (make-grade "Radha" "Vijaykumar" 12)))

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))