Download Model question papers & previous years question papers
|
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
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
Return to question paper search
|
|
|
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.