Theoretical Computer Science (M21276)
Part B/8: Problem complexity and Classification of problems
(Jan 10-14, 2022)
Question 1. Draw a picture of the decision tree for an optimal algorithm to find the maximum number in the list ⟨x1, x2, x3, x4⟩.
Copyright By PowCoder代写 加微信 powcoder
Answer: Clearly, 3 decisions are enough.
Question 2. Suppose there are 95 possible answers to some problem. For each of the following types of decision tree, find a reasonable lower bound for the number of decisions necessary to solve the problem:
a) binary decision tree,
Answer: Minimum number of decisions is 7 (27 = 128 > 95). b) ternary decision tree,
Answer: Minimum number of decisions is 5 (35 = 243 > 95). c) four-way decision tree.
Answer: Minimum number of decisions is 4 (44 = 256 > 95).
Question 3. The time complexity function T(n) is given by the recurrence relation T(n) = T(n − 1) + 3 and T(1) = 2. Can you express the function T(n) without the recurrence?
Answer: T(n) = T(n−1)+3 = T(n−2)+3+3 = T(n−3)+3+3+3 = ··· = T (n − (n − 1)) + 3(n − 1) = T (1) + 3(n − 1) = 2 + 3(n − 1)
Question 4. Look at the following problem:
Problem: Find the smallest and largest keys in an arrays S of size n.
Input: positive integer n, array of keys S indexed from 1 to n
Output: variable small/large, whose values are the smallest and largest keys in S
Can you suggest an algorithm to solve the problem? How many comparisons does the algorithm make ?
Answer: Easy to write the algorithm with 2(n − 1) comparisons, just run through array
and compare the current value with temporary small/large value. But can be done by
(3n − 3) if n is odd, resp. (3n −2) if n is even. The trick is to pair the keys (consecutive) 222
and find which key in each pair is smaller. This can be done with about n/2 comparisons and the largest of all the larger keys with about n/2 comparisons. In this way, we find both the smallest and the largest keys with only about 3n/2 total comparisons.
Question 5. Give an algorithm for the following problem and determine its time com- plexity. Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is maximized. You may assume that n is a multiple of 2.
Answer: The first list should have the larger half of the elements, and the second list should have the smaller half, so we have to find the median. The easiest way to do it is to sort the list, which is Θ(n log n) The median can, however, be found very efficiently with the “Median of Medians” algorithm, whose complexity is only Θ(n), after which the list can be partitioned using the median as a pivot in another Θ(n) operations, which makes the entire algorithm Θ(n).
Question 6. Give an algorithm for the following problem. Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that n is a multiple of 2.
Answer: Let the set of all list nodes be denoted by A. The algorithm needs a temporary set of n2 elements, TempSet.
int min diff = LARGE NUMBER; int diff;
for (each subset S of size n2 of A) { diff = abs(sum(S) − sum(A-S)); if (diff < min diff) {
min diff = diff;
TempSet = S;
print min diff, TempSet;
Each iteration of the for loop has a constant worst-case cost (one comparison, an integer assignment, a set assignment), and the loop executes n-choose-n/2 times, so the algorithm
isinΘ n! . (n/2)!2
Question 7. Give an example of a problem that is: (a) undecidable,
(b) apparently intractable,
(c) tractable,
(e) in NP.
(f) a proven intractable.
In each case clearly formulate your problem. Give a reason why your problem is tractable or why it is in P.
Answer: Various problems can be listed in each case. (a) Halting problem, (unbounded) Tilling problem, (b) Travelling Salesman Problem, (bounded) Tilling Problem, (c) sorting problem – known O(n log n) algorithm, (d) searching problem (in unsorted array) – known O(n) (e) a decision version of TSP (f) Tower of Hanoi
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com