Analysis and Design of Algorithms
Full explanation, worked examples & memory tricks in the app
Analysis and Design of Algorithms
English 18 leveled MCQs Free
Shared by a Veda teacher · Generated with Veda AI
Smart notes
1
What you'll study, topic by topic
Solved paper preview
Sample questions with model answers
Every question in the paper gets a full exam-length answer in the app — organised by marks, the way a topper writes it.
7 marks Long answer
Write binary search algorithm and analyze it for worst case time complexity. Represent its time complexity using Big-oh (O) notation.
Show answer outline
Binary search has a time complexity of O(log n).
The full exam-length answer is in the app.
7 marks Long answer
Solve following recurrence relation using suitable method and express your answer using Big-oh (O) notation. T(n) = T(n/6) + T(5n/6) + Θ(n)
Show answer outline
T(n) = O(n).
The full exam-length answer is in the app.
7 marks Long answer
Write greedy algorithm for activity selection problem. Give its time complexity. For following intervals, select the activities according to your algorithm. I1 (1-3), I2 (0-2), I3 (3-6), I4 (2-5), I5 (5-8), I6 (3-10), I7 (7-9).
Show answer outline
Time complexity is O(n log n), selected activities are I1, I3, I5, I7.
The full exam-length answer is in the app.
7 marks Long answer
Find the optimal way of multiplying following matrices using dynamic programming. Also indicate optimal number of multiplications required. A:2 x 3, B: 3 x 5, C:5 x 6, D: 6 x 2, E: 2 x 3.
Show answer outline
Optimal number of multiplications is 30.
The full exam-length answer is in the app.
7 marks Long answer
Given a text and a pattern, write the naive string matching algorithm to find all occurrences of the pattern in the text. Use the text "ABCABCABC" and the pattern "ABC". Also, give time complexity of naive string matching algorithm.
Show answer outline
Time complexity is O(n*m), where n is text length and m is pattern length.
The full exam-length answer is in the app.
7 marks Long answer
Show that Hamiltonian cycle is a NP problem.
Show answer outline
Hamiltonian cycle can be verified in polynomial time.
The full exam-length answer is in the app.
4 marks Medium answer
Define Omega and Theta notations with graph.
Show answer outline
Omega notation describes lower bounds, Theta describes tight bounds.
The full exam-length answer is in the app.
4 marks Medium answer
If P(n) = a0 + a1 n + a2 n^2 + ... + am n^m then prove that P(n) = Ω(n^m). Here a0, a1, a2 …..am are constants and am>0.
Show answer outline
P(n) is dominated by the term am n^m.
The full exam-length answer is in the app.
4 marks Medium answer
Write the recurrence relation for the quick sort on input instance: 15, 19, 20, 25, 32, 37, 50, 62, 70. Comment on the nature of input i.e. best case, average case or worst case.
Show answer outline
Recurrence is T(n) = T(k) + T(n-k-1) + O(n); average case.
The full exam-length answer is in the app.
4 marks Medium answer
What is knapsack problem? Using greedy algorithm find an optimal solution for fractional knapsack instance n=7, M =17, profits p[ ] = {10,5,15,7,6,16,4} and weights w[ ] = {2,3,5,7,1,4,1}.
Show answer outline
Optimal solution is to take items with maximum value/weight ratio until the knapsack is full.
The full exam-length answer is in the app.
4 marks Medium answer
Explain the backtracking strategy to solve optimization problem. Explain how it can be applied to find the solution for 4-queen problem.
Show answer outline
Backtracking explores all possible configurations and eliminates those that fail constraints.
The full exam-length answer is in the app.
4 marks Medium answer
Give example of any NP complete problem. Explain how to prove that particular problem is NP complete.
Show answer outline
Example: 3-SAT; prove by reduction from known NP-complete problems.
The full exam-length answer is in the app.
2 marks Short answer
Find Big-oh (O) notation of following functions f(n)=3n^6 + 2 n * lg n + 6n, h(n)= 3n^2 + 6n*lg n + 2n^2.5
Show answer outline
O(n^6)
The full exam-length answer is in the app.
2 marks Short answer
Prove that (n + 6)^3 = Θ(n^3).
Show answer outline
It can be shown using the definition of Θ notation.
The full exam-length answer is in the app.
2 marks Short answer
Arrange the following growth rates from the lowest to highest asymptotic order: O(n log n), O(n^2n), Ω(log n), O(n^0.5), O(n!), Ω(2^n), O(n^0.5 log n)
Show answer outline
Ω(log n), O(n^0.5), O(n^0.5 log n), O(n log n), O(n^2n), Ω(2^n), O(n!)
The full exam-length answer is in the app.
2 marks Short answer
What is Principle of Optimality in dynamic programming? Explain it with example.
Show answer outline
It states that an optimal solution to any instance of an optimization problem is composed of optimal solutions to its subproblems.
The full exam-length answer is in the app.
2 marks Short answer
Define P and NP problems. Also give example of each type of problem.
Show answer outline
P problems are solvable in polynomial time; NP problems are verifiable in polynomial time.
The full exam-length answer is in the app.
2 marks Short answer
What is a polynomial reduction? Explain its role in proving NP-completeness.
Show answer outline
Polynomial reduction transforms one problem into another in polynomial time.
The full exam-length answer is in the app.
Study it properly — free, in the app
The full Veda Bites deck, complete notes, spaced-repetition flashcards, leveled MCQs, tests and games for this kit — plus Daily Facts and the Arena, every day.