CSci 1301: Problem Set 10

Due Thursday, Dec. 10 at 11:59pm by e-mail

As always, please include a contract, a purpose, examples, and tests for each function.

Problem 1 (20 points)

Extended exercise 28.2

A board is represented as a list of lists of booleans. Note that the solution for exercise 28.2.1 is just a description of a board, no Scheme code. Below are test cases for 28.2.2:


(check-expect (build-board 5 (lambda (i j) (cond [(even? (+ i j)) true][else false])))
              (list (list true false true false true)
                    (list false true false true false)
                    (list true false true false true)
                    (list false true false true false)
                    (list true false true false true)))

(check-expect (board-ref (build-board 5 (lambda (i j) (cond [(even? (+ i j)) true][else false])))
                         2 3) false)

(check-expect (board-ref (build-board 5 (lambda (i j) (cond [(even? (+ i j)) true][else false])))
                         2 4) true)

Problem 2 (6 points)

Define tail-recursive functions to

Problem 3 (12 points)

Use change_memory.ss as examples of memory update fucntions.

Your task is to write a function that counts how many times each element appears in a given list. The result is stored as a global (i.e. outside of all functions) list of structures of pairs of an element value and its count.

The structure definition and the contracts for the functions that you need to write are given below. Make sure to follow the contracts precisely. Note that update-count is recursive over the list of counts. It must call add-element to add the element to the global list.

The language must be set to Advanced Student


;; the structure represents an element (a number) and
;; its count (an integer >= 1)
(define-struct count (value its-count))

(define element-counts empty)

;; add-element: number -> void
;; adds a count structure in the front of element-counts list
;; with the value "element" and a count 1.
;; Example: if element-counts is empty then after a call
;; (add-element 7)
;; element-counts becomes
;; (list (make-count 7 1))

;; update-counts: number list-of-counts -> void
;; Checks if the element is in the given lists of counts
;; If it is, sets the count for that element to the current count
;; value plus one
;; If it is not, calls add-element to add the element 
;; to element-counts list 
;; Example: if element-counts is empty then after the call
;; (update-counts 3 element-counts)
;; it becomes
;; (list (make-count 3 1))
;; and after the second call
;; (update-counts 3 element-counts)
;; it becomes
;; (list (make-count 3 2))



;; element-counts: list of numbers -> boolean
;; The function resets the counts in element-counts list
;; to count the number of occurrences of each element
;; Example: if element-counts is empty then after the call
;; (count-elements (list 1 3 2 4 5 3 2 4 5 ))
;; element-counts becomes:
;; (list (make-count 5 2) (make-count 4 2) (make-count 2 2) (make-count 3 2) (make-count 1 1))
;; The function returns false or void from its base case

Problem 4, extra credit (up to 12 points)

Design and implement your own fractal picture.


CSci 1301 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.