Written Assignment #4

1. Storage Management: Assume that free memory initially contains blocks of the following sizes:
   100, 300, 200, 400
   1. Give a sequence of memory allocation requests that could be handled by first-fit, but not by best-fit.
   2. Give a sequence of memory allocation requests that could be handled by best-fit, but not by first-fit.
   3. Which algorithm would be better for the following sequence of requests, and why?
      200, 300.

2. Garbage Collection and Lisp : Recall the definitions of append1 and rev1 given in class:

   (defun append1 (list1 list2)
          (cond ((null list1) list2)
                (t (cons (car list1) 
                         (append1 (cdr list1) list2)))))
   
   
   (defun rev1 (list)
         (cond ((null list) nil)
               (t (append (rev1 (cdr list))
                          (cons (car list) nil)))))

   Also recall that the list function returns a list of it's arguments - that is, one cons cell for each argument, where the car points to the argument, and the cdr points to the next cons cell (except for the last cdr, which is nil). Draw the cons cells that get created in processing the following expressions. Make sure to label which cells are pointed at by X and Y.

   (setq X (append1 (list 'a 'b 'c) (list 'd 'e 'f)))
   (setq Y (rev1 X))

3. For the previous question, some of those cells are not accessible after finishing evaluation of the expressions. These cells are garbage. If X and Y point at the only immediately accessible cells, mark all the accessible cells, and tell how many are now garbage.

4. Overflow (paging):
   Assume the following pages (in order) in memory:
   A B C D E F G
   Also, the program has the following pages not initially in memory:
   H I J
   Whenever someone accesses a page not in memory, it must be brought (back) in, and another page must be sent out. Assume the following memory accesses:
   A C D I B C H G J I
   
   1. which pages get sent out, according to the LRU (least recently used) scheme? Show the final state of the list of pages.
   2. Which pages get sent out, according to the NUR (not used recently) scheme? Show the final list of pages, including the used recently bits.

5. Show the results of the first three passes of bubble sort on the following data (sorting from lowest to highest):
   1 12 3 8 4 9

6. Make a heap of the following data:
   3 8 7 4 5 9 10 12 2 8 6
   

7. For the heap constructed in the previous question, show the reconstructed heap after the highest two elements are removed.

8. Prove that if a binary tree has the heap property (each parent is at least as large as each of its kids), then the root must be the largest item.

9. Show the value and position counters for a distribution sort on the following data:
   1 5 2 1 3 4 1 6 7 1 3 4 3