Midterm 1

CSE341 Winter 2002

Name:

This Midterm is worth 50 points. Each point represents a minute of time. Use the point totals as a guide for budgeting your time. The exam is closed-book, closed-notes, open-mind.

Page Possible Score
2 15
3 7
4 14
5 14
Total 50






For the purposes of this exam, assume the following functions are defined for you. We just show the "prototypes" of the functions below: 

;; map the function f over the given list
;; return the list consisting of f applied to each element of a-list
(map f a-list)

;; reduce the given list, given a reducing function f and a base value
(reduce f base a-list)

;; return the length of the given list
(length a-list)

;; return a list which is the concatenation of the given lists
(append listA listB)

;; return a list which is the reverse of the given list
(reverse a-list)

(1.) [5 points total] For the following Scheme expressions, show how the result prints out. If the expression results in a run-time error, say why.

  1. (car (+ 1 2) (* 3 4))

  2. (cons (+ 1 2) '(- 3 4))

  3. (append '(1 2) (reverse '(3 4))))

  4. (map (lambda (x) (>= x 10)) '(11 10 9 5 15 6 0))

  5. (list 3 (cdr 1 2))

(2.) [5 points] True / False

TRUE / FALSE When garbage-collecting large objects, copy-collectors are preferable to mark-sweep collectors.
TRUE / FALSE Mark-sweep collectors tend to fragment heap memory.
TRUE / FALSE Scheme is dynamically typed, meaning that it cannot be strongly typed.
TRUE / FALSE C is an example of a statically typed language.
TRUE / FALSE In a C program, space for local variables is allocated in the static region of program memory.

(3.) [5 points] Short Answer. Answer ONLY one of the below. Correct, concise answers will be rewarded.

  1. Describe three (3) salient differences between Scheme and another programming language of your choice (eg. C, C++, Java). One sentence per difference should suffice.
  2. Define tail recursion and give an example of a function that is non-tail-recursive AND then show a tail-recursive version of that function.
  3. Dr. Dweezel has developed a copy-collected heap. He claims that it actually allocates memory faster than the standard (programmer-managed) heap used in a language such as C. Is he correct? Why? (HINT: There are interpretations of his claim that make it either true or false. Choose one and defend it.)

(4.) [7 points total] For each of the following Scheme expressions, show how the result prints out AND also draw the cons-cell box and pointer diagram of the result. For example, for (list 1 2 3) I would answer:

(1 2 3)

4.1) 

'(((foo)) bar)
4.2) 
(list (cons (+ 1 2) ()) 'foo)
4.3) 

(let* ((x '(3 4))
       (y (cons '(1 2) x))
       (z '(4 5 6)))
   (list (+ (car x) (car (cdr y))) 
         (+ (car (cdr x)) (car (cdr (cdr z))))))

(5.) [7 points] Write a function called char-count, which takes list of symbols. It returns a list of the lengths of the symbols in the original list. The function must be written recursively and cannot make use of any of Scheme's higher-order functions such as map. You should use the built-in functions symbol->string and string-length to determine the length of a symbol. Here are some examples:

(symbol->string 'foobar)                     => "foobar"
(string-length (symbol->string 'foobar))     => 6
(char-count '(Hello there my name is Bob))   => (5 5 2 4 2 3)
(6.) [7 points] Write count-chars again, this time using map. You must use a lambda expression (do not define extraneous helper functions).

(7.) [7 points] If we represent documents in Scheme as lists of lists of symbols (where each inner list is a sentence), write a function called stats that takes a "document" and returns a list containing three items: total number of characters, total number of words, and total number of lines. For example, the below "document" contains 33 characters, 9 words, and 4 sentences.

HINTS: If you leverage char-count, as well as reduce, append, and length, this function is quick to write! If you couldn't write char-count, assume it's defined for you. 

(stats '((Dear Sue) (I am learning Scheme) (See ya) (Bill)))  => (33 9 4)
(8.) [7 points] Write a function called map2, that takes three arguments: a function (which takes two arguments) and two lists. map2 should return a list that consists of the provided function applied to the corresponding elements of the two lists. Example: 
(map2 (lambda (x y) (+ 1 (* x y))) '(1 2 3) '(4 5 6))   => (5 11 19)