GATE CSE 2006 | Searching and Sorting Question 32 | Algorithms

Algorithms

Complexity Analysis and Asymptotic Notations

Marks 1 Marks 2

Searching and Sorting

Marks 1 Marks 2

Divide and Conquer Method

Greedy Method

P and NP Concepts

Dynamic Programming

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Given two arrays of numbers a₁,......,a_n and b₁,......, b_n where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that a_i+a_i+1......a_j = b_i+b_i+1......b_j or report that there is not such span,

Takes O(3ⁿ) and $$\Omega(2^{n})$$ time if hashing is permitted

Takes O(n³) and $$\Omega(n^{2.5})$$ time in the key comparison model

Takes θ(n) time and space

Takes $$O(\sqrt n)$$ time only if the sum of the 2n elements is an even number

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)

$$O(n \log \log n)$$

$$\Theta(n \log n)$$

$$\Omega(n \log n)$$

$$\Omega\left(n^{3/2}\right)$$

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Let G(V, E) an undirected graph with positive edge weights. Dijkstra's single-source shortest path algorithm can be implemented using the binary heap data structure with time complexity:

$$O\left( {{{\left| V \right|}^2}} \right)$$

$$O\left(|E|+|V|\log |V|\right)$$

$$O\left(|V|\log|V|\right)$$

$$O\left(\left(|E|+|V|\right)\log|V|\right)$$

GATE CSE 2004

MCQ (Single Correct Answer)

-0.6

The elements 32, 15, 20, 30, 12, 25, 16, are inserted one by one in the given order into a max Heap. The resultant max Heap is