Data Structures and Algorithms

Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is :

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

The median of n elements can be found in O(n) time. Which one of the following is correct about the complexity of quick sort, in which the median is selected as pivot?

The in order and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively The post order traversal of the binary tree is:

What is the time complexity of the following recursive function?

Int Do Something (int n) {
return 1;
else
return (Do Something (floor sqrt (n))) + n);

Consider the process of inserting an element into a Max Heap, where the Max Heap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is