What is the purpose of a destructor for a class? What is the destructor for class River called? Under what circumstances is the destructor called?
A destructor recovers resources owned by an object. Typically, it deletes memory that the object owns, but that is physically outside the object.
The destructor for class River is called ~River.
The destructor is called any time an object is destroyed, for any reason.
Object-oriented programming in C++ can be used to make it impossible to violate the abstraction of an abstract data type.
What feature of C++ makes this possible?
The class, and private members of classes.
Programmers rarely deliberately sabotage their own work. Since programmers are not supposed to violate abstractions, why is it so important that a compiler prevent them from doing so? Can't programmers police themselves?
Even good programmers make mistakes, and the compiler should catch those mistakes wherever possible.
Programming teams often have some less experienced programmers who are likely to violate abstractions if permitted to do so. A compiler that disallows such violations gives the better programmers confidence that the less experienced programmers are not violating abstractions.
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?
25
/ \
/ \
/ \
60 40
/ \ / \
65 75 42 46
/
80
25
/ \
/ \
/ \
33 40
/ \ / \
60 75 42 46
/ \
80 65
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 step for each vertex. That is, it does n basic update steps.
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.
In the diagram, the merge function is abbreviated m. So, for example m(2,4) indicates that you should merge 2 and 4.
I presume that merge(A,B) tries to make A' point to B', rather than making B' point to A', where A' is the leader of A and B' is the leader of B.
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__
Using the type Node shown, write a function called PrintEvens that prints the even numbers in a binary search tree in descending order, one number per line, skipping the odd numbers in the tree. (n is even if n%2 == 0.) For example, if t is the tree shown in problem 11, then PrintEvens(t) would print the numbers 100, 20 and 16, one per line, in that order. The function should not destroy the tree.
struct Node {
int key;
Node* left;
Node* right;
Node(Node* l, int k, Node* r)
{
left = l;
key = k;
right = r;
}
};
void PrintEvens(Node* T)
{
if(T != NULL) {
PrintEvens(T->right);
if(T->key % 2 == 0) cout << T->key << endl;
PrintEvens(T->left);
}
}
The binary search tree implementation that was discussed in class was nonpersistent; the insert operation, for example, changed the tree. It is possible to implement binary search trees in a persistent way also, so that they compute new trees from old ones, without modifying the trees.
Using the type Node of the previous problem, write a function removeMin(t) that returns the tree that would result from removing the smallest value from tree t, but that does not alter tree t. If t is empty, then removeMin(t) should return an empty tree. For example, if t is the tree
81
/ \
20 100
\
65
/ \
50 70
then removeMin(t) should
return the following tree, without altering tree t.
81
/ \
65 100
/ \
50 70
The new tree that you construct can share
subtrees with t, as long as it does not change the subtrees.
Node* removeMin(const Node* t)
{
if(t == NULL) return NULL;
else if(t->left == NULL) return t->right;
else return new Node(removeMin(t->left), t->key, t->right);
}
Write a function that makes a copy of a binary search tree. The copy must use all new nodes. Use the type Node from the preceding question.
Node* copy(const Node* t)
{
if(t == NULL) return NULL;
else return new Node(t->left, t->key, t->right);
}
How long, to within a constant factor, does it take to insert a new value into a height-balanced binary search tree that has n values in it?
log2(n)
Suppose that you insert 25 into the following tree using the algorithm that does rotations to keep the tree height-balanced. What is the resulting tree?
81
/ \
20 100
/ \
16 65
81 65
/ \ / \
20 100 20 81
/ \ / \ \
16 65 16 25 100
/
25
before rotations after rotations
The answer is the tree on the right. It is obtained from the
tree on the left by doing a double rotation at the root.
Consider the following tree with integer keys.
25
/ \
10 30
/ \
26 50
Is this tree a binary search tree? That is, does it obey the ordering requirements?
Yes.
Ignoring the keys, is this tree height-balanced?
Yes.
If you were to use the standard (unbalanced) binary search tree insertion algorithm, show what this tree would look like after inserting 40.
25
/ \
10 30
/ \
26 50
/
40
Is the tree height-balanced after inserting 40, without rebalancing?
No.