NEW
Font size
S
M
L
XL
WorksheetsUnit 2 MCQ Class Test
Total questions: 80
Worksheet time: 40mins
Name
Class
Date
1.
In the Hiring Problem, what is the expected number of times a candidate is hired out of n applicants?
a)
O(n²)
b)
O(n log n)
c)
O(log n)
d)
O(ln n)
2.
In the Hiring Problem, the best candidate selection uses which probabilistic concept?
a)
Uniform random permutation
b)
Binomial distribution
c)
Poisson distribution
d)
Gaussian distribution
3.
If 100 candidates are interviewed randomly, the expected hires are approximately equal to
a)
1
b)
10
c)
5
d)
log(100)
4.
The main purpose of using indicator random variables in analysis is to
a)
Represent probabilistic events numerically
b)
Reduce time complexity
c)
Implement random sampling
d)
Optimize recursive calls
5.
Which of the following is not true about indicator random variables?
a)
It can take any real number value
b)
It represents an event
c)
It takes values 0 or 1
d)
It simplifies probabilistic calculations
6.
In randomized algorithms, the expected running time is calculated using
a)
Worst-case input
b)
Average over all random choices
c)
Best-case input
d)
Fixed deterministic input
7.
Randomized algorithms improve performance mainly by
a)
Deterministic sorting
b)
Random input distribution
c)
Introducing randomness in decision steps
d)
Fixed control flow
8.
Suppose an algorithm’s expected time is T(n)=O(n)T(n) = O(n)T(n)=O(n) but worst-case is O(n2)O(n^2)O(n2). What does this indicate?
a)
Algorithm is always optimal
b)
Algorithm is inefficient
c)
Randomized algorithm with low expected cost
d)
Deterministic algorithm
9.
Which type of analysis evaluates the expected performance over all possible inputs?
a)
Worst-case analysis
b)
Best-case analysis
c)
Amortized analysis
d)
Probabilistic analysis
10.
For a fair coin flipped n times, the expected number of heads can be expressed using
a)
n/2
b)
2n
c)
√n
d)
log n
11.
The advantage of probabilistic analysis is that it
a)
Ignores random factors
b)
Considers the distribution of inputs
c)
Always yields exact results
d)
Avoids expected value computation
12.
If XiX_iXi is an indicator variable for candidate i being hired, then total hires =
a)
∑Xi\sum X_i∑Xi
b)
max(Xi)\max(X_i)max(Xi)
c)
Xi2X_i^2Xi2
d)
Xi+1X_i + 1Xi+1
13.
In the Hiring Problem, the total cost includes
a)
Interview cost only
b)
Hiring cost only
c)
Both interview and hiring costs
d)
None
14.
Which statement best describes randomized quicksort?
a)
Always produces same pivot
b)
Uses deterministic partition
c)
Uses random pivot selection to reduce expected cost
d)
Avoids recursion
15.
The expected number of comparisons in randomized quicksort is
a)
O(n²)
b)
O(n log n)
c)
O(log n)
d)
O(n)
16.
Probabilistic analysis helps mainly when
a)
Input is adversarial
b)
Input pattern is unknown
c)
Input size is small
d)
Algorithm is deterministic
17.
Indicator random variables are used in the Hiring Problem to
a)
Count number of hires
b)
Determine time complexity
c)
Select next candidate
d)
Generate random numbers
18.
Randomized algorithms can outperform deterministic ones in
a)
Every case
b)
Adversarial input cases
c)
Only sorted inputs
d)
Small datasets
19.
If a randomized algorithm fails with probability 1/100, how can reliability be improved?
a)
Run once
b)
Run multiple times independently
c)
Fix random seed
d)
Increase input size
20.
In probabilistic analysis, expectation linearity is used to
a)
Simplify computation of expected values
b)
Increase execution time
c)
Reduce algorithmic steps
d)
Generate random numbers
21.
In the Hiring Problem with 10 candidates, what is the expected number of hires? (Use E=H10≈ln(10)+0.577E = H_{10} ≈ \ln(10) + 0.577E=H10≈ln(10)+0.577)
a)
2.3
b)
3.1
c)
3.9
d)
4.5
22.
If interview cost = ₹10 and hiring cost = ₹100, and expected hires = 3, total expected cost for 10 candidates is
a)
₹130
b)
₹310
c)
₹400
d)
₹430
23.
For 20 candidates, expected number of hires ≈ H20≈ln(20)+0.577H_{20} ≈ \ln(20) + 0.577H20≈ln(20)+0.577. Compute approximate value.
a)
2
b)
3
c)
3.6
d)
4.2
24.
If a random algorithm succeeds with probability 0.8, what is the probability it succeeds at least once in 3 independent runs?
a)
0.992
b)
0.952
c)
0.488
d)
0.216
25.
A fair coin is flipped 10 times. Expected number of heads = ?
a)
2
b)
5
c)
8
d)
10
26.
In a randomized quicksort with 8 elements, expected comparisons ≈ 2nlnn=2×8×2.082n \ln n = 2×8×2.082nlnn=2×8×2.08. Value = ?
a)
25.6
b)
30
c)
33.3
d)
40
27.
If expected hires = ln(n) + 0.577, what is the expected number of hires for n = 50?
a)
3.9
b)
4.5
c)
5.5
d)
6.2
28.
In a randomized algorithm, probability of failure = 0.05 per run. Probability of failure after 5 independent runs = ?
a)
0.25
b)
0.05
c)
0.0025
d)
0.0003
29.
Suppose XiX_iXi = 1 if candidate i is hired. If n=5, expected total hires = ? (Use E[X]=H5E[X] = H_5E[X]=H5)
a)
1.5
b)
2.2
c)
3
d)
3.5
30.
Expected value of indicator random variable for event with probability 0.4 = ?
a)
0
b)
0.4
c)
0.5
d)
1
31.
For a biased coin (P(head)=0.6), expected number of heads in 10 tosses = ?
a)
4
b)
5
c)
6
d)
7
32.
In hiring problem, interview cost = ₹5, hiring cost = ₹50, n=12. Expected hires = ln(12)+0.577=3.0. Total expected cost = ?
a)
₹60
b)
₹75
c)
₹165
d)
₹210
33.
Randomized quicksort expected comparisons for 10 elements ≈ 2nlnn=2×10×2.32n \ln n = 2×10×2.32nlnn=2×10×2.3. Value = ?
a)
36
b)
40
c)
46
d)
50
34.
If a randomized algorithm has 90% success probability per trial, how many independent runs are needed for ≥99% success?
a)
1
b)
2
c)
3
d)
4
35.
A dice rolled 6 times. Expected number of times “4” appears = ?
a)
1
b)
2
c)
3
d)
6
36.
If E[X]=2.5E[X] = 2.5E[X]=2.5 and E[Y]=3.5E[Y] = 3.5E[Y]=3.5, what is E[X+Y]E[X + Y]E[X+Y]?
a)
5.5
b)
6
c)
7
d)
9
37.
Probability that a randomized algorithm produces the correct output = 0.7. Expected number of correct outputs in 10 runs = ?
a)
5
b)
6
c)
7
d)
8
38.
A candidate is hired if better than previous best. For 8 candidates, probability that 5th candidate is hired = ?
a)
2025-01-08 00:00:00
b)
2025-01-05 00:00:00
c)
2025-01-04 00:00:00
d)
2025-01-03 00:00:00
39.
For 100 candidates, expected number of hires = ln(100)+0.577 = ?
a)
3.9
b)
4.5
c)
5.2
d)
6
40.
Randomized algorithm success rate = 0.9. Probability of failing all 5 runs = ?
a)
0.59
b)
0.49
c)
1e-05
d)
0.0001
41.
A company interviews 20 candidates randomly. Based on the hiring problem, which strategy minimizes cost and maximizes quality?
a)
Hire the first candidate
b)
Hire every 5th candidate
c)
Hire only when better than all previous
d)
Hire last candidate
42.
A recruitment agency follows a random interview sequence. What is the expected number of times they will hire out of 12 candidates?
a)
2
b)
3
c)
4
d)
5
43.
A data scientist uses a randomized quicksort to handle 1,000,000 records. Why is it preferred over deterministic quicksort?
a)
Random pivot avoids worst-case input patterns
b)
Deterministic sorting is faster
c)
Uses less memory
d)
It avoids recursion
44.
In a hiring system, each candidate has equal chance of being best so far. What is the probability that the 6th candidate is hired?
a)
2025-01-06 00:00:00
b)
2025-01-05 00:00:00
c)
2025-01-04 00:00:00
d)
2025-01-03 00:00:00
45.
An HR team wants to predict hiring cost. If each interview costs ₹50 and hiring cost is ₹500, and expected hires = 4, total expected cost = ?
a)
₹200
b)
₹700
c)
₹900
d)
₹1,100
46.
A programmer runs a randomized algorithm 5 times with success probability 0.9 each run. What is the chance it succeeds at least once?
a)
0.9
b)
0.99
c)
0.95
d)
0.59
47.
A company compares deterministic vs. randomized algorithms for large datasets. Which approach performs better on unpredictable input?
a)
Deterministic
b)
Randomized
c)
Greedy
d)
Divide and Conquer
48.
A random sampling algorithm is used to estimate average marks of 10,000 students. What property ensures unbiased estimation?
a)
Deterministic selection
b)
Equal probability sampling
c)
Fixed interval sampling
d)
Stratified selection
49.
A randomized algorithm gives wrong answers 5% of the time. If repeated 3 times independently, probability of at least one correct output is:
a)
0.85
b)
0.95
c)
0.997
d)
0.999
50.
A company uses indicator random variables to count employees exceeding target. If 60% meet target, expected indicators out of 100 = ?
a)
40
b)
50
c)
60
d)
70
51.
In randomized quicksort, worst case arises when pivot is always smallest element. Probability of this case for n elements = ?
a)
1/n
b)
1/n²
c)
log n
52.
An algorithm uses randomness to choose hash functions for data storage. Why does this improve performance?
a)
Reduces hash collisions
b)
Increases collisions
c)
Increases cost
d)
Slows retrieval
53.
A start-up interviews 15 candidates sequentially. They decide to hire a candidate only if better than all seen so far. Expected hires = ?
a)
2
b)
3
c)
4
d)
5
54.
A network routing algorithm picks random paths to reduce congestion. What concept supports its efficiency?
a)
Probabilistic load balancing
b)
Fixed routing
c)
Greedy scheduling
d)
Deterministic pathfinding
55.
In a coin-toss experiment, algorithm A runs successfully only if at least one head appears in 3 tosses. Probability of success = ?
a)
0.5
b)
0.75
c)
0.875
d)
0.9
56.
A company estimates expected delivery delays using probabilistic analysis. Why is this useful?
a)
Handles uncertain conditions
b)
Improves fixed timing
c)
Removes randomness
d)
Ignores real data
57.
Randomized quicksort chooses pivot randomly for 8 elements. Expected comparisons ≈ 2nlnn2n \ln n2nlnn. Value = ?
a)
20
b)
25
c)
33
d)
40
58.
If an algorithm’s success probability is 0.8, how many independent runs are needed for 99% overall success?
a)
2
b)
3
c)
4
d)
5
59.
An engineer models algorithm behavior using indicator variables XiX_iXi. If 5 of 10 events have P=0.3, expected total = ?
a)
2
b)
3
c)
4
d)
5
60.
In a hiring simulation, if expected hires = ln(n) + 0.577 for n=25, what is the expected value?
a)
3
b)
3.5
c)
4
d)
5
61.
Assertion (A): In the Hiring Problem, every candidate has an equal probability of being the best so far. Reason (R): Candidates are interviewed in a random order.
a)
A and R are true, and R explains A
b)
A true, R false
c)
A false, R true
d)
Both false
62.
A: Indicator random variables can take only two values, 0 and 1. R: They are used to indicate whether an event occurs or not.
a)
Both A and R true, and R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
63.
A: The expected number of hires in the Hiring Problem with n candidates is approximately ln(n) + 0.577. R: The probability of hiring any candidate i is 1/i.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
64.
A: Randomized algorithms always produce the same result for the same input. R: Randomness affects control flow, not output.
a)
Both true
b)
Both false
c)
A false, R true
d)
A true, R false
65.
A: Probabilistic analysis focuses on analyzing the expected behavior of algorithms. R: It assumes inputs are randomly distributed.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
66.
A: Randomized algorithms perform better against adversarial inputs. R: Randomness prevents the adversary from predicting the algorithm’s choices.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
67.
A: Indicator random variables help compute expectations easily. R: The expected value of an indicator variable equals the probability of the event.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
68.
A: In the Hiring Problem, hiring cost dominates interview cost when n is large. R: Expected number of hires increases linearly with n.
a)
Both true
b)
Both false
c)
A true, R false
d)
A false, R true
69.
A: Randomized quicksort has an expected time complexity of O(n log n). R: Random selection of pivots reduces chance of worst-case partitions.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
70.
A: Probabilistic analysis helps in estimating expected performance over all inputs. R: It considers the average of best and worst cases.
a)
Both true
b)
Both false
c)
A true, R false
d)
A false, R true
71.
A: Expected value can be found by summing probabilities of all possible outcomes. R: Linearity of expectation applies even if events are dependent.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
72.
A: In the Hiring Problem, the first candidate is always hired. R: There is no previous candidate to compare with.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
73.
A: Randomized algorithms are always faster than deterministic ones. R: Randomness ensures optimal performance in all cases.
a)
Both true
b)
Both false
c)
A true, R false
d)
A false, R true
74.
A: Expected number of heads in 10 fair coin flips is 5. R: Each coin flip has equal probability of being head or tail.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
75.
A: Randomization can reduce algorithm complexity in expectation. R: It allows uniform exploration of input possibilities.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
76.
A: The use of indicator variables simplifies the computation of expected number of events. R: They replace complex summations with binary random variables.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
77.
A: Randomized algorithms eliminate the possibility of worst-case performance. R: Random choices guarantee the best outcomes.
a)
Both true
b)
Both false
c)
A true, R false
d)
A false, R true
78.
A: In probabilistic analysis, expected performance depends on input distribution. R: It assumes all inputs are equally likely.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
79.
A: Randomized algorithms can have lower expected cost than deterministic ones. R: Randomness can avoid pathological input cases.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
80.
A: The expected number of hires in the Hiring Problem is logarithmic in n. R: The probability of hiring decreases with each candidate.
a)
Both true, R explains A
b)
Both true, R does not explain A
c)
A true, R false
d)
Both false
Reset
