COURSE CODE: ECAP538
COURSE NAME: ALGORITHM DESIGN AND ANALYSIS
Time Allowed: 02:00 hrs. Max. Marks: 70
Read all the instructions carefully
1. There are 20 multiple choice and 3 descriptive questions in this exam.
2. Section - 1: contain(s) 20 question(s) and each question carries 2 mark(s). Each question in this
section has a time limit of 2 minutes. Once you go to next question, you can never come back to
the previously seen question in this section.
3. Section - 2: contain(s) 2 descriptive question(s) and each question carries 10 mark(s). Attempt any
1 question within 26 minutes in this section. You can navigate between the 2 questions in this
section.
4. Section - 3: contain(s) 2 descriptive question(s) and each question carries 10 mark(s). Attempt any
1 question within 27 minutes in this section. You can navigate between the 2 questions in this
section.
5. Section - 4: contain(s) 2 descriptive question(s) and each question carries 10 mark(s). Attempt any
1 question within 27 minutes in this section. You can navigate between the 2 questions in this
section.
6. You can skip a question if you do not know the answer by clicking on the Next button.
7. A correctly answered question will score the allocated mark.
8. Skipping a question without answering will result in 0 marks for that question
9. The entire exam is recorded along with all your actions during the exam.
10. Do not try to leave the test window during the exam.
11. Since this is a proctored exam, you will have to provide permissions to share your location,
webcam, microphone (and screen if the proctor demands).
12. Make sure to use the latest Chrome browser on Android, Windows, Linux, Mac OS. For iOS
devices, use only Safari browser.
Instructions for DESCRIPTIVE questions requiring SCAN & UPLOAD
13. Make sure to upload your scans immediately after you answer every question. Do NOT wait till the
end to avoid panic at the end.
14. The exam time is inclusive of time for scanning & uploading answers.
15. If using laptop + mobile for the exam, click on Open Test on laptop and click on Scan & Upload
on mobile.
16. If using laptop + mobile for the exam, when scanning and uploading from mobile, ensure that the
correct question is open on the laptop.
17. When clicking on Camera button on a smart phone for scanning and uploading, you have 2
camera applications available to scan the answer: your phone's native camera and an alternative
Low Memory Camera. Click on the Low Memory Camera in case your browser shows an error
due to low memory.
18. If you are using only mobile phone to take the exam, then click on “Open Test” button to start the
exam and click on "Camera" button under each question to scan the answer sheets.
Click Finish only after completion of the Exam.
Page | 1
Section 1: Attempt All the Questions
1. Which of these is a primitive operation?
A. Calling a method
B. Comparing two numbers
C. Indexing into an array
D. All of the above
2. The RAM model of computation stands for
A. Random Access Memory
B. Random Access Machine
C. Realtime Access Machine
D. None of the above
3. The RAM model of computation consists of
A. A read-only input tape
B. A write-only input tape
C. A fixed program
D. All of the above
4. The time complexity of merge sort is _______.
A. O (n)
B. O (1)
C. O (log n)
D. O (n log n)
5. Traversing of elements in merge sort is done in _______.
A. Preorder
B. Postorder
C. Inorder
D. None of the above
6. In merge sort, the list is considered as small, when it is having ____ element.
A. 0
B. 1
C. 2
D. 3
Page | 2
7. The time complexity of quick sort is
A. O (n)
B. O (log n)
C. O (n log n)
D. None of the above
8. Which data structure is used for sorting of elements in quick sort?
A. Stack
B. Queue
C. Tree
D. Graph
9. Out of these, the Dijkastra algorithm cannot work on ____.
A. Directed edges
B. Undirected edges
C. Negative edges
D. None of the above
10. The Dijkastra algorithm follows ___.
A. Dynamic programming
B. Greedy method
C. Divide and Conquer
D. Quick sort
11. The Dijkastra algorithm can work on
A. Directed graph
B. Undirected graph
C. Both of the above
D. None of the above
12. The Dijkastra algorithm always searches for _____ path.
A. Shortest
B. Longest
C. Equal
D. None of the above
13. Which of these follows the bottom-up approach?
A. Tabulation method
B. Memorization method
C. Both of the above
D. None of the above
Page | 3
14. Which data structure is used for solving problems of dynamic programming?
A. Queue
B. Stack
C. Tree
D. Graph
15. Out of these techniques, which one provides the fastest method for generating optimal
binary search tree?
A. Greedy method
B. Dynamic programming
C. Branch and bound
D. Divide and Conquer
16. In binary search tree, the left subtree always contains the elements ____ the root node.
A. Lesser than
B. Greater than
C. Equal to
D. None of the above
17. If there are 3 key elements, then the number of possible binary search trees will be
A. 3
B. 4
C. 5
D. 6
18. Find the odd one out.
A. Sum of Subsets
B. N Queens
C. Hamiltonian Cycle
D. Merge sort
19. N Queens problem can be efficiently solved using
A. Divide and Conquer
B. Backtracking
C. Dynamic Programming
D. Algebraic Manipulation
Page | 4
20. How many unique solutions are there for 8 Queens Problem?
A. 8
B. 4
C. 12
D. 16
Section 2: Attempt any one question out of two
1. Write the algorithm for quick sort and its partitioning. Explain it with the help of an example.
2. What are two methods of use in dynamic programming? Explain the difference between both.
Section 3: Attempt any one question out of two
1. Explain the process of solving all-pair shortest path problem with the help of an example.
Write its time complexity.
2. What are different algorithms for pattern matching? What is its element space?
Section 4: Attempt any one question out of two
1. Explain the method of calculation of lower bound for searching and sorting problem.
2. What is a non-deterministic algorithm? What is its use? Explain its phases and related terms .
--------------------------------------END OF QUESTION PAPER--------------------------------------------
Page | 5