CSci 1901: Lab 15, May 3

Lab 15: Practice for the Final

  1. Write a procedure (insert-in-order el lst) to insert a number into a ordered list of numbers, maintaining the order. The numbers must be in increasing order. Write this procedure in a way that does not modify the original list.
    STk> (insert-in-order 3 (list 7 8 10))
    (3 7 8 10)
    STk> (insert-in-order 3 (list 1))
    (1 3)
    
  2. Write a procedure (insert-in-order! el lst) to modify a given ordered list of numbers by inserting a number into it, maintaining the order. Assume the numbers are in increasing order. This is the same problem as in the previous question, but now you have to modify the list instead of creating a new copy.
    STk> (insert-in-order! 3 (list 7 8 10))
    (3 7 8 10)
    STk> (insert-in-order! 3 (list 1))
    (1 3)
    STk> (define lst (list 1 2 4 5))
    (1 2 4 5)
    STk> lst
    (1 2 4 5)
    STk> (insert-in-order! 3 (list 1 2 4 5))
    (1 2 3 4 5)
    STk> lst
    (1 2 3 4 5)
    
  3. Write a procedure (map-tree proc tree) to apply the procedure tt proc to each element of the tree. Assume that proc is a procedure of one argument. It should work like this:
    STk> (map-tree (lambda (x) (* x x))  '(3 (4 6 (2 1)) 5))
    (9 (16 36 (4 1)) 25))
    STk> (map-tree sqrt '((4) 16 25))
    ((2) 4 5)
    
  4. Show the values of the indicated expressions, assuming all the expressions are evaluated in order.
    (define q (make-queue)) 
    q                               => .....
    (insert-queue! q 'a)            => .....
              ;; Draw Cons Box Diagram for Q
    (insert-queue! q 'b)            => .....
    (delete-queue! q)               => .....
              ;; Draw Cons Box Diagram for Q
    (delete-queue! q)               => .....
    
  5. Write a procedure (collect lst num) that returns a new list in which the elements of lst are grouped into sublists of length n. The last sublist might be shorter than n if there are no more elements in the list. It should work like this:
    STk> (collect '(a b c d) 2)
    ((a b) (c d))
    STk> (collect '(a b c d e) 3)
    ((a b c) (d e))
    
  6. Below is a class that implements a stack in Python. A stack, like a queue, is an abstraction over a list of data. Unlike a queue, a stack is a last-in first out (LIFO) data structure, as opposed to first in, first out (FIFO) data structure like a queue.
    class Stack:
       def __init__(self):
           self.data = []
    
       def push(self,item):
            self.data.append(item)
    
       def pop(self):
          return self.data.pop()
    
       def is_empty(self):
          return self.data == []
    
    Add a method for printing out the elements of a stack. Then show how to create a new stack, add the numbers 1, 2, and 3 to the stack, and then print the elements out using the method you implemented.
  7. Write in Python a procedure that takes a list and adds all the elements of the list that are a multiple of 7. Assume all the elements of the list are integers. It should work like this:
    >>> multiple7([3,49,21,5,36])
    70
    
  8. Write in Python a function extract(d,list_of_keys) to return from the dictionary d the values of the keys that are in the list list_of_keys. For instance, given a dictionary with names of people and office numbers and a list of names, extract should return a list of the offices of the people who are in the list of names. It should work like this:
    >>> offices ={'bill':503,'joe':305,'john':307,'maria':512,'shana':305}
    >>> names = ['john','joe']
    >>> extract(offices,names)
    [307,305]
    >>> extract(offices,['charles','joe'])
    [None,305]