Q.1 What is the main objective of the Activity Selection Problem?
To minimize the number of activities selected
To maximize the number of non-overlapping activities
To minimize the finishing time of all activities
To select activities with the shortest duration
Explanation - The Activity Selection Problem aims to select the maximum number of activities that do not overlap in time, ensuring optimal scheduling.
Correct answer is: To maximize the number of non-overlapping activities
Q.2 Which algorithmic strategy is used to solve the Activity Selection Problem?
Dynamic Programming
Greedy Algorithm
Divide and Conquer
Backtracking
Explanation - The problem is solved using a greedy strategy, always choosing the next activity with the earliest finishing time that is compatible.
Correct answer is: Greedy Algorithm
Q.3 In Activity Selection, why do we sort activities by their finishing time?
To minimize total duration
To maximize overlap
To always pick the earliest finishing activity
To simplify complexity to O(1)
Explanation - Sorting by finishing time ensures that the greedy choice leads to an optimal solution.
Correct answer is: To always pick the earliest finishing activity
Q.4 If there are n activities, what is the time complexity of solving the Activity Selection Problem using a greedy approach?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - Sorting the activities by finish time requires O(n log n), while the selection is O(n).
Correct answer is: O(n log n)
Q.5 Which condition must be satisfied for two activities to be compatible?
They must start at the same time
One must finish before the other starts
They must have equal duration
They must overlap at least partially
Explanation - Activities are compatible if one finishes before the next one begins, preventing overlap.
Correct answer is: One must finish before the other starts
Q.6 What is the greedy choice property in the Activity Selection Problem?
Choose the longest activity first
Choose the earliest starting activity
Choose the activity with the smallest duration
Choose the earliest finishing activity
Explanation - By choosing the earliest finishing activity, we leave maximum room for later activities, ensuring optimal results.
Correct answer is: Choose the earliest finishing activity
Q.7 Which step is performed first in solving the Activity Selection Problem?
Choose maximum duration activity
Sort activities by finish time
Sort activities by start time
Choose the first starting activity
Explanation - Sorting by finish time is necessary to apply the greedy choice effectively.
Correct answer is: Sort activities by finish time
Q.8 If two activities have the same finishing time, which one is chosen?
The one with later start time
The one with earlier start time
Any one can be chosen
The one with longest duration
Explanation - If finishing times are equal, either activity works as the greedy choice still holds.
Correct answer is: Any one can be chosen
Q.9 What is the optimal substructure property in Activity Selection?
Problem cannot be divided
Optimal solution contains optimal solutions of subproblems
Overlapping subproblems exist
No smaller subproblems possible
Explanation - After choosing an activity, the problem reduces to solving for remaining non-overlapping activities.
Correct answer is: Optimal solution contains optimal solutions of subproblems
Q.10 In which real-world scenario is Activity Selection Problem applicable?
CPU Scheduling
Memory Allocation
Graph Coloring
String Matching
Explanation - CPU scheduling with non-overlapping tasks is a direct application of activity selection.
Correct answer is: CPU Scheduling
Q.11 What data structure is commonly used to store activities?
Queue
Stack
Array of pairs (start, finish)
Graph adjacency list
Explanation - Activities are represented as (start, finish) pairs, often stored in an array for sorting.
Correct answer is: Array of pairs (start, finish)
Q.12 Which is the first activity chosen in the greedy method?
Earliest starting activity
Latest starting activity
Earliest finishing activity
Longest activity
Explanation - The greedy approach always starts with the activity that finishes earliest.
Correct answer is: Earliest finishing activity
Q.13 What happens if activities are sorted by start time instead of finish time?
The algorithm still works optimally
The algorithm may fail to give optimal solution
It reduces time complexity
It guarantees shortest schedule
Explanation - Sorting by start time does not guarantee maximum number of activities.
Correct answer is: The algorithm may fail to give optimal solution
Q.14 How is the greedy approach validated in Activity Selection?
By comparing with brute force
By using proof of correctness
By empirical testing only
By backtracking
Explanation - Mathematical proof shows that greedy choice gives the optimal solution for this problem.
Correct answer is: By using proof of correctness
Q.15 Which of the following best describes the Activity Selection Problem?
Interval Scheduling Problem
Pathfinding Problem
Subset Sum Problem
Sorting Problem
Explanation - It is a classic example of interval scheduling, selecting maximum number of non-overlapping intervals.
Correct answer is: Interval Scheduling Problem
Q.16 If there are n activities, how many activities can be selected in the worst case?
1
n
n/2
0
Explanation - In the worst case, all activities overlap, and only one can be selected.
Correct answer is: 1
Q.17 Which famous algorithm design problem is Activity Selection related to?
Knapsack Problem
Huffman Coding
Job Scheduling
Binary Search
Explanation - Activity selection is closely related to job scheduling with deadlines and constraints.
Correct answer is: Job Scheduling
Q.18 What happens if activities are not sorted before applying greedy selection?
Algorithm still works correctly
Algorithm fails to guarantee optimality
Algorithm becomes O(1)
It gives maximum activities always
Explanation - Sorting is crucial to ensure correctness of greedy choice.
Correct answer is: Algorithm fails to guarantee optimality
Q.19 Which mathematical concept supports greedy choice in this problem?
Graph Theory
Set Theory
Matroid Theory
Probability
Explanation - Matroid theory proves that greedy algorithms work for problems like activity selection.
Correct answer is: Matroid Theory
Q.20 If we use dynamic programming for Activity Selection, what would be its complexity?
O(n)
O(n^2)
O(log n)
O(n log n)
Explanation - DP solution requires checking all pairs, leading to O(n^2), unlike greedy O(n log n).
Correct answer is: O(n^2)
Q.21 What type of algorithm is Activity Selection considered?
Optimization Algorithm
Search Algorithm
Sorting Algorithm
Simulation Algorithm
Explanation - It optimizes the number of non-overlapping activities chosen.
Correct answer is: Optimization Algorithm
Q.22 What is the main advantage of greedy method in Activity Selection?
Simplicity and efficiency
Works for all problems
No sorting required
Better than DP always
Explanation - The greedy method is fast and easy to implement for this problem.
Correct answer is: Simplicity and efficiency
Q.23 If activities are already sorted by finish time, what is the runtime of the greedy selection step?
O(n)
O(n log n)
O(1)
O(n^2)
Explanation - After sorting, scanning through activities and selecting is linear in time.
Correct answer is: O(n)
Q.24 Which of the following is NOT an assumption of Activity Selection?
Activities have defined start and finish times
Activities cannot overlap
Activities may be interrupted
Activities must be non-preemptive
Explanation - The problem assumes activities are non-preemptive and must run fully.
Correct answer is: Activities may be interrupted
Q.25 Which field commonly uses Activity Selection Problem?
Operating Systems
Networking
Cryptography
Database Management
Explanation - Task scheduling in operating systems is a direct application of activity selection.
Correct answer is: Operating Systems