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. |
|
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. |
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. | . |
Question 4
Question MCQ▾
What is the Big-O estimate for the function given below?
Choices
Choice (4) | Response | |
---|---|---|
a. | ||
b. | ||
c. | ||
d. |
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. |
Question 6
Appeared in Year: 2019
Question MCQ▾
The following multithreaded algorithm computes transpose of a matrix in parallel: (December)
p Trans (X, Y, N)
if N =1
then Y [1, 1] ⇽ X [1, 1]
else partition X into four (N /2) × (N/2) submatrices X11, X12, X21, X22
partition Y into four (N /2) × (N/2) submatrices Y11, Y12, Y21, Y22
spawn p Trans (X11, Y11, N/2)
spawn p Trans (X12, Y12, N/2)
spawn p Trans (X21, Y21, N/2)
spawn p Trans (X22, Y22, N/2)
What is the asymptotic parallelism of the algorithm?
Choices
Choice (4) | Response | |
---|---|---|
a. | ||
b. | ||
c. | ||
d. |