Back to Subject

Unit 4: Greedy techniques - Practice Quiz

CSE329 — Prelude To Competitive Coding 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What is the core idea behind the greedy algorithm paradigm?

Greedy problem solving paradigm Easy
A. Make the choice that looks best at each step
B. Break the problem into overlapping subproblems
C. Randomly select choices until a solution is found
D. Try all possible combinations exhaustively

2 In greedy algorithms, a "locally optimal choice" refers to a decision that is:

Locally optimal choice Easy
A. Best at the current step without considering the future
B. Based on solving all subproblems first
C. Best for the entire problem globally
D. Chosen at random from valid options

3 A greedy algorithm always produces a globally optimal solution when:

Global optimal choice Easy
A. All elements in the input are equal
B. The problem exhibits the greedy-choice property and optimal substructure
C. The input array is sorted in ascending order
D. The problem size is very small

4 In the Job Sequencing problem with deadlines, the goal is to:

Job Sequencing problem Easy
A. Minimize the number of jobs scheduled
B. Minimize the total time taken for all jobs
C. Schedule every job regardless of deadline
D. Maximize total profit by scheduling jobs before their deadlines

5 To apply the greedy strategy in Job Sequencing, jobs are typically sorted by:

Job Sequencing problem Easy
A. Increasing profit
B. Decreasing profit
C. Job name alphabetically
D. Increasing deadline

6 In job selection problems, greedy techniques help decide which jobs to pick in order to:

Job Selection problem Easy
A. Guarantee all jobs are always selected
B. Optimize an objective such as maximum profit or count
C. Sort the jobs by their identifiers
D. Minimize the memory used by the program

7 For the array , what is the minimum product subset value?

Minimum product subset of an array Easy
A.
B.
C.
D.

8 To get a negative minimum product from an array, the subset should include:

Minimum product subset of an array Easy
A. An even number of negative elements
B. Exactly one zero element
C. Only positive elements
D. An odd number of negative elements

9 For the array , what is the maximum product subset value?

Maximum product subset of an array Easy
A.
B.
C.
D.

10 To minimize the sum of products of two arrays (one element from each), you should:

Minimum sum of product of two arrays Easy
A. Sort both arrays in ascending order
B. Leave both arrays in their original order
C. Sort both arrays in descending order
D. Sort one array ascending and the other descending

11 The Bin Packing problem aims to:

Bin packing problem Easy
A. Maximize the number of bins used
B. Fill a single bin with the most valuable items
C. Sort bins by their capacity
D. Pack items into the minimum number of fixed-capacity bins

12 Which of the following is a common greedy heuristic for the Bin Packing problem?

Bin packing problem Easy
A. First Fit
B. Binary Search
C. Depth First Search
D. Merge Sort

13 In the Activity Selection problem, activities are greedily selected by sorting them according to their:

Activity Selection problem Easy
A. Earliest finish time
B. Longest duration
C. Earliest start time
D. Latest finish time

14 The objective of the Activity Selection problem is to:

Activity Selection problem Easy
A. Select every available activity
B. Select the maximum number of non-overlapping activities
C. Minimize the total time of all activities
D. Select the activity with the longest duration

15 In the Fractional Knapsack problem, items are chosen greedily based on their:

Fractional Knapsack problem Easy
A. Weight only
B. Value-to-weight ratio
C. Alphabetical order
D. Value only

16 Which key feature distinguishes the Fractional Knapsack from the 0/1 Knapsack problem?

Fractional Knapsack problem Easy
A. The knapsack has no capacity limit
B. Only one item can be selected
C. Items must be taken whole
D. Items can be broken into fractions

17 In the "Connect n ropes with minimum cost" problem, which data structure is most suitable?

Connect n ropes with minimum cost Easy
A. Hash table
B. Max-heap only
C. Stack
D. Min-heap (priority queue)

18 Given ropes of lengths , what is the minimum total cost to connect them all?

Connect n ropes with minimum cost Easy
A.
B.
C.
D.

19 The greedy approach to the Coin Change problem selects coins by:

Coin change problem Easy
A. Trying every possible combination
B. Choosing coins in random order
C. Choosing the largest denomination that does not exceed the remaining amount
D. Choosing the smallest denomination first

20 A majority element in an array of size is an element that appears more than:

Majority Element Easy
A. times
B. times
C. times
D. times

21 In a greedy algorithm, a solution is built incrementally. Which property is essential for a greedy algorithm to always produce a globally optimal solution?

Greedy problem solving paradigm Medium
A. Overlapping subproblems and memoization
B. Greedy choice property and optimal substructure
C. Divide and conquer decomposition
D. Backtracking with pruning

22 A greedy algorithm makes a locally optimal choice at each step. What is the main risk of relying only on local optimality?

Locally optimal choice Medium
A. It requires exponential memory
B. It may fail to reach the global optimum for some problems
C. It cannot be implemented iteratively
D. It always increases time complexity

23 For which of the following problems does the greedy approach guarantee a globally optimal solution?

Global optimal choice Medium
A. Longest common subsequence
B. 0/1 Knapsack problem
C. Traveling salesman problem
D. Fractional Knapsack problem

24 In the Job Sequencing with Deadlines problem, jobs are first sorted by which criterion to maximize total profit?

Job Sequencing problem Medium
A. Decreasing order of profit
B. Decreasing order of deadline
C. Increasing order of profit
D. Increasing order of deadline

25 Given jobs with (profit, deadline): , , , , . What is the maximum profit achievable if each job takes one unit of time?

Job Sequencing problem Medium
A. 142
B. 100
C. 127
D. 115

26 When selecting the maximum number of non-overlapping jobs (each with a start and finish time), the greedy strategy selects jobs based on:

Job Selection problem Medium
A. Shortest duration
B. Earliest finish time
C. Longest duration
D. Earliest start time

27 For the array , what is the minimum product of a non-empty subset?

Minimum product subset of an array Medium
A. 24
B. -8
C. -24
D. -12

28 If an array contains a zero, some negatives, and some positives, when is the minimum product subset equal to a negative value rather than zero?

Minimum product subset of an array Medium
A. Only when the count of negatives is even
B. When at least one negative number exists in the array
C. Only when no positives are present
D. When at least two negatives exist

29 For the array , what is the maximum product of a non-empty subset?

Maximum product subset of an array Medium
A. 48
B. -24
C. 24
D. 12

30 To compute the maximum product subset, if the array has an odd number of negative numbers, the greedy rule is to:

Maximum product subset of an array Medium
A. Include all negatives
B. Exclude the negative number with the smallest absolute value
C. Exclude the negative number with the largest absolute value
D. Exclude all negatives

31 Given arrays and , the minimum sum of element-wise products (with one permutation allowed) is obtained by pairing:

Minimum sum of product of two arrays Medium
A. Sorting both in the same order
B. Largest of A with largest of B
C. Largest of A with smallest of B
D. Pairing equal-index elements as given

32 The rearrangement inequality states that the sum is minimized when the two sequences are:

Minimum sum of product of two arrays Medium
A. Sorted in opposite orders
B. Both kept unsorted
C. Both randomly shuffled
D. Sorted in the same order

33 In the First Fit Decreasing (FFD) heuristic for bin packing, items are processed in what order?

Bin packing problem Medium
A. Decreasing order of size
B. Increasing order of size
C. Random order
D. Order of arrival

34 The bin packing problem (minimizing number of bins) is known to be:

Bin packing problem Medium
A. Solvable optimally in by greedy
B. Solvable optimally by a simple greedy algorithm
C. Solvable in linear time
D. NP-hard, solved approximately by greedy heuristics

35 Given activities with (start, finish): , how many activities can be selected using the greedy earliest-finish-time rule?

Activity Selection problem Medium
A. 5
B. 3
C. 2
D. 4

36 In the Fractional Knapsack problem with capacity , items (value, weight) are . What is the maximum value obtainable?

Fractional Knapsack problem Medium
A. 220
B. 160
C. 240
D. 180

37 For ropes of lengths , what is the minimum total cost to connect them all into one rope?

Connect n ropes with minimum cost Medium
A. 33
B. 27
C. 30
D. 29

38 Which data structure gives the most efficient implementation for the 'connect n ropes with minimum cost' problem?

Connect n ropes with minimum cost Medium
A. Hash table
B. Stack
C. Max-heap
D. Min-heap (priority queue)

39 The greedy coin change algorithm (always picking the largest denomination) fails to give the minimum number of coins for which coin system when making amount 6?

Coin change problem Medium
A. Coins
B. Coins
C. Coins
D. Coins

40 The Boyer-Moore Voting Algorithm finds a majority element (appearing more than times) in:

Majority Element Medium
A. time and space
B. time and space
C. time and space
D. time and space

41 A greedy algorithm is guaranteed to produce a globally optimal solution only when the problem exhibits which two properties?

Greedy problem solving paradigm Hard
A. Optimal substructure and overlapping subproblems
B. Greedy-choice property and optimal substructure
C. Greedy-choice property and overlapping subproblems
D. Overlapping subproblems and memoization

42 Consider making change for using coins . What is the difference between the number of coins the greedy (largest-first) approach uses versus the true optimal?

Locally optimal choice Hard
A. Greedy uses , optimal uses ; difference
B. Greedy uses , optimal uses ; difference
C. Greedy uses , optimal uses ; difference
D. Greedy uses , optimal uses ; difference

43 In Job Sequencing with deadlines (each job takes unit time), jobs are : . What is the maximum total profit?

Job Sequencing problem Hard
A.
B.
C.
D.

44 When scheduling to maximize the number of non-overlapping jobs, which greedy criterion guarantees optimality?

Job Selection problem Hard
A. Select the job with the earliest finish time first
B. Select the job with the earliest start time first
C. Select the job with the highest profit first
D. Select the job with the shortest duration first

45 For the array , what is the minimum product of a non-empty subset?

Minimum product subset of an array Hard
A.
B.
C.
D.

46 For the array , what is the maximum product of a non-empty subset?

Maximum product subset of an array Hard
A.
B.
C.
D.

47 Given and , arranging freely (only reorder within each array), the minimum value of is:

Minimum sum of product of two arrays Hard
A.
B.
C.
D.

48 Which statement about the First-Fit Decreasing (FFD) heuristic for bin packing is correct?

Bin packing problem Hard
A. FFD always finds the optimal number of bins
B. FFD runs in time without sorting
C. FFD uses at most bins
D. FFD uses at most bins and no better bound exists

49 Activities with : . Using the earliest-finish-time greedy, how many activities can be selected?

Activity Selection problem Hard
A.
B.
C.
D.

50 Items : with capacity . What is the maximum value obtainable in the fractional knapsack?

Fractional Knapsack problem Hard
A.
B.
C.
D.

51 For ropes of lengths , the minimum total cost to connect them all into one rope is:

Connect n ropes with minimum cost Hard
A.
B.
C.
D.

52 For which of the following coin systems is the greedy (largest-coin-first) algorithm guaranteed to be optimal for every amount?

Coin change problem Hard
A.
B.
C.
D.

53 In the Boyer-Moore Voting Algorithm, after the first pass finds a candidate, why is a second pass usually required?

Majority Element Hard
A. The algorithm only guarantees a candidate if a majority exists; a second pass verifies it truly appears times
B. The first pass sorts the array, so verification confirms the sort order
C. The second pass is needed to compute the exact index of the majority element
D. The candidate from pass one is always wrong and must be corrected

54 You want to form the largest possible number by concatenating integers from . Which comparator correctly orders two strings ?

Problems based on greedy techniques Hard
A. Place before if (string concatenation comparison)
B. Place before if
C. Place before if
D. Place before if numerically

55 Why does the greedy approach fail for the 0/1 Knapsack but succeed for the Fractional Knapsack?

Fractional Knapsack problem Hard
A. 0/1 knapsack lacks optimal substructure entirely
B. In 0/1, values are always negative, making greedy invalid
C. In fractional, items can be split so the ratio bound is always fully saturated; in 0/1, indivisibility can leave unusable residual capacity
D. Fractional knapsack has no weight constraint, so greedy trivially works

56 Using a Disjoint-Set (Union-Find) optimization for job sequencing with maximum deadline , the time complexity to schedule jobs becomes approximately:

Job Sequencing problem Hard
A.
B.
C.
D.

57 For an array containing exactly one zero, some positive numbers, and an even number of negatives (all nonzero), the minimum product subset equals:

Minimum product subset of an array Hard
A. The product of all negative elements
B. The product of the two smallest elements
C. The product of all elements including zero, i.e.,
D. The single smallest (most negative) negative element

58 Suppose each activity also carries a weight and we want the maximum-weight set of non-overlapping activities. Which approach is correct?

Activity Selection problem Hard
A. Dynamic programming with binary search, since the earliest-finish greedy no longer guarantees maximum weight
B. Sort by weight descending and greedily pick compatible activities
C. Sort by start time and pick greedily
D. The same earliest-finish-time greedy still gives the optimal weight

59 Which of the following classic problems does NOT admit a correct greedy solution guaranteeing a global optimum?

Global optimal choice Hard
A. Huffman coding
B. 0/1 Knapsack problem
C. Fractional Knapsack problem
D. Minimum Spanning Tree (Kruskal's)

60 If we instead wanted to MAXIMIZE the total cost of connecting ropes , which strategy and cost is correct?

Connect n ropes with minimum cost Hard
A. Order does not affect total cost
B. Use a min-heap as usual; total
C. Use a max-heap; total
D. Use a max-heap, always combining the two largest; total
Previous MCQ
Unit 3
Next MCQ
Unit 5