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

Choose Programs:

🎓 Study Material (1190 Notes): 2024-2025 Syllabus

Rs. 1000.00 -OR-

3 Year Validity (Multiple Devices)

Topic-wise Notes & SampleDetails

🎯 302 Numeric, 2894 MCQs (& PYQs) with Full Explanations (2024-2025 Exam)

Rs. 650.00 -OR-

3 Year Validity (Multiple Devices)

CoverageDetailsSample Explanation

Help me Choose & Register (Watch Video) Already Subscribed?

Question 1

Appeared in Year: 2014

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)

Edit

Question 2

Appeared in Year: 2014

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.

Edit

Question 3

Appeared in Year: 2014

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.

.

Edit

Question 4

Question MCQ▾

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

Choices

Choice (4)Response

a.

b.

c.

d.

Edit

Question 5

Appeared in Year: 2019

Question MCQ▾

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

(December)

Choices

Choice (4)Response

a.

b.

c.

d.

Edit

Question 6

Appeared in Year: 2019

Question MCQ▾

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

  1. p Trans (X, Y, N)
  2. if N =1
  3. then Y [1, 1] ⇽ X [1, 1]
  4. else partition X into four (N /2) × (N/2) submatrices X11, X12, X21, X22
  5. partition Y into four (N /2) × (N/2) submatrices Y11, Y12, Y21, Y22
  6. spawn p Trans (X11, Y11, N/2)
  7. spawn p Trans (X12, Y12, N/2)
  8. spawn p Trans (X21, Y21, N/2)
  9. spawn p Trans (X22, Y22, N/2)

What is the asymptotic parallelism of the algorithm?

Choices

Choice (4)Response

a.

b.

c.

d.

Edit