Practice Final Solutions
A Fine Product Brought To You By Richard
(If anything is wrong, please direct your hate mail to him.)

1


Thanks to Derek Arndt for pointing out the mistake in the solution below (correction in red).
(define (insert-in-order el lst)
  (cond ((null? lst) (cons el '()))
        ((< el (car lst)) (cons el lst))
	(else (cons (car lst) (insert-in-order el (cdr lst))))
  )
)

2


Problem 2 doesn't command us to return anything, so we don't.
Maria: in Scheme we should always return a value even when not explicitely requested
The simple solution, with complexity 2n.
Maria: the time complexity is 2n but also the space complexity is 2n since the list is copied twice
(define (insert-in-order! el lst)
  (set-car! lst (car (insert-in-order el lst)))
  (set-cdr! lst (cdr (insert-in-order el lst)))
)

The solution below is more efficient than the one above. It has complexity n.
Maria: the time complexity is n but also the space complexity is n since the list is copied once
(define (insert-in-order! el lst)
  (let ((new-lst (insert-in-order el lst)))
    (set-car! lst (car new-lst))
    (set-cdr! lst (cdr new-lst))
  )
)

In the answer below, note that (set-cdr! lst (cons (car lst) (cdr lst))) cannot be replaced by (set-cdr! lst lst).
Note that the answer below will fail if a null list is given. This is bad as the question allows for this possibility.
For this reason the answer below is not a good "solution".
(define (insert-in-order! el lst)
  (cond ((null? lst) "Error: Can't work with this!")
        ((< el (car lst)) 
	 (set-cdr! lst (cons (car lst) (cdr lst))) 
	 (set-car! lst el))
	((null? (cdr lst)) (set-cdr! lst (cons el '())))
	(else (insert-in-order! el (cdr lst)))
  )
)
Maria: here is another solution
(define (insert-in-order! el lst)

  (define (attach el l)
	  (set-cdr! l (cons el (cdr l))))

  (define (insert-aux el lst)
	  (cond ((null? (cdr lst))  ; insert after last element
		 (attach el lst))
		((<= el (cadr lst)) ; found spot
		 (attach el lst))
		(else (insert-in-order! el (cdr lst)))))
	
  (cond ((null? lst) "error -- empty list")   ; special case -- empty list
        ((< el (car lst))         ; special case -- insert first element
	 (set-cdr! lst (cons (car lst) (cdr lst)))
	 (set-car! lst el)
	 lst)
	(else (insert-aux el lst)
	       lst)))

3

;Probably the best solution
(define (map-tree proc tree)
  (cond ((null? tree) '())
        ((pair? tree) (cons (map-tree proc (car tree)) (map-tree proc (cdr tree)))) ;Build and break here
	(else (proc tree)) ;Do proc here
  )
)

4


(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


Take and drop may aide you later in your life.
(define (take n lst) ;Returns the first n elements
  (if (or (= n 0) (null? lst))
    '()
    (cons (car lst) (take (- n 1) (cdr lst)))
  )
)

(define (drop n lst)
  (if (or (= n 0) (null? lst))
    lst
    (drop (- n 1) (cdr lst))
  )
)

(define (collect lst num)
  (if (null? lst)
    '()
    (cons (take num lst) (collect (drop num lst) num))
  )
)

6


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 == []

   def print(self):
      for x in self.data:
        print x

   def print(self): #An alternative way to do the print method
      print x for x in self.data

s=Stack()
s.push(1)
s.push(2)
s.push(3)
s.print()

7


def AddSevens(lst):
  result=0
  for x in lst:
    if x % 7 == 0:
      result+=x
  return result

8


def extract(d,list_of_keys):
  return [d.get(x) for x in list_of_keys if d.has_key(x)]

def extract(d,list_of_keys):
  return [d[x] for x in list_of_keys if d.has_key(x)]

def extract(d,list_of_keys):
  return [d[x] for x in list_of_keys if x in d.keys()]

def extract(d,list_of_keys):
  result=[]
  for x in list_of_keys:
    if x in d.keys():
      result+=d[x]
  return result

def extract(d,list_of_keys):
  result=[]
  for x in list_of_keys:
    if d.has_key(x):
      result+=d[x]
  return result