Q.1 What is the main goal of algorithm design?
To make programs longer
To solve problems efficiently
To use more memory
To avoid coding
Explanation - Algorithm design focuses on solving computational problems in the most efficient way possible in terms of time and space.
Correct answer is: To solve problems efficiently
Q.2 Which of the following is NOT a characteristic of a good algorithm?
Finiteness
Definiteness
Ambiguity
Input/Output
Explanation - A good algorithm should not be ambiguous; each step must be clear and precise.
Correct answer is: Ambiguity
Q.3 What is meant by the time complexity of an algorithm?
The memory used by the algorithm
The number of steps an algorithm takes relative to input size
The number of bugs in the algorithm
The speed of the processor
Explanation - Time complexity measures the growth of computational steps with respect to input size.
Correct answer is: The number of steps an algorithm takes relative to input size
Q.4 Which notation is commonly used for asymptotic upper bound analysis?
Big-O
Big-Theta
Big-Omega
Little-o
Explanation - Big-O notation describes the asymptotic upper bound of an algorithm's time or space complexity.
Correct answer is: Big-O
Q.5 Which step in algorithm design ensures correctness?
Optimization
Verification
Implementation
Compilation
Explanation - Verification ensures that the algorithm solves the intended problem correctly for all valid inputs.
Correct answer is: Verification
Q.6 An algorithm must terminate after a finite number of steps. This property is called?
Finiteness
Definiteness
Correctness
Optimality
Explanation - Finiteness ensures that the algorithm terminates after a limited number of steps.
Correct answer is: Finiteness
Q.7 Which design paradigm is used in Merge Sort?
Dynamic Programming
Divide and Conquer
Greedy
Backtracking
Explanation - Merge Sort works by dividing the problem into subproblems, solving them, and combining the results.
Correct answer is: Divide and Conquer
Q.8 What does space complexity of an algorithm refer to?
The size of input
The amount of memory required
The time taken
The number of operations
Explanation - Space complexity refers to the amount of memory used by an algorithm, including input storage, auxiliary space, and recursion stack.
Correct answer is: The amount of memory required
Q.9 Which is NOT a common algorithm design paradigm?
Divide and Conquer
Greedy
Recursion Tree
Dynamic Programming
Explanation - Recursion trees are tools for analyzing recurrences, not a design paradigm.
Correct answer is: Recursion Tree
Q.10 What does the 'correctness' of an algorithm mean?
It runs fast
It produces the expected output for all valid inputs
It uses less memory
It is easy to code
Explanation - Correctness refers to whether the algorithm always gives the right result for all valid inputs.
Correct answer is: It produces the expected output for all valid inputs
Q.11 Which term describes the problem of designing algorithms for the best performance?
Optimization
Verification
Validation
Debugging
Explanation - Optimization involves designing an algorithm to run in the most efficient way possible.
Correct answer is: Optimization
Q.12 In algorithm analysis, what does input size usually refer to?
Memory size
CPU speed
Number of elements in the input
Program length
Explanation - Input size typically refers to the number of items or elements the algorithm needs to process.
Correct answer is: Number of elements in the input
Q.13 Which one is the worst-case complexity of Linear Search?
O(1)
O(n)
O(log n)
O(n log n)
Explanation - In the worst case, Linear Search may need to scan all n elements.
Correct answer is: O(n)
Q.14 What is the role of pseudocode in algorithm design?
To execute the algorithm
To represent the algorithm in machine code
To describe the algorithm in a human-readable form
To optimize memory usage
Explanation - Pseudocode is a simplified representation of the steps of an algorithm for better understanding.
Correct answer is: To describe the algorithm in a human-readable form
Q.15 Which of the following problems is NP-complete?
Sorting
Searching
Traveling Salesman Problem
Binary Search
Explanation - The Traveling Salesman Problem is a classical NP-complete problem that has no known polynomial-time solution.
Correct answer is: Traveling Salesman Problem
Q.16 Why do we analyze algorithms?
To increase code length
To predict performance
To avoid coding
To make hardware faster
Explanation - Analyzing algorithms helps us predict their performance in terms of time and memory usage.
Correct answer is: To predict performance
Q.17 Which of the following is a Greedy algorithm application?
Binary Search
Dijkstra’s Shortest Path
Merge Sort
Heap Sort
Explanation - Dijkstra’s algorithm is based on the Greedy paradigm as it selects the shortest available edge at each step.
Correct answer is: Dijkstra’s Shortest Path
Q.18 What is the best case time complexity of Quick Sort?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - In the best case, Quick Sort divides the array evenly at each partition step, resulting in O(n log n).
Correct answer is: O(n log n)
Q.19 Which property of algorithms ensures that every step is clearly defined?
Correctness
Definiteness
Finiteness
Efficiency
Explanation - Definiteness means each step of the algorithm is clearly and unambiguously defined.
Correct answer is: Definiteness
Q.20 Which notation gives the asymptotic tight bound of an algorithm?
Big-O
Big-Theta
Big-Omega
Little-o
Explanation - Big-Theta gives both lower and upper bounds tightly, representing the exact asymptotic behavior.
Correct answer is: Big-Theta
Q.21 What is the recurrence relation for Merge Sort?
T(n) = 2T(n/2) + O(n)
T(n) = T(n-1) + O(1)
T(n) = T(n/2) + O(1)
T(n) = T(n-1) + O(n)
Explanation - Merge Sort divides the array into two halves and merges them in O(n) time, giving the recurrence relation T(n) = 2T(n/2) + O(n).
Correct answer is: T(n) = 2T(n/2) + O(n)
Q.22 Which design technique does Dynamic Programming rely on?
Overlapping Subproblems and Optimal Substructure
Greedy choice property
Divide and Conquer
Randomization
Explanation - Dynamic Programming is based on overlapping subproblems and the principle of optimal substructure.
Correct answer is: Overlapping Subproblems and Optimal Substructure
Q.23 What is the worst-case time complexity of Binary Search?
O(n)
O(log n)
O(n log n)
O(1)
Explanation - Binary Search divides the array in half at each step, leading to logarithmic time complexity.
Correct answer is: O(log n)
Q.24 Which is faster on average: Linear Search or Binary Search?
Linear Search
Binary Search
Both are same
Depends on processor
Explanation - Binary Search is faster than Linear Search for large datasets since it runs in O(log n) instead of O(n).
Correct answer is: Binary Search
Q.25 What is the main difference between worst-case and average-case analysis?
Worst-case assumes the easiest input, average-case assumes the hardest
Worst-case assumes the hardest input, average-case assumes expected input
Both assume hardest input
Both assume easiest input
Explanation - Worst-case considers the most time-consuming input, while average-case considers typical expected inputs.
Correct answer is: Worst-case assumes the hardest input, average-case assumes expected input