1- Find the greatest common divisor(gcd) by Euclid’s Algorithm of a and b with a
ID: 3798519 • Letter: 1
Question
1- Find the greatest common divisor(gcd) by Euclid’s Algorithm of a and b with a b
is given by
int gcd (int a, int b) {
int r = 0;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return r ;
}
Show that the number of operations of the while loop is no more than log(a) plus some
very small constant.
2- Draw the binary search tree by insert the following keys
44, 19, 69, 6, 24, 61, 82, 0, 7, 59, 62.
Then print the items using the level order, Pre-order, In-order, Post-order traversal.
3- Prove by Math. Induction that a perfect binary tree has 2h+1-1 nodes, where h is the
height of the tree.
Explanation / Answer
Ans.1.
Since a is replaced by b and b is replaced by a%b, therefore while loop executes not more than log a + constant(steps inside while loop)
Ans.2.
44
19 69
6 24 61 82
0 7 59 62
level order: [44], [19, 69], [6, 24, 61, 82], [0, 7, 59, 62]
pre order: 44, 19, 6, 0, 7, 24, 69, 61, 59, 62, 82
in order: 0, 6, 7, 19, 24, 44, 59, 61, 62, 69, 82
post order: 82, 62, 69, 61, 59, 44, 24, 19. 7, 6, 0
Ans. 3.
Base condition: h = 1, nodes = 2
Hypothesis:
It is true for h = n,
Therefore: nodes = 2n + 1 - 1
For h = n + 1, at new level, each node from previous level will give rise to 2 nodes, therefore:
nodes = 2(n+1) + 1 - 1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.