Advance Algorithm MCQ
Question 1 : Another name for Jarvis march algorithm to find convex hull is
- Gift wrapping
- Bin packing
- Segment linking
- Region mapping
Question 2 : Arrange the following in the increasing order of their asymptotic complexity in big theta notation 2n, log n, n! , n
- 2n < log n < n! < n
- 2n < n< n! < log n
- n < log n < 2n < n!
- log n < n < 2n < n!
Question 3 : The number of black nodes from the root to a node is the node's____ ______; the uniform number of black nodes in all paths from root to the leaves is called the ____ _____ of the red–black tree.
- Black depth, Black height
- Black height, black depth
- red depth, red height
- red height, red depth
Question 4 : Let X is a problem that belongs to the class NP. Then which one of the following is TRUE?
- There is no polynomial time algorithm for X.
- If X can be solved deterministically in polynomial time, then P = NP.
- If X is NP-hard, then it is NP-complete.
- X may be undecidable.
Question 5 : In a B-tree of order n, root node contains how many minimum keys?
- (n - 1)/2
Question 6 : Recursion tree is used for?
- solving recurrences
- solving iterative relations
- analyzing loops
- calculating the time complexity of any code
Question 7 : How many cases are there in under master method?
Question 8 : The black height of a red black tree is
- Black height of its root
- Black height of a node
- Red height of a node
- Height of a tree
Question 9 : Closest pair algorithm using brute force performs which basic operation
- Euclidean distance
- Manhattan distance
Question 10 : When to prefer Red-black trees over AVL trees?
- When log(nodes) time complexity is needed.
- When more search operations are needed.
- When there are more insertions or deletions.
- When tree must be balanced
Question 11 : Which of the terms is not used in a linear programming problem?
- Slack variables
- Objective function
- Concave region
- Feasible solution
Question 12 : If T(n) = T(n/2) + n, then the complexity will be as follows:
- O(log n)
- O(n.log n)
Question 13 : Which method of amortized analysis keeps the same amortized cost for all the operations?
- Aggregate Analysis
- Accounting Method
- Potential Method
- Dynamic Table
Question 14 : In what time can an augmented path be found?
- O(|E| log |V|)
- O(|E|2 log |V|)
Question 15 : In LPP, the optimal value of the objective function is attained at the points
- Given by intersection of inequations with axes only
- Given by intersection of inequations with x-axis only
- Given by corner points of the feasible region.
- Given by intersection of inequations with y-axis only
Question 16 : In a binomial tree, the key of a node is ______ the key of its parent.
- greater than
- greater than or equal to
- less than
- less than or equal to
Question 17 : Problems that cannot be solved by any algorithm are called?
- tractable problems
- intractable problems
- undecidable problems
- decidable problems
Question 18 : Let f1(n) and f2(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is always true?
- f2(n) = Omega(f1(n))
- f2(n) = theta(f1(n))
- f2(n) = O(f1(n))
- f2(n) = o(f1(n))
Question 19 : Push Relabel algorithm is used to find
- finding a flow between source and sink that is maximum
- finding a flow between source and sink that is minimum
- finding the shortest path between source and sink
- computing a minimum spanning tree
Question 20 : In a binary max heap containing n numbers, the smallest element can be found in time
Question 21 : For vectors p1 and p2 to check if p1 is clockwise from p2 with respect to origin(0,0) which of the following is true:
- p1 × p2 is +ve
- p1 × p2 is -ve
- p1 × p2 is 0
- p1 and p2 are collinear, pointing in either opposite or same direction.
Question 22 : How many nodes a binomial tree Bk consists of?
Question 23 : The complexity of the ford fulkerson algorithm is
Question 24 : BINOMIAL_HEAP_MERGE returns a root list H that is sorted by _____ degree
- monotonically decreasing
- monotonically increasing
- Initially increasing, later decreasing
Question 25 : The flow from vertex u to vertex v is the negative of the flow in reverse direction is called as
- Capacity constraint
- Skew Symmetry
- Flow conservation property
- Residual Capacity
Question 26 : During the execution of BINOMIAL_HEAP_UNION, how many maximum roots of a given degree can be there on the root list of Binomial Heap H.
Question 27 : Which asymptotic notation is used to show loose upperbound
- Big O
- Small o
Question 28 : What is the special property of red-black trees and what root should always be?
- A colour of a node is either red or black and root should always be black colour only
- height of the tree
- pointer to next node
- A colour which is either green or black
Question 29 : Calculate complexity of the given recurrence equation. T(n) = 4T(n/2) + n2
- ϴ(n logn)
- ϴ(n2 log n)
Question 30 : The running time of graham scan Algorithm for solving convex hull is(n=number of points in set Q).