Written Assignment #4: Sample Answers

Table of Contents

  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.
      Answer: 400, 150, 200, 150
      First Fit Remaining memory: 100
      Best Fit memory before last request: 100, 100, 50
    2. Give a sequence of memory allocation requests that could be handled by best-fit, but not by first-fit.
      Answer: 400, 200, 300
      Best Fit Remaining memory: 100
      First Fit memory before last request: 100, 100, 200
    3. Which algorithm would be better for the following sequence of requests, and why?
      200, 300.
      Answer: Best fit - since the fits are exact, this will leave bigger blocks around which could be split if needed.

  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))


    Answer: For ease of drawing, we will allocate lisp cells sequentially in memory. Each cell will contain either an atom or a list of two pointers representing the locations of the car and cdr, respectively. Nil is represented by the location 0. Cells 1-12 are constructed in making the two lists which are input to the append1 call in setting the value of X. 13-15 are created in processing the append call. The value of X is set to cell 13. When processing the rev1 call, many cells are created, due to the inefficiency of using append. In the deepest pass, cell 16 is created. Then the next deepest, cells 17,18 are created, then cells, 19-21, etc., until on the return from the main call, 31-36 are created, and Y points to cell 36, a list with the reverse elements of X. 
    1   A
2   B
3   C
4   3,0
5   2,4
6   1,5
7   D
8   E
9   F
10  9,0
11  8,10
12  7,11
13  1,14
14  2,15
15  3,12
16  9,0
17  8,0
18  9,17
19  7,0
20  8,19
21  9,20
22  3,0
23  7,22
24  8,23
25  9,24
26  2,0
27  3,26
28  7,27
29  8,28
30  9,29
31  1,0
32  2,31
33  3,32
34  7,33
35  8,34
36  9,35

  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.
    Answer: Use any of the marking algorithms from class. Since we don't have to worry about stack space, probably number 2 is easiest -- just follow all the unmarked links from the cells that TT>X and Y are pointing to, i.e., 13, 36. The marked cells will be 1-3,7-15, and 31-36 (e.g., A points to 13, which points to 1 and 14, 14 points to 2 and 15, etc). The garbage cells will be the ones that are not marked, i.e, 4-6, and 16-30, so 18 garbage cells in all!

  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.
      Answer: Each time a page is accessed it is placed in the front of the list of pages. If the page was not already in memory, then the last page is paged out. Memory appears as follows for each operation: 
      In: a b c d e f g        Out: h i j      Access:  a
In: a b c d e f g        Out: h i j      Access:  c
In: c a b d e f g        Out: h i j      Access:  d
In: d c a b e f g        Out: h i j      Access:  i
In: i d c a b e f        Out: h j g      Access:  b
In: b i d c a e f        Out: h j g      Access:  c
In: c b i d a e f        Out: h j g      Access:  h
In: h c b i d a e        Out: j g f      Access:  g
In: g h c b i d a        Out: j f e      Access:  j
In: j g h c b i d        Out: f e a      Access:  i
In: i j g h c b d        Out: f e a
      So, the pages sent out were g,f,e, and a.
    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.
      Answer: Here, we need to keep a circular list of the pages, with an accessed bit, and a pointer to the next cell to check. Assuming that we start checking from A, memory is updated as follows, where a * indicated a marked page: 
      In: a b c d e f g        Out: h i j  Pointer: a    Access:  a
In: a* b c d e f g       Out: h i j  Pointer: a    Access:  c
In: a* b c* d e f g      Out: h i j  Pointer: a    Access:  d
In: a* b c* d* e f g     Out: h i j  Pointer: a    Access:  i
In: a i c* d* e f g      Out: h b j  Pointer: c    Access:  b
In: a i c  d b f g       Out: h e j  Pointer: f    Access:  c
In: a i c* d b f g       Out: h e j  Pointer: f    Access:  h
In: a i c* d b h g       Out: f e j  Pointer: g    Access:  g
In: a i c* d b h g*      Out: f e j  Pointer: g    Access:  j
In: j i c* d b h g       Out: f e a  Pointer: i    Access:  i
In: j i* c d b h g       Out: f e a  Pointer: i
      So, the pages sent out were b,e,f,a.

  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
    Answer: dashed lines show comparisons with no change, arros show a change. * shows an item in its final position, which requires no more comparisons. The list is sorted after the second pass, but we can't realize this until the third pass when there no exchanges. 
    1 12 3 8 4 9     Initial  
First Pass: 1 - 12 <-> 3 <-> 8 <-> 4 <-> 9
1 3 8 4 9 12*
Second Pass:1 - 3 - 8 <-> 4 - 9 12*
1 3 4 8 9* 12*
Third Pass:1 - 3 - 4 - 8*  9* 12*
1 3 4 8 9* 12*

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

    Answer: The easiest way to start is to just insert the items one by one into a heap. Here. we use an array representation of a binary tree, for ease of drawing on a computer. The left child of location n is at location 2n, while the right child is at location 2n+1. Here is the heap after the insertion of each item. Each time we insert an item, we have to percolate it up to its proper place in the heap, which means perhaps percolating some items down. 
    Node: 1  2  3  4 5 6 7 8 9 10 11
Heap:                            Add: 3
Heap: 3                          Add: 8
Heap: 8  3                       Add: 7
Heap: 8  3  7                    Add: 4
Heap: 8  4  7  3                 Add: 5
Heap: 8  5  7  3 4               Add: 9
Heap: 9  5  8  3 4 7             Add: 10
Heap: 10 5  9  3 4 7 8           Add: 12
Heap: 12 10 9  5 4 7 8 3         Add: 2
Heap: 12 10 9  5 4 7 8 3 2       Add:8
Heap: 12 10 9  5 8 7 8 3 2 4     Add:6
Heap: 12 10 9  5 8 7 8 3 2 4  6
    Other heaps are possible, e.g., inserting all the items then checking all the nodes (going up and down when necessary) to fix the heap property.

  7. For the heap constructed in the previous question, show the reconstructed heap after the highest two elements are removed.
    Answer: Switch the first item with the last (removing the new last), and rebuild the heap. 
        Node: 1  2  3  4 5 6 7 8 9 10 11
    Heap: 12 10 9  5 8 7 8 3 2 4  6         
Exchange:  6 10 9  5 8 7 8 3 2 4 |12     
 Rebuild: 10 8  9  5 6 7 8 3 2 4 
Exchange:  4 8  9  5 6 7 8 3 2 |10 
 Rebuild:  9 8  8  5 6 7 4 3 2

  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.
    Answer: Proof by induction:
    Base Case:consider a binary tree of depth 1 - this has just the root. Since there are no children, it trivially fulfills the heap property, and is also the largest item.
    Inductive step: Assume the root is the largest item in any tree of depth n with the heap property. Now, consider trees of depth n+1 with the heap property. For any such tree T, of depth n+1, we can construct a tree T', which has only those nodes of T at depth n or less. Since this tree also has the heap property (since T did), and is of depth n, we know that the root is the biggest node in T'. Now all other nodes in T, not in T' will be at depth n+1, and each node D must be less than its parent, P, a node at depth T, via the heap property. Since P is less than the root, D must also be less than the root. Since all nodes in T are less than the root, the root is also the largest item in trees of depth n+1.
    Thus, by induction, the root is the largest item of any binary tree with the heap property.

  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
    Answer: 
       Index: 1 2 3 4 5 6  7
 counter: 4 1 3 2 1 1  1
Position: 0 4 5 8 9 10 11

Final Sort:
1 1 1 1 2 3 3 3 4 4 5 6 7

David Traum
April 2, 1997