New question. A rational number can be represented by a pair of integers, the numerator and the denominator. For example, the rational number with numerator 1 and denominator 3 stands for 1/3. The advantage is that some numbers that can only be represented approximately using type double can be represented exactly as ratios of integers. An abstract data type Rational is intended to represent rational numbers. So a member of type Rational is thought of as having a numerator and a denominator. Among the operations are a constructor that takes two integers (a numerator and a denominator) and initializes a rational number; an operation flip so that x.flip() makes x into its reciprocal; an operation multiplyBy so that x.multiplyBy(y) makes x into the product of x's current value and y, where y is a rational number; an operation getNumerator that returns the numerator, and an operation getDenominator that returns the denominator. (So x.getNumerator() is the numerator of x.) Rational numbers are always stored in a form where the numerator and denominator have no common factors. Instead of 3/6, you store 1/2. You cannot assume that somebody who uses this data type knows this convention. There is nothing wrong with creating a rational number with numerator 3 and denominator 6. But it you then ask for the numerator, it will be 1, not 3. This can be achieved by dividing the numerator and denominator by their greatest common divisor. Assume the function gcd(m,n) is available to you. You do not need to write it.
Write Rational in C++ as a class, including the constructor and methods flip, multiplyBy, getNumerator and getDenominator. Also provide a private method called reduce that reduces a rational number by dividing the numerator and denominator by their greatest common divisor. You will want to use reduce in some other functions.
Write a main program that creates rational numbers 1/3 and 3/7, calculates the product of those two numbers, and prints the product in the form numerator/denominator. (So it will print "1/7".)
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?
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?
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?
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
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.
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?
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 boss[i] i boss[i] i boss[i] i boss[i]
1 1 1 ____ 1 ____ 1 ____
2 2 2 ____ 2 ____ 2 ____
m(1,5) m(5,2) m(5,4)
3 3 --------> 3 ____ --------> 3 ____ --------> 3 ____
4 4 4 ____ 4 ____ 4 ____
5 5 5 ____ 5 ____ 5 ____
Using the type BSTNode 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 BSTNode {
int key;
BSTNode* left;
BSTNode* right;
BSTNode(int k, Node* l, Node* r)
{
left = l;
key = k;
right = r;
}
};
void PrintEvens(BSTNode* T)
{
}
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 BSTNode 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 BSTNode* t)
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)
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?
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
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?
Ignoring the keys, is this tree height-balanced?
If you were to use the standard (unbalanced) binary search tree insertion algorithm, show what this tree would look like after inserting 40.
Is the tree height-balanced after inserting 40, without rebalancing?