CS502 Assignment # 02 Solution Spring 2013

by ChIntoo Mon May 13, 2013 4:52 pm

Assignment No. 02, Semester: Spring 2013, CS502-Fundamentals of Algorithms last date 15/05/2013
Lectures Covered: 7 to 15

Objective
To solve Recurrence relations using Iteration method.

Uploading instructions:
Please view the Assignment Submission Process document provided to you by the Virtual University for uploadingassignments.

Your assignment must be in .doc format. (Any other formats like scan images, PDF, Zip, rar, bmp etc. will not be accepted).
Save your assignment with your ID (e.g. bc020200786.doc).
No assignment will be accepted through email.

Rules for Marking:
It should be clear that your assignment will not get any credit if:

The assignment is submitted after due date.
The submitted assignment does not open or file is corrupted.
Your assignment is copied from internet, handouts or from any other student

(Strict disciplinary action will be taken in this case).

Solve the following recurrence relation using Iteration method.

T(n)= 1 if n=1 , 4T (n/4)+ n^2

NOTE: Submit “.doc” file only. Every student should provide his/her own work, exact copying of the assignment (or some portion of the assignment) from the internet or other students will lead to copy case and zero marks will be awarded. Different softwares will be used to check plagiarism in assignments. Do not put any query on MDB about this assignment, if you have any query then email at [You must be registered and logged in to see this link.]

by Victoria333 Mon May 13, 2013 4:53 pm

please read carefully page no:31 from handout to solve the question

see the first four pages of the file to solve the assignment question

by ChIntoo Mon May 13, 2013 4:54 pm

= 4T(n/4) + n + n
= 4(2T(n/ Cool

+ n/4) + n + n
= 8T(n/ Cool

+ n + n + n
= 8(2T(n/16) + n/ Cool

+ n + n + n
= 16T(n/16) + n + n + n + n
If n is a power of 2 then let n = 2k or k = log n.
T(n) = 2kT(n/(2k)) + (n + n + n + · · · + n) | {z }
k times
= 2kT(n/(2k)) + kn
= 2(logn)T(n/(2(logn))) + (log n)n
= 2(logn)T(n/n) + (log n)n
= nT(1) + n log n = n + n log n

by Sponsored content

CS502 Assignment # 02 Solution Spring 2013

CS502 Assignment # 02 Solution Spring 2013

Re: CS502 Assignment # 02 Solution Spring 2013

Re: CS502 Assignment # 02 Solution Spring 2013

Re: CS502 Assignment # 02 Solution Spring 2013