Algorithms-Asymptotic Notation [GATE (Graduate Aptitude Test in Engineering) Computer Science]: Questions 1 - 6 of 6

Access detailed explanations (illustrated with images and videos) to 2122 questions. Access all new questions- tracking exam pattern and syllabus. View the complete topic-wise distribution of questions. Unlimited Access, Unlimited Time, on Unlimited Devices!

View Sample Explanation or View Features.

Rs. 550.00 -OR-

Question 1

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

Question

Match List-Ⅰ List-Ⅱ▾

Match the following: (December Paper III)

List-Ⅰ (Column I)List-Ⅱ (Column II)
(A)

Matrix chain multiplication

(i)

(B)

All pairs shortest paths

(ii)

(C)

Huffman

(iii)

(D)

Bucket sort

(iv)

Choices

Choice (4)Response
• (A)
• (B)
• (C)
• (D)

a.

• (i)
• (ii)
• (iv)
• (iii)

b.

• (ii)
• (i)
• (iii)
• (iv)

c.

• (iv)
• (ii)
• (i)
• (iii)

d.

• (i)
• (iv)
• (ii)
• (iii)

Question 2

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

Question

MCQ▾

Big-O estimates for the factorial function and the logarithm of the factorial function i.e.. and is given by (June paper II)

Choices

Choice (4)Response

a.

b.

c.

d.

Question 3

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

Question

MCQ▾

Given the following equalities:

for all fixed and , and .

Which of the following is true? (June paper III)

Choices

Choice (4)Response

a.

.

b.

.

c.

d.

.

Question 4

Asymptotic Notation

Question

MCQ▾

What is the Big-O estimate for the function given below?

Choices

Choice (4)Response

a.

b.

c.

d.

Question 5

Asymptotic Notation

Appeared in Year: 2019 (UGC-NET)

Question

MCQ▾

Give asymptotic upper and lower bound for given below. Assume is constant for .

(December)

Choices

Choice (4)Response

a.

b.

c.

d.

Question 6

Asymptotic Notation

Appeared in Year: 2019 (UGC-NET)

Question

MCQ▾

The following multithreaded algorithm computes transpose of a matrix in parallel: (December)

1. pTrans (X, Y, N)
2. ifN =1
3. thenY [1, 1] ⇽ X [1, 1]
4. elsepartitionXintofour (N / 2) × (N/2) submatricesX11, X12, X21, X22
5. partitionYintofour (N / 2) × (N/2) submatricesY11, Y12, Y21, Y22
6. spawnpTrans (X11, Y11, N/2)
7. spawnpTrans (X12, Y12, N/2)
8. spawnpTrans (X21, Y21, N/2)
9. spawnpTrans (X22, Y22, N/2)

What is the asymptotic parallelism of the algorithm?

Choices

Choice (4)Response

a.

b.

c.

d.

Developed by: