I have attached it's about theory of computation

CS 323/700    Fall 2016  Homework Assignment #1  Due: in class on 09/22/16, Thursday

Only hard copies will be accepted. Late submissions and email submissions will not be accepted. If you have not been able to solve a problem completely, you may show the work you have done for partial points. Observe  course policies  in solving assignment problems.

1. Presume that the algorithm takes f(n) microseconds to solve inputs of size n. For each function f(n) and time span in the following table, determine an approximate maximum input size that can be solved in the given time span. 

f(n)	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
lg n
(lg n)100
n2lg n
n4
3n

2.

3. Order the following functions by their asymptotic growth rate. Write "f(n) < g(n)" if f(n) = o(g(n)) and "f(n) = g(n)" if f(n) = Θ(g(n)). Justify your answer; you may use any of the facts/theorems given in class or the textbook.  22n,   log3 n,   22n,   n,   nlg n,   n2.5,   lg(n1/2),   2lg n,   n100,   3n,   n0.1 

4. Show that for all real numbers a, b > 1, alogb n = Θ(nlogb a). You may use any of the facts/theorems given in class or the textbook. 

5. Using the Master Theorem, determine the asymptotic class of each of the following recurrences. Justify your answers. 

i. T(n) = 3T(n/3) + 2n

ii. T(n) = 3T(n/3) + log3 n

iii. T(n) = 2T(n/3) + 2n

6. Consider the recurrence in Q4 (i). Determine the asymptotic class of T(n) by the substitution method (i.e. expansion method) described in class. 

7. Using Figure 7.1 (page 172) as a model, illustrate the step-by-step operation of the Partition function on each of the following arrays: 

i. 3, 7, 5, 1, 8, 2, 4, 6

ii. 1, 2, 3, 4, 5, 6, 7, 8

iii. 8, 7, 6, 5, 4, 3, 2, 1

8. This is a mandatory question for CS 700 students, and is an optional, bonus question for CS 323 students.  Consider the recurrence in Q4 (iii). Determine the asymptotic class of T(n) by the substitution method (i.e. expansion method) described in class.