Back to Subject

Unit 3: Greedy Method - Practice Quiz

ECAP538 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 What does a greedy algorithm choose at each step?

General method Easy
A. The globally worst available choice
B. The locally best available choice
C. A randomly selected available choice
D. Every available choice simultaneously

2 Which property means that a globally optimal solution can be reached through locally optimal choices?

General method Easy
A. Greedy-choice property
B. Loop-invariant property
C. Backtracking-choice property
D. Divide-and-conquer property

3 How does a typical greedy algorithm treat a choice after making it?

General method Easy
A. It keeps the choice unchanged
B. It examines every alternative later
C. It replaces the choice randomly
D. It postpones the choice indefinitely

4 Which statement about greedy algorithms is correct?

General method Easy
A. They work only on sorted arrays
B. They always examine every solution
C. They require suitable problem properties
D. They are optimal for every problem

5 In the fractional knapsack problem, which quantity is commonly used to order items?

Knapsack problem Easy
A. Value-to-weight ratio
B. Original item position
C. Total item weight
D. Weight-to-value ratio

6 What is allowed in the fractional knapsack problem?

Knapsack problem Easy
A. Taking part of an item
B. Changing an item's value
C. Exceeding the knapsack capacity
D. Adding unlimited item copies

7 What distinguishes the 0/1 knapsack problem from the fractional knapsack problem?

Knapsack problem Easy
A. Values must be equal
B. Items have no weights
C. Capacity has no limit
D. Items cannot be divided

8 An item has value and weight . What is its value-to-weight ratio?

Knapsack problem Easy
A.
B.
C.
D.

9 How does Prim's algorithm construct a minimum spanning tree?

Minimal spanning trees: Prim's algorithm Easy
A. By visiting vertices in alphabetical order
B. By removing every edge from the graph
C. By growing separate trees from every edge
D. By growing one tree from a starting vertex

10 Which edge does Prim's algorithm select next?

Minimal spanning trees: Prim's algorithm Easy
A. The lightest edge joining two vertices outside the tree
B. The heaviest edge joining two vertices inside the tree
C. The lightest edge joining the tree to an outside vertex
D. The first edge listed in the graph representation

11 Prim's algorithm is primarily used to find which structure?

Minimal spanning trees: Prim's algorithm Easy
A. A topological ordering
B. A maximum-flow network
C. A strongly connected component
D. A minimum spanning tree

12 For which type of graph is a spanning tree normally defined?

Minimal spanning trees: Prim's algorithm Easy
A. A graph without vertices
B. A directed acyclic graph
C. A connected undirected graph
D. A disconnected directed graph

13 What is the first major step in Kruskal's algorithm?

Minimal spanning trees: Kruskal's algorithm Easy
A. Sort edges by increasing weight
B. Choose a starting source vertex
C. Remove all minimum-weight edges
D. Sort vertices by decreasing degree

14 When does Kruskal's algorithm reject an edge?

Minimal spanning trees: Kruskal's algorithm Easy
A. When it touches an unvisited vertex
B. When it has the smallest weight
C. When it would create a cycle
D. When it joins different components

15 Which data structure is commonly used to detect cycles in Kruskal's algorithm?

Minimal spanning trees: Kruskal's algorithm Easy
A. Priority stack structure
B. Hash table structure
C. Circular queue structure
D. Disjoint-set structure

16 What does Kruskal's algorithm maintain before the minimum spanning tree is complete?

Minimal spanning trees: Kruskal's algorithm Easy
A. A single directed cycle
B. A table of vertex colors
C. A forest of separate trees
D. A list of source distances

17 What does the single-source shortest-path problem compute?

Single-source shortest paths Easy
A. Minimum spanning trees from every source vertex
B. Shortest paths between every pair of vertices
C. Longest paths from all vertices to one source
D. Shortest paths from one source to all vertices

18 Which condition is required by the standard Dijkstra's algorithm?

Single-source shortest paths Easy
A. All edge weights are nonnegative
B. All vertices have even degree
C. All paths contain one edge
D. All edge weights are identical

19 What is the initial shortest-path distance from the source vertex to itself?

Single-source shortest paths Easy
A.
B.
C.
D.

20 Which algorithm can handle negative edge weights when no reachable negative cycle exists?

Single-source shortest paths Easy
A. Bellman-Ford algorithm
B. Kruskal's algorithm
C. Prim's algorithm
D. Dijkstra's algorithm

21 Which two properties are typically required to prove that a greedy algorithm produces an optimal solution?

General method Medium
A. Divide-and-conquer structure and memoization
B. Greedy-choice property and optimal substructure
C. Greedy-choice property and exhaustive search
D. Overlapping subproblems and optimal substructure

22 A greedy coin-change algorithm repeatedly selects the largest coin not exceeding the remaining amount. For denominations and amount , what does the algorithm produce?

General method Medium
A. It examines every possible combination before selecting the minimum number of coins
B. Three coins:
C. Two coins:
D. Three coins:

23 In the activity-selection problem, activities are sorted by finishing time. Which next activity should be selected after choosing an activity that finishes at time ?

General method Medium
A. The activity with the shortest total duration
B. The compatible activity with the latest start time
C. The compatible activity with the earliest finish time
D. The activity overlapping the fewest remaining activities

24 Consider activities , , , , , and . How many activities are selected by the earliest-finish-time greedy method?

General method Medium
A. activities
B. activities
C. activities
D. activities

25 A fractional knapsack has capacity . Items have values , , and . What maximum profit is obtained?

Knapsack problem Medium
A.
B.
C.
D.

26 For the fractional knapsack problem, which quantity should be used to order items greedily?

Knapsack problem Medium
A. Increasing item weight
B. Increasing remaining capacity
C. Decreasing profit-to-weight ratio
D. Decreasing item profit

27 A fractional knapsack has capacity and items , , and . What maximum profit can be obtained?

Knapsack problem Medium
A. All three items are selected completely because their combined profit is greater than the capacity
B.
C.
D.

28 For a knapsack of capacity , items have values , , and . Why does the profit-to-weight greedy rule fail?

Knapsack problem Medium
A. It obtains , while the optimum is
B. It obtains , while the optimum is
C. It obtains , while the optimum is
D. It obtains , while the optimum is

29 An undirected graph has edges , , , , and . Starting Prim's algorithm at , what is the total weight of the resulting MST?

Minimal spanning trees: Prim's algorithm Medium
A.
B.
C.
D.

30 Suppose Prim's algorithm has already included vertices . Which edge is eligible to be selected next?

Minimal spanning trees: Prim's algorithm Medium
A. The lightest edge having both endpoints inside the tree
B. The globally lightest edge even if it creates a cycle
C. The lightest edge joining the tree to an excluded vertex
D. The edge that reaches the excluded vertex having the largest number of incident edges

31 If a connected weighted graph has several equal-weight edges, what can happen when Prim's algorithm resolves ties differently?

Minimal spanning trees: Prim's algorithm Medium
A. It must stop before including every vertex
B. It must produce trees with different total weights
C. It may produce different MSTs with the same total weight
D. It may produce a spanning tree containing a cycle

32 Using adjacency lists and a binary min-heap, what is the typical time complexity of Prim's algorithm on a connected graph?

Minimal spanning trees: Prim's algorithm Medium
A.
B.
C.
D.

33 An undirected graph has edges , , , , , and . What is the MST weight produced by Kruskal's algorithm?

Minimal spanning trees: Kruskal's algorithm Medium
A.
B.
C.
D.

34 Why does Kruskal's algorithm skip an edge whose endpoints are already in the same disjoint-set component?

Minimal spanning trees: Kruskal's algorithm Medium
A. The edge would form a cycle
B. The edge is compared with every previously rejected edge before being permanently removed
C. The edge must have negative weight
D. The edge cannot connect two vertices

35 Which data structure most efficiently supports cycle detection in Kruskal's algorithm?

Minimal spanning trees: Kruskal's algorithm Medium
A. Binary search tree
B. Disjoint-set union
C. FIFO queue
D. Adjacency matrix

36 What does Kruskal's algorithm produce when it is applied to a disconnected undirected graph?

Minimal spanning trees: Kruskal's algorithm Medium
A. A maximum-weight connected graph
B. A shortest-path tree
C. A single minimum spanning tree
D. A minimum spanning forest

37 A directed graph has edges , , , , and . What shortest distance from to does Dijkstra's algorithm find?

Single-source shortest paths Medium
A.
B.
C.
D.

38 During edge relaxation, , edge weight , and the current . What is the updated value of ?

Single-source shortest paths Medium
A. It remains because relaxation updates only vertices that have already been permanently settled
B.
C.
D.

39 Why can standard Dijkstra's algorithm give an incorrect result on a graph containing a reachable negative-weight edge?

Single-source shortest paths Medium
A. Every vertex must have the same out-degree
B. A settled distance may later be reduced
C. Negative edges always create directed cycles
D. The source distance becomes negative immediately

40 A graph has edges , , , , and . In what order are vertices settled by Dijkstra's algorithm?

Single-source shortest paths Medium
A.
B.
C.
D.

41 Let be a finite independence system. A greedy algorithm processes elements in nonincreasing order of nonnegative weight and adds an element whenever feasibility is preserved. Under which condition is this algorithm guaranteed to return a maximum-weight feasible set for every weight assignment?

General method Hard
A. The feasible sets form a matroid.
B. Every maximal feasible set is unique.
C. The feasible sets form a greedoid.
D. Every element belongs to a feasible pair.

42 In an exchange-argument proof, a greedy algorithm first chooses . Which statement most directly establishes that this first choice is safe?

General method Hard
A. Every optimal solution initially contains as its first selected element.
B. The choice has greater value than the entire remaining solution.
C. Removing makes every remaining feasible solution uniquely determined.
D. Some optimal solution can be modified to contain without losing value.

43 For coin denominations and target value , what does the largest-denomination-first greedy rule demonstrate?

General method Hard
A. It uses six unit coins because divisibility is not preserved.
B. It uses , so negative coins are implicitly required.
C. It uses , although uses fewer coins.
D. It uses , which is the unique optimal representation.

44 Five unit-time jobs have values , , , , and . Using the greedy rule that processes jobs by decreasing profit and places each job in its latest available slot, which schedule is produced?

General method Hard
A. Slots with profit .
B. Slots with profit .
C. Slots with profit .
D. Slots with profit .

45 A fractional knapsack of capacity has items , , , and , where each pair is . What solution is obtained by density-ordered greedy selection?

Knapsack problem Hard
A. Take , , and of for value .
B. Take , , and of for value .
C. Take , , and of for value .
D. Take , , and of for value .

46 A knapsack has capacity and items , , and . What is the outcome of selecting items by decreasing value-to-weight ratio?

Knapsack problem Hard
A. Greedy selects only for , but gives .
B. Greedy selects for , which is globally optimal.
C. Greedy selects for , but gives .
D. Greedy selects for , but gives .

47 Assume all weights are positive and values are nonnegative. Why can an optimal basic solution of the fractional knapsack contain at most one partially selected item?

Knapsack problem Hard
A. The capacity constraint forces all selected fractions to have equal denominators.
B. Any pair of partial items can always be replaced by one indivisible item.
C. Two partial items can be shifted toward the higher-density item without reducing value.
D. Every partial item must have a density strictly greater than every full item.

48 A fractional knapsack uses the constraint that total weight is at most . Its items are , , and . What is the optimal value?

Knapsack problem Hard
A. , by taking only because it has the greatest weight.
B. , by taking all three items and filling the knapsack.
C. , by taking and while leaving capacity unused.
D. , by taking and using the remaining capacity on .

49 An undirected graph has edges , , , , , , and . Starting Prim's algorithm at , which edges are selected in order?

Minimal spanning trees: Prim's algorithm Hard
A. , with total weight .
B. , with total weight .
C. , with total weight .
D. , with total weight .

50 A connected undirected graph contains negative edge weights but no other unusual constraints. Which statement about Prim's algorithm is correct?

Minimal spanning trees: Prim's algorithm Hard
A. It remains correct only after the same constant is added to every edge.
B. It fails unless all negative edges are selected before choosing a start vertex.
C. It remains correct because the cut property does not require nonnegative weights.
D. It fails because selecting a negative edge can later create a negative cycle.

51 What happens if standard Prim's algorithm is started in a graph that has multiple connected components?

Minimal spanning trees: Prim's algorithm Hard
A. One run automatically joins all components using implicit zero-weight edges.
B. One run spans only the start component; restarting produces a minimum spanning forest.
C. The algorithm necessarily reports a cycle when its priority queue becomes empty.
D. One run spans every component but omits one edge from each component.

52 All edge weights in a connected undirected graph are distinct. How can Prim's output depend on its starting vertex?

Minimal spanning trees: Prim's algorithm Hard
A. Only the lexicographically smallest start vertex produces the unique MST.
B. The selection order may differ, but every start produces the same unique MST.
C. The final tree may differ, although every produced tree has the same weight.
D. The start vertex determines both the final weight and the number of edges.

53 An undirected graph has edges , , , , , , and . Which edge set does Kruskal's algorithm select?

Minimal spanning trees: Kruskal's algorithm Hard
A. , with total weight .
B. , with total weight .
C. , with total weight .
D. , with total weight .

54 Edge is the unique heaviest edge on some cycle of a connected undirected graph. What can Kruskal's cycle property conclude?

Minimal spanning trees: Kruskal's algorithm Hard
A. Edge must be selected before the other cycle edges.
B. Edge belongs to every minimum spanning tree.
C. Edge is excluded only when all weights are distinct.
D. Edge belongs to no minimum spanning tree.

55 Using comparison sorting and disjoint sets with union by rank and path compression, what is Kruskal's running time on a graph with vertices and edges?

Minimal spanning trees: Kruskal's algorithm Hard
A. , dominated by edge sorting.
B. , dominated by vertex sorting.
C. , dominated by cycle detection.
D. , dominated by repeated component scans.

56 A graph has MST edges , , and non-tree edges , , . What is the weight of the minimum spanning tree whose weight is strictly greater than the MST weight?

Minimal spanning trees: Kruskal's algorithm Hard
A. , obtained only by replacing edge with edge .
B. , obtained by an exchange involving or .
C. , obtained by replacing edge with edge .
D. , obtained by selecting both and .

57 A directed graph has edges , , , , , , and . What settled-vertex order and final distances does Dijkstra's algorithm produce?

Single-source shortest paths Hard
A. Order ; distances for .
B. Order ; distances for .
C. Order ; distances for .
D. Order ; distances for .

58 Consider edges , , and . Why can standard Dijkstra's algorithm, which never revisits settled vertices, fail?

Single-source shortest paths Hard
A. It cannot initialize tentative distances when one edge is negative.
B. It settles at before discovering the true distance through .
C. It settles at before discovering the true distance through .
D. It creates a negative cycle containing , , and .

59 Which edge-weight condition is sufficient for the standard correctness proof of Dijkstra's single-source shortest-path algorithm?

Single-source shortest paths Hard
A. Every edge leaving the source has a strictly positive weight.
B. Every simple path has positive total weight, despite negative edges.
C. Every directed cycle has nonnegative total weight, despite negative edges.
D. Every edge weight is nonnegative, including the possibility of zero.

60 For a dense graph with and nonnegative edge weights, which implementation gives the better asymptotic bound for Dijkstra's algorithm?

Single-source shortest paths Hard
A. A sorted edge array with disjoint sets, taking .
B. A binary heap with adjacency lists, taking .
C. An adjacency matrix with linear minimum selection, taking .
D. A breadth-first queue with adjacency lists, taking .
Previous MCQ
Unit 2
Next MCQ
Unit 4