Font size
WorksheetsQuiz3_DivideConquer_GreedyApproach
Total questions: 10
Worksheet time: 11mins
Divide and conquer involves 3 major steps: (type in the format: A, B, C)
(a)
By using divide and conquer approach in the algorithm, it means that sub-problems are solved:
recursively
repeatedly
greedily
dynamically
Why do we need a base case in divide and conquer approach?
Base case represents no more breaking of problem into subsequence recursive call and return a constant value.
Base case means that it is to round the value of recursive function.
Base case means that the iteration of loop by calling itself.
Base case represents that a constant value is called recursively.
The algorithms that apply divide and conquer includes: (select all that apply)
Merge sort
Quick sort
Binary search tree
Closest pair of point
Given the array. Assume that merge sort is used. What is the first index of the partition function given that the index = (p+r)/2?
index = 4
index = 5
index = 6
index = 12
T(n) of merge sort is 2(T(n/2)+ n instead of T(n/2)+n. Is the statement true? Justify.
True. The array is breaking into left half and right half, so it is 2T(n/2) and the constant n is for merging.
False. The array is breaking into half with T(n/2).
True. The array is breaking into half with T(n/2), merge with another T(n/2) and sort with n comparison.
True. The array is dividing into half with T(n/2) and make comparison with another T(n/2) and then sorting with n.
Given this: T(n) = 8 T(n/2)+100(n^2). What is f(n)?
4
n^2
100n^2
8
Find the path to reach the destination from starting location with greedy method. Assume that the algorithm always select the most minimum path.
A-B-C-D
A-H-G-D
A-H-D
A-E-F-G-D
What is the first added path if Kruskal algorithm is applied?
A-H
A-B
A-E
H-G
Given the knapsack problem. Greedy approach is used to maximize the value. What is/are the selected items?
Item 1 & Item 3
Item 2(1 lb); item 4 (2 lb); item 3 (2/3 lb)
Item 3 & item 4
Item 2 (1 lb); item 4(1 lb); item 3
