CSci 1901: 3rd Homework
Due: Monday, March 19

This homework is to be done individually. You can do it with pencil and paper or with the computer. Working alone will help you assess how prepared you are for the upcoming In Class Quiz and Midterm. For questions and help, see the TAs.
Homeworks done in collaboration with others will be considered in violation of the Scholastic Conduct Code stated in the syllabus: "Collaboration on homeworks, or exams is cheating and grounds for failing the course."
  1. (15 points) Write a procedure insert-at that inserts a given element into a list in a specified position. Assume that the positions are numbered from 0, and that the position specified is always 0 or positive. If the position is greater than the length of the list the procedure should return the list itself. It should work like this:
    STk> (insert-at 'k 3 '(b c m n))
    (b c m k n)
    STk> (insert-at 'a 0 '(b c d e))
    (a b c d e)
    STk> (insert-at 'a 7 '(b c d e))
    (b c d e)
    
  2. (15 points) Write a procedure (expand lst) that takes as an argument a list. The elements of the list are either symbols or lists of two elements, a strictly positive integer (i.e. greater than 0) and a symbol. The integer is a repeat count, meaning that the symbol following it should be repeated that many times. The procedure should return a list where the repeated symbols are expanded, i.e. each sublist (< number > < symbol >) is replaced by a list with the symbol repeated < number > times. You cannot use any global variable, but you are free to use as many auxiliary procedures as you like. It should work like this:
    STk> (expand '(oh (2 ah)))
    (oh (ah ah))
    STk> (expand '(school is (1 very) hard))
    (school is (very) hard)
    
  3. (10 points) Write a procedure (replace old new lst) to replace every occurrence of the element old in the list lst with new. If the element does not appear in the list, the list should be returned unchanged. It should work like this:
    STk> (replace 3 -3 (list 3 4 1 2 3))
    (-3 4 1 2 -3)
    STk> (replace 1 11 (list 3 2 10))
    (3 2 10)
    STk> (replace 1 '(2 3) '(3 1 4 2))
    (3 (2 3) 4 2)
    
  4. (10 points) Write a procedure running-sum that given a list produces a new list that contains, as each element in the new list, the sum of all corresponding elements up to that point in the original list. It should work like this:
    STk> (running-sum (list 1 3 9 2))
    (1 4 13 15)
    ;where 4 = 1+3, 13 = 1+3+9, 15=1+3+9+2
    STk> (running-sum (list 2 2 2 2 2))
    (2 4 6 8 10)     
    STk> (running-sum (list 2))
    (2)
    
  5. (10 points) Write a predicate (find pred tree) that returns a list of the elements of the tree that satisfy the predicate. It should work like this:
    STk>(find odd? '(3 (2 (1 3) 9)))
    (3 1 3 9)
    STk>(find even? '((3 11) 5))
    ()
    
  6. (10 points) Write a procedure inc1-even that takes as an argument a tree whose elements are numbers and increments by one all the numbers that are even. It should work like this:
    STk> (inc1-even '(1 (2 (3 4) 8 10) 9 (11)))
    (1 (3 (3 5) 9 11) 9 (11)))
    STk> (inc1-even '(1 (5 (3))))
    (1 (5 (3)))
    
  7. (10 points) Write a procedure (remove-el el set) to remove an element from a set represented by an ordered list. If the element does not exist in the set, the procedure should return the same set. Write the procedure to take advantage of the ordering of the elements of the set to speedup the computation. It should work like this:
    STk> (remove-el 3 (list 2 3 7)) 
    (2 7)
    STk> (remove-el 5 (list 2 3 7)) 
    (2 3 7)
    
  8. (10 points) Write a predicate (set-diff set1 set2) to compute the difference of two sets, which is the set containing each element that appears in set1 but not in set2. Assume the sets are represented by ordered lists. To get full credit you have to write the predicate to take advantage of the ordering of the elements of the sets. It should work like this:
    STk> (set-diff '(2 5 7 9 25) '(2 7 9) )
    (5 25)
    STk> (set-diff '(2 5 7 9 25) '(3 8) )
    (2 5 7 9 25)
    STk> (set-diff '(2 3) '(2 3) )
    ()
    
  9. (10 points) You are given the following procedures from the textbook:
    (define (attach-tag type-tag contents)
      (cons type-tag contents))
    
    (define (type-tag datum)
      (if (pair? datum)
          (car datum)
          (error "Bad tagged datum -- TYPE-TAG" datum)))
    
    (define (contents datum)
      (if (pair? datum)
          (cdr datum)
          (error "Bad tagged datum -- CONTENTS" datum)))
    
    and the following definition
    (define mytree '(a (b (c)) d))
    
    1. Show the procedure call to attach the tag tree to mytree by completing the following:
      (define tagged-tree ??)
      
    2. Show the values of the following expressions:
      (contents tagged-tree) 
      (type-tag tagged-tree) 
      
    3. Show the internal representation of tagged-tree. Draw the cons box representation.
Copyright: © 2000-2006 by the Regents of the University of Minnesota
Department of Computer Science and Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.