Midterm Exam Solutions

1. linked list: easiest insertion, and not much space overhead needed for links.
2. doubly linkes list: easy to go forwards or backwards
3. sequential storage - random access, as long as you know where the item is. Can use binary search if not (assuming items are sorted).
All of these could be possible results for input restricted deque. In addition, B would be the result if using a stack and C would be the result if using a queue.

A B I C D E G H F J K
I B D H G E J K F C A

Left kid is a node's first child. Right kid is the node's next sibling.

Base Case: A tree with 1 node (just the root) has zero edges. 1-1 = 0
Inductive Step: Assume that any tree with k nodes has k-1 edges, for k <= n.
Show Also true for k = n+1: If we add a node to a tree of n nodes, we either add it as the root, as a leaf or add it between two existing nodes. In the first two cases, we need exactly one edge to connect it to the rest of the tree (connecting the leaf to its parent, or the root to its child, the old root). In these cases the number of edges is (n-1)+1 = n, which is (n+1)-1. If we add the node between two other nodes, then we add two edges, one connecting the node to its parent, and one connecting to its child. But we also removed one edges, that was originally connecting the parent to the child, before we added the new node. Thus the number of edges is (n-1)+2-1= n. In either case when we add a node to get N+1 nodes, we have n edges, and so the property holds.
Since it holds inductively, it holds for all values of n >+1.

At each step add the edge which connects one of the unconnected nodes to a component node with the cheapest cost. Start arbitarily with any node.

Component Edges	Component Nodes	Unconnected Nodes
	A	B C D E F
(A B)	A B	C D E F
(A B) (B D)	A B D	C E F
(A B) (B D) (C D)	A B C D	E F
(A B) (B D) (C D) (D F)	A B C D F	E
(A B) (B D) (C D) (D F) (E F)	A B C D E F

So, total tree has cost of 3+2+2+2+4

1. Inductive Proof:
  Base Case: A graph with 2 nodes and zero edges is unconnected: it has more than one connected sub-components (i.e, in this case two components, one for each node).
  Inductive Step: Assume that any graph with k nodes and < k-1 edges, is unconnected for k <= n.
  Show Also true for k = n+1:Since the graph with k nodes and k-2 edges is unconnected that means it contains at least 2 unconnected components. If we add a node then it has 3 unconnected components. Now we can only add at most one more edge to keep below (K+1)-1 edges total. Each edge can connect (at most) two components. But if we start with three, we will still have at least two after adding the edge. Thus this property is true for graphs with k+1 nodes, and thus, by induction, for all graphs with n>=2 nodes.
2. Proof by contradiction: Assume there is a graph with n nodes and n edges that does not have a cycle. If the graph does not have a cycle, then there must be at least one node that has degree of 1 or less (if a node has a degree of 2 or more, then you can travel in one edge and out another edge. When you repeat this process, traversing the graph, if you come to a node you've already been to, that's a cycle. Eventually you will run out of new nodes, so that by the nth node, if not before, you will either have no where to go, or will go to a node you've visited. Assuming no cycles, then you must have reached a node with degree less than 2). Now transform the graph by removing a node that has degree 1 or 0. If the node had degree 1, also remove the corresponding edge (since it is missing one of its vertices. Thus the new graph has n nodes, and at least n-1 edges. Now, by the same argument, the new graph will either have at least one node with degree less than 2, or will have a cycle. If the new graph has a cycle, then so did the original. Continue this process of removing nodes and edges until there is only one node left. You have removed n-1 nodes, and at most n-1 edges. But this means that there is at least one edge left, and no such graph can exist, sicne there are no other nodes for the edge to connect to. Thus any graph with n nodes and more than n-1 edges has at least one cycle. <
1. mystery merges two lists, copying each element, until one is empty, and then sharing the remaining structure of the other list.
2. (1 a 2 b 3 c 4)
3. Using a table for the cons cells, showing car and cdr and assuming numbers are stored elsewhere (indicated with hash marks):
```
1 #1 2
2 #3 3
3 #5 4
4 #6 0
5 #2 6
6 #4 0
7 #1 8
8 #2 9
9 #3 10
10 #4 3
```
  Cells 1-4 are created by the first list call, and bound to list1 when mystery is called. Cells 5-6 are created by the second list call, and bound to list2 inside of mystery. Inside of mystery, cells 7-8 are created by the outer call, and 9-10 by the recursive call. When the outer call finishes, it reutns cell 7, which is what setq binds X to.
4. follow all the pointers, starting from X, which poijts to cell 7. This marks 7,8,9,10,3,4. Thus cells 1-2, and 5-6 are unmarked: 4 cells total.

Remove the needed storage from the first block that is big enough:

1000,500,400,200,800   Allocate 500
500,500,400,200,800    Allocate 600
500,500,400,200,200    Allocate 500
500,400,200,200        Allocate 400
100,400,200,200

Remove the needed storage from the smallest block that is big enough:

1000,500,400,200,800   Allocate 500
1000,400,200,800       Allocate 600
1000,400,200,200       Allocate 500
500,400,200,200        Allocate 400
500,200,200

           Unsorted        Sorted
Start:  1 12 3 8 4 9
Pass 1: 12 3 8 4 9       1
Pass 2: 3 8 4 9          1 12
Pass 3: 8 4 9            1 3 12

Several heaps are possible. You need to have all items represented in a complete binary tree, in which each parent is bigger than it's children. Here's one example:
```
      9
     / \
    8   6
   / \ / \
  7  5 4  2
 / \ 
1   3
```


(defun mergesort (unsorted)
   (cond ((null unsorted) unsorted)        ;empty list is sorted
         ((null (cdr unsorted) unsorted))  ; list with one elt is sorted
         (t (mergelists (mergesort (firsthalf unsorted))
                        (mergesort (secondhalf unsorted))))))

(defun mergelists (list1 list2)
  (cond ((null list1) list2)
        ((null list2) list1)
	((< (car list1) (car list2)) ;>
	 (cons (car list1) (mergelists (cdr list1) list2)))
	(t (cons (car list2) (mergelists list1 (cdr list2))))))

Children are shown in clockwise order from NW.

      
          A 
     / /      \   \
    / /        \ 
   /  |         \  
  E   C           B
    /| | \     / | | \
          F        G  D