GATE CSE 2009 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2009

MCQ (Single Correct Answer)

-0.3

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exist s.
Q: Finds whether any negative weighted cycle is reachable from the source.

P Only

Q Only

Both P and Q

Neither P nor Q

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

The running time of an algorithm is represented by the following recurrence relation:
$$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$$
Which one of the following represents the time complexity of the algorithm?

$$\Theta(n)$$

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

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

$$\Theta(n)$$

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

$$\Theta(n^2)$$

$$\Theta(n^2 \log n)$$

GATE CSE 2009

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2009 Algorithms - Greedy Method Question 20 English

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?

(b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

(b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

(b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

(b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

PREVIOUS NEXT

GATE CSE Papers

2023