Active Members
TodayLast 7 Days
more...

Posted Date: 05 Feb 2010      Posted By:: dheeraj    Member Level: Silver    Points: 5 (Rs. 1)

2009 Indian Institute of Technology Kanpur M.Tech Neural Networks Cse310 hw University Question paper

 Course: M.Tech Neural Networks University/board: Indian Institute of Technology Kanpur

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. Find the smallest integer N  1 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 each function f(n) (the row index in the following table) and time t (the column
index in the following table), determine the largest size n of a problem that can be solved in
time t, assuming that the algorithm takes f(n) microseconds to solve an instance of a problem
of size n. Fill the value n in the corresponding entry.
1 second 1 minute 1 hour 1 day 1 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 two sets (not the union): an element of the LHS has the form f(n) = f1(n) + f2(n),
where f1(n) 2 (n) and f2(n) 2 O(n1:5).
4. (10 pts) Prove that n50 = O(2n).
5. (10 pts) Prove that nn+3 6= ((n + 3)n).
1

Related Question Papers:

• M.E Electronics and Telecommunications

• M.E Computer Science Gate Questions

• Indian Institute of Technology Kanpur JMET 2006 English University Question Paper

• Indian Institute of Technology Kanpur JMET 2006 English University Question Paper

• CBSE Indian Institute of Technology Kanpur M.E Computer Science Gate Questions

• Categories

Submit Previous Years University Question Papers and make money from adsense revenue sharing program

Are you preparing for a university examination? Download model question papers and practise before you write the exam.