Theoretical Computer Science (M21276)
Part B/5: Introduction to Computational Complexity
(Jan 4-10, 2021)
Question 1. Simulate the sequential and binary search algorithm for the following array L of integers
Copyright By PowCoder代写 加微信 powcoder
10, 16, 19, 24, 28, 30, 33, 38, 49, 58, 66, 69, 76, 85, 96, 100 and keys (i) x = 10, (ii) x = 38.
How many basic steps (loops) have to be executed in each case?
Give an example of a key for which both algorithms have to do the most steps
(loops) for L. If such a key doesn’t exist give a reason.
Question 2. Consider two possible algorithms to solve a problem, A and B. The time time complexity of the first algorithm is TA(n) = An3 , where n is the size of the input and for the second one TB(n) = Bn2. After programming these, you run it for a small subset (n = 100) and discover that they take TA(100) = 0.1 seconds and TB(100) = 2 seconds. How long does each take for n = 10,000? For what values of n does it make sense to use the algorithm A ?
Answer: Begin by solving for the constants A and B. TA(100) = A×1003 = 0.1 seconds. Thus, A = 10−7 seconds. Similarly, we can show that B = 2 × 10−4 seconds. Next, evaluate the functions for n = 10, 000 = 104 :
TA(104) = A × (104)3 = 10−7 seconds × 1012 = 105 seconds TB(104)=B×(104)2 =2×10−4 seconds×108 =2×104 seconds
Thus, method B is five times faster than A when n = 10,000. Method A is better at small n, while B is better at large n. The cross over point is where TA(n) = TB(n). This is when, An3 = Bn2. Solving this, we find that
n= A = 10−7 seconds=2×103 =2000.
For n < 2000, algorithm A is faster, while for n > 2000, B is faster. Question 3. Given the following algorithm:
while i <= n
i := i + 1; x := x + 1; S;
(a) Find the number of times that the statement S is executed during the running of the program for n = 4, as a function of n.
Answer: n-times
(b) Find the number of times that the assignment statement (:=) is executed during
the running of the program for n = 4, as a function of n. Answer: 2 + 2n
Question 4. Given the following algorithm:
while i < (n + 1)
i := i + 1;
for j := 1 to i do S od od
(a) Find the number of times that the statement S is executed during the running of the program for n = 4, as a function of n.
Answer: 2+3+···+(n+1)= (n+1)(n+2) −1 2
(b) Find the number of times that the assignment statement (:=) is executed during the running of the program for n = 4, as a function of n (including assignments := as part of for statement itself).
Answer: 1+2+3+···+(n+1)+n= (n+1)(n+2) +n 2
Question 5. Given the following algorithm:
for i := 1 to n do
for j := 1 to i do x := x + f(x) od; x := x + g(x)
(a) Find the number of times that the addition operation (+) is executed during the running of the program for n = 4, as a function of n.
(b) Find the number of times that the assignment statement (:=) is executed during the running of the program for n = 4, as a function of n (including assignments := as part of for statement itself).
Answer: ni=1(2+2i)=2n+n2 +n=n2 +3n
Question 6. Given the following algorithm:
while j <= n/2
while i <= j
print j, i; i := i + 1; S;
j := j + 1; od
(a) What is the output when n = 8?
(b) Find the number of times that the statement S is executed during the running of
the program as a function of n.
Answer: (a)11212231323341424344(b)T(n)=n2 +n
Question 7. Given the following algorithm:
while x <= y
x := x + 2; y := y/2; S;
Find the number of times that the statement S is executed during the running of the program.
Answer: 4-times
Question 8. Suppose you have an old computer that requires 1 minute to solve a problem P using your algorithm A for instances of size n = 10 000. Suppose you buy a new computer that runs 100 times faster than the old one (hence the new computer runs 100 times more operations for the same input). What size of input can be run in 1 minute on the new computer, assuming the following time complexities T(n) for the algorithm A?
(a) T(n)=n, (b) T(n)=n2,
(c) T(n) = 10n.
Answer: Count the number of operation in each case, then multiply by 100 and figure
out n. (i) 106 (ii) 105 (iii) 10 002
Question 9. Fill in the following table for different time-complexity functions. For large
values use only approximative values in the terms of powers of 10, e.g. 109, ...
n logn n2 2n n!
Consider a problem with exponential/factorial complexity and assume 1 computation per 10−12 seconds.
Computing continuously from 0 A.D. until now, for which n we would still not have solved the problem in exponential/factorial case?
n log2 n n2 2n n!
5 2 10 3 20 4 30 4 40 5 50 5
100 6 200 7
100 400 900 1,600 2,500 10,000 40,000
1,048,576 1018
3,628,800 109 1032
1012 1048 1015 1064
1030 10161 1060 10374
#of operations = 2019 × 365.247 × 24 × 3600 × 1012 ≈ 6.4 × 1022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com