Answer: Assuming that there is already a successor to i, and that we can find i:
j.next = i.next i.next.prev = j j.prev = i i.next = jOtherwise we would also have to search for i, and/or point the end marker to j.
push a, push b, push c, pop, push d, pop, pop, push e
Answer: The contents of the stack is shown after each operation:
Stack: Operation: push a Stack: a Operation: push b Stack: a b Operation: push c Stack: a b c Operation: pop Stack: a b Operation: push d Stack: a b d Operation: pop Stack: a b Operation: pop Stack: a Operation: push e Stack: a e
insert a, insert b, insert c, remove, insert d, remove, remove, insert e
Answer:
Queue: Operation: insert a Queue: a Operation: insert b Queue: a b Operation: insert c Queue: a b c Operation: remove Queue: b c Operation: insert d Queue: b c d Operation: remove Queue: c d Operation: remove Queue: d Operation: insert e Queue: d e
a < b, a < c, d < b, e < c, a < e, a <
d
Answer: This one is easy, with many possibilities. The best way in general is to construct the data structure of the in count and list of out counts for each vertex participating in these relationships, then repetitively choose a zero count vertex and decrement the in counts of all items it points to. The data structure is:
a 0 b c d e b 2 c 2 d 1 b e 1 cSo, a must be first followed by d or e. B can be anywhere after d, and c could be anywhere after e. Thus one possible order is a d e b c.
nodes.
Answer: The easiest way to prove this is to first prove a supporting lemma, that a binary tree has at most 2^(d-1) nodes at depth d. We can also prove this inductively:
Base Case: A binary tree of depth 1 has just one node (the root). 2^(1-1)= 2^0 =1, so this is true.
Inductive step: Assume that all binary trees of depth d have at most 2^(d - 1) nodes or fewer at depth d. Now consider a binary tree of depth d+1. All nodes at depth d+1 must be children of nodes at depth d. Moreover, each node can have at most two children. So the maximum number of nodes at depth d+1 = 2*(max nodes at depth d) = 2*2^(d-1) = 2^d = 2^((d+1)-1). So the property holds for trees of depth d+1, as well, and thus for all binary trees, whatever the depth.
Now, we can easily prove the main theorem:
Base Case: A binary tree of depth 1 has just one node (the root). 2^1-1 =1, so this is true.
Inductive step: Assume that all binary trees of depth d have 2^d - 1 nodes or fewer. Now consider a binary tree of depth d+1. This will be equivalent to a binary tree of depth d, plus some nodes added at depth d+1. Since the most nodes we could possibly add at depth d is 2^d, by the above lemma, the most nodes a tree of depth d+1 could have is 2^d-1 + 2^d = 2*2^d-1 = 2^d -1 = 2^((d+1) -1), and so the property holds for the inductive step, and this for all trees, whatever the depth.
 |
|
(A B 6) (A C 3) (B C 3) (B E 6) (C E 7) (C D 2) (E D 3)
Answer: First it's probably useful to compute the vertex based representation for this graph -see the answer to the next problem.
Now, we partition the set into a starting node (chose A, without loss of generality), and a set of unconnected nodes. Now we compute at each step the chepest connection from the connected set to a node in the unconnected set and add the new edge which connects them:
Connected Nodes: A Edges: Unconnected: B C D E New Edge: AC Connected Nodes: A,C Edges: AC Unconnected: B D E New Edge: CD Connected Nodes: A,C,D Edges: AC,CD Unconnected: B E New Edge: BC Connected Nodes: A,B,C,D Edges: AC,CD,BC Unconnected: E New Edge: DE Connected Nodes: A,B,C,D,E Edges: AC,CD,BC,DE Unconnected:
Answer:
A B C D E A 6 3 B 6 3 6 C 3 3 2 7 D 2 3 E 6 7 2Alternatively, rather than an array with one space for each possible edge, whether it exists or not, could have had a list of pairs of vertex and weight
Answer: No. Some vertices, namely B and E, have an odd degree.
- (A . B)
Answer:_____ | | | ||_||_| | | v v a b
- (A B C)
Answer:_____ __ __ __ __ | | ---->| | ---->| | /| ||_|__| ||_|__| ||_|/_| | | | v v v a b c
- (cons 'A (cons 'B nil))
Answer:_____ __ __ | | ---->| | /| ||_|__| ||_|/_| | | v v a b
- (list 'A 'B)
Answer: Same as (c).
(defun mystery (list)
(cond ((null list) nil)
((null (cdr list)) list)
(t (cons (car list)
(append (mystery (cdr list))
(cons (car list) nil))))))
- In english, what does mystery do?
Answer: It computes a palindrome based on its input. That is, given a list (a1 a2, ... an-1, an), it returns a list (a1 a2, ... an-1 an, an-1, ... a2, a1) - what is the result of the following call:
(mystery '(a b c))
Answer:(a b c b a) - Draw the cons cells created in evaluating the following
expression:
(setq X (mystery (list 1 3 5 6)))
Answer: Using the array memory allocation scheme used in the previous homework, and assuming that the atoms for numbers are already prelallocate, we will use the following cells (a # in the pointer means the pointer to the atom representing that number, not to that location. Cells 1-4 are used to construct the list input to mystery. Cells 5-7 are created in the deepest (non-trivial) call to mystery. Cells 13-19 are created on the final call, and X is set to cell 19.1 #6,0 2 #5,1 3 #3,2 4 #1,3 5 #5,0 6 #6,5 7 #5,6 8 #3,0 9 #5,8 10 #6,9 11 #5,10 12 #3,11 13 #1,0 14 #3,13 15 #5,14 16 #6,15 17 #5,16 18 #3,17 19 #1,18
- assuming X is the only immediately accessible pointer, mark the
accessible cons cells and tell how many are now garbage.
Answer: Cells 13-19 are accessible, the rest are inaccessible, for 12 cells of garbage.
insertionsort which takes an
arbitary list of numbers and returns a sorted list by repeatedly calling the
second: insert, which takes an item and a sorted list, and
returns a new list with the item included in it's proper location.
Answer:
(defun insert (item list)
(cond ((or (null list)
(< item (car list)))
(cons item list))
(t (cons (car list)
(insert item (cdr list))))))
(defun insertion-sort (list)
(cond ((null list) nil)
(t (insert (car list) (insertion-sort (cdr list))))))
;alternatively:
(defun insertion-sort2 (list)
(insert-help list nil))
(defun insert-help (unsorted sorted)
(cond ((null unsorted) sorted)
(t (insert-help (cdr unsorted)
(insert (car unsorted) sorted)))))
Chicago, (10, 40) (the root) Miami, (90, 100)If you are looking for items inside the box centered at Miami with horizontal extent 100 and vertical extent 60, which quadrants of Chicago can you avoid searching?
Answer: Computing the box, you want any items with X coordinates between -10 and 190, and Y coordinates between 60 and 160. If you ever find any quadrants that can't possibly have any items in this range, you can avoid searching them. In particular, if we say that postive X is East and positive Y is North, then the south quadrants of Chicago will be out of this range (their Y coordinates will be lower than 40). So, we only need to searhc the NE and NW coordinates of Chicago, and can avoid the SW and SE.