CMSC 15100 - Autumn 2005
Lab 4

Extra Credit problems are in red!!

0. Designing Functions on Two Complex Pieces of Data

In this lab you will be designing functions which take two complex pieces of data.

Using function templates is very important when you are designing programs for complex data. Remember the three Cs for data:

  1. Is the data conditional?
  2. Is the data complex? (i.e. structured data)
  3. Do you need to call-in another function template for a part of the data?

1. Lists

1a. Template for lists

Write a template for list-of-numbers. What changes must you make in the template for list-of-symbols?

1b. Cross

You may use the built-in append function.

;; Example:
;; (cross '(a b c) '(1 2)) = (list (list 'a 1) (list 'a 2) (list 'b 1) (list 'b 2) (list 'c 1) (list 'c 2))

;; A symbol-number-pair is a
;; -- (list symbol number)
;; cross: list-of-symbols list-of-numbers --> list-of-symbol-number-pairs
;; Produce all possible pairs of a symbol from a-loss and a number
;; from alons
(define (cross a-loss a-lons) ...)

1c. Dot Product

Given two list-of-numbers of the same length, the dot product is the sum over the product of corresponding numbers in each sequence:

;; Examples:
;; (dot-product empty empty) = 0
;; (dot-product (list 3 6) (list 5 10)) = (3*5) + (6*10) = 75
;; (dot-product (list 1 2 3) (list 4 5 6)) = (1*4) + (2*5) + (3*6) = 32

;; dot-product: list-of-numbers list-of-numbers -> number
;; Compute the dot product of a-lons1 and a-lons2, where these
;; are lists of the same length. Return 0, if lists are empty.
(define (dot-product a-lons1 a-lons2) ... )

1d. Equality for lists-of-symbols

;; Examples:
;; (sym-list=? '(a b c) '(c a b)) = false
;; (sym-list=? '(a b c) '(a b c)) = true

;; sym-list=? : list-of-symbols list-of-symbols -> boolean
;; to determine whether a-list1 and a-list2
;; contain the same symbols in the same order
(define (sym-list=? a-list1 a-list2) ...)

1e. Equality for lists-of-posns

Two posns are equal if their constituent fields are identical. Write a template for list-of-posns before you write the following:

;; Examples:
;; (make-posn 1 2) is the same posn as (make-posn 1 2)
;; (make-posn 1 2) is not the same posn as (make-posn 2 1)

;; posn-list=? : list-of-posns list-of-posns -> boolean
;; to determine whether a-list1 and a-list2
;; contain the same posns in the same order
(define (posn-list=? a-list1 a-list2) ...)

2. Binary Symbol Trees

2a. Template for Binary-Symbol-Trees

Write a template for a binary-symbol-tree.

;; A binary-symbol-tree is a
;; --empty
;; (make-bst symbol binary-symbol-tree binary-symbol-tree)
(define-struct bst (node left right))
;; Template for binary-symbol-trees
;; (define (fun-for-bst a-bst) ...)

2b. Counting Nodes in Binary-Symbol-Trees

;; Examples:
;; (count-nodes empty) = 0
;; (count-nodes (make-bst 'a (make-bst 'b empty empty) empty)) = 2

;; count-nodes: binary-symbol-tree -> number
;; Return the number of nodes in a-bst
(define (count-nodes a-bst) ...)

2c. Equality for Binary-Symbol-Trees

Two binary-symbol-trees, a-bst1 and a-bst2 are the same if either both are empty or the following conditions are all true:

  1. (bst-node a-bst1) and (bst-node a-bst2) are the same symbol.
  2. (bst-left a-bst1) and (bst-left a-bst2) are the same.
  3. (bst-right a-bst1) and (bst-right a-bst2) are the same.


;; Examples:
;; (bst=? empty empty) = true
;; (bst=? (make-bst 'a empty empty) (make-bst 'b empty empty)) = false
;; (bst=? (make-bst 'a empty empty) empty) = false

;; bst=? : binary-symbol-tree binary-symbol-tree -> boolean
;; to determine whether a-bst1 and a-bst2
;; are the same binary-symbol-trees
(define (bst=? a-bst1 a-bst2) ...)

3. Symbol Trees

3a. Template for Symbol-Trees

Write a template for a symbol-tree. You may find it helpful to see Mutual Recursive Data:

;; A symbol-tree is a
;; --empty
;; (make-st symbol list-of-symbol-trees)
(define-struct st (node branches))
;; A list-of-symbol-trees is one of
;; --empty
;; --(cons symbol-tree list-of-symbol-trees)

;; Template for symbol-trees
;; Why must you define TWO templates?
;; (define (fun-for-st an-st) ...)
;; (define (fun-for-list-st an-lst) ...)

3b. Counting Nodes

;; Examples:
;; (count-nodes-st empty) = 0
;; (count-nodes-st (make-st 'a (list (make-st 'b empty)))) = 2

;; count-node-st: symbol-tree -> number
;; returns number of nodes on an-st
(define (count-nodes-st an-st) ...)

3c. Finding Symbols

;; find-node?: symbol symbol-tree -> boolean
;; Return true if node in an-st and false otherwise.
(define (find-node? node an-st) ...)

3d. Equality for Symbol-Trees

You have seen tests of sameness for list-of-symbols and binary-symbol-trees. Now, extend this notion to symbol-trees and write a functin for testing whether two symbol-trees are the same.

;; st=? : symbol-tree symbol-tree -> boolean
;; to determine whether an-st1 and an-st2
;; are the same symbol-trees
(define (st=? an-st1 an-st2) ...)