Indian Institute of Technology Kanpur (IIT-K) 2009 M.Tech Neural Networks Cse310 hw - Question Paper

CSE310 HW01,
Please note that you have to typeset your assignment using either LATEX or Microsoft
Word. Hand-written assignment will not be graded. You need to submit a hardcopy
before the lecture on the due date. You also need to submit an electronic version at
the digital drop box. For the electronic version, you should name your le using the
format HWxy-LastName-FirstName.
1. (10 pts) Let f(n) = n3 and g(n) = 100  n  log2 n. obtain the smallest integer N  one such
that f(N)  g(N) but f(N + 1) > g(N + 1). Show the values of N, f(N), g(N), f(N + 1)
and g(N + 1).
2. (10 pts) For every function f(n) (the row index in the subsequent table) and time t (the column
index in the subsequent table), determine the largest size n of a issue that can be solved in
time t, assuming that the algorithm takes f(n) microseconds to solve an instance of a issue
of size n. Fill the value n in the corresponding entry.
1 2nd one minute one hour one day one year
pn
n
n2
2n
3. (10 pts) Prove that (n) + O(n1:5)  O(n1:5).
Note that for this problem, you are proving that the set of functions on the left hand side (LHS)
is a subset of the set of functions on the right hand side (RHS). The set on the LHS is algebraic
sum of 2 sets (not the union): an element of the LHS has the form f(n) = f1(n) + f2(n),
where f1(n) two (n) and f2(n) two O(n1:5).
4. (10 pts) Prove that n50 = O(2n).
5. (10 pts) Prove that nn+3 6= ((n + 3)n).
1

Earning:   Approval pending.