ABOUT THE COURSE :
This course will cover basic concepts in the design and analysis of algorithms.
Asymptotic complexity, O() notation
Sorting and search
Algorithms on graphs: exploration, connectivity, shortest paths, directed acyclic graphs, spanning trees
Design techniques: divide and conquer, greedy, dynamic programming
Data structures: heaps, union of disjoint sets, search trees
Intractability
CRITERIA TO GET A CERTIFICATE
Average assignment score = 25% of average of best 6 assignments out of the total 8 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100
Final score = Average assignment score + Exam score
YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.
REMEMBER :- We are giving the best answer not 100% confirm answer so don't copy the answer blindly. Research about answers it is possible that the answer is different from this blog.
1. Suppose that the following is a binary search tree. The letters indicate the names of the nodes, not the values that are stored.
What is the successor node, in terms of value, of the node B?
A
E
H
M
2. We have n distinct values stored in a binary search tree. Define the height of a tree to be the number of nodes in the longest path from root to leaf. Which of the following statements is not true?
If the root is the median value, the height of the tree is at most n/2.
If the root is the median value, the height of the tree is at most log n.
The height of the tree is at least log n.
The height of the tree is at most n.
3. Suppose we have some values stored in a binary search tree of height n. Which of the following statements is true?
The number of elements in the tree is at most n.
The number of elements in the tree is at least n.
The number of elements in the tree is at least 2n.
The number of elements in the tree is at most n log n.
4. Preorder traversal prints a tree by first listing the value at the root and then recursively listing the values of the left and right subtrees.
function preOrder(t) {
if (t != NIL) {
print(t.value);
preOrder(t.left);
preOrder(t.right);
}
}
What is the complexity of preorder traversal for a binary search tree with n nodes?
O(log n) if the tree is balanced, O(n2) otherwise.
O(n) if the tree is balanced, O(n log n) otherwise.
O(n log n) whether the tree is balanced or unbalanced.
O(n) whether the tree is balanced or unbalanced.
5. The preorder traversal of a binary search tree with integer values produces the following sequence: 35, 23, 26, 46, 40, 39, 41. What is the value of the right child of the root of the tree?
23
39
40
46