Suppose that you insert 33 into the following heap. What does the heap look like after the insertion, and after restoring it to a heap using reheapUp? Note that only the priorities are shown. Do not worry about additional information.
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
25
/ \
/ \
/ \
33 40
/ \ / \
60 75 42 46
/ \
80 65
Suppose that you remove the smallest value from the following heap. What does the heap look like after the removal, and after restoring it to a heap using reheapDown?
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
40
/ \
/ \
/ \
60 42
/ \ / \
65 75 80 46
How long does it take, in terms of n, to remove the smallest thing from a heap? The answer only needs to be correct to within a constant factor.
log2(n)
Dijkstra's shortest distance algorithm performs a sequence of basic update operations, where one basic update consists of finding a vertex u, marking u done, and then updating the status and other information of all vertices that are adjacent to u. If there are n vertices, about how many basic update operations does Dijkstra's algorithm do, in the worst case?
It does one step to initialize (marking the start vertex done), and then does one update for every other vertex. So, in the worst case Dijkstra's algorithm does one basic update step for each vertex. That is, it does n basic update steps. If you do not count the initialization of the first vertex, the you get n-1 updates, and either answer is good.
Suppose that you use the merge/together algorithm discussed in class to manage connections in a graph. Show how the boss array changes as each of the following operations are done. Use the algorithm that does not do either of the improvements -- the basic algorithm. Use the variant where merge always makes its second parameter's leader the new boss of the first parameter's leader.
In the diagram, the merge function is abbreviated m. So, for example m(2,4) indicates that you should merge 2 and 4.
i boss[i] i boss[i] i boss[i] i boss[i]
1 1 1 _5__ 1 _5__ 1 _5__
2 2 2 _2__ 2 _2__ 2 _4__
m(1,5) m(5,2) m(5,4)
3 3 --------> 3 _3__ --------> 3 _3__ --------> 3 _3__
4 4 4 _4__ 4 _4__ 4 _4__
5 5 5 _5__ 5 _2__ 5 _2__
Suppose that a linked list is built from list cells, where each cell has the following type.
struct ListCell
{
ListCell* next;
int item;
ListCell(int i, ListCell* n)
{
next = n;
item = i;
}
};
Write a function called copylist that will produce a copy
of a linked list. The copy must be built out of new list cells.
ListCell* copylist(const ListCell* L)
{
if(L == NULL) return NULL;
else return new ListCell(L->item, copylist(L->next));
}
Using the type ListCell from the preceding problem, write a function called take such that take(n,L) returns the length n prefix of list L, using new list cells. This function must not modify list L. If L has fewer than n members, then take(n, L) should produce a copy of L.
ListCell* take(int n, const ListCell* L)
{
if(L == NULL) return NULL;
else if(n == 0) reutrn NULL;
else return new ListCell(L->item, take(n-1, L->next));
}