AlgorithmsAsymptotic 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 topicwise distribution of questions. Unlimited Access, Unlimited Time, on Unlimited Devices!
View Sample Explanation or View Features.
Rs. 550.00 OR
How to register? Already Subscribed?
Question 1
Appeared in Year: 2014 (UGCNET)
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 (UGCNET)
Question
MCQ▾BigO 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 (UGCNET)
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 BigO estimate for the function given below?
Choices
Choice (4)  Response  

a.  
b.  
c.  
d. 
Question 5
Appeared in Year: 2019 (UGCNET)
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 (UGCNET)
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. 