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
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,
b) ternary decision tree, c) four-way decision tree.
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?
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 ?
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.
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.
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.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com