CS502 Assignment # 02 Solution Spring 2013

View previous topic View next topic Go down

GMT + 8 Hours CS502 Assignment # 02 Solution Spring 2013

Post by ChIntoo on 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.].pk
avatar
ChIntoo
Monstars
Monstars

Posts : 92
Join date : 2011-02-13

Back to top Go down

GMT + 8 Hours Re: CS502 Assignment # 02 Solution Spring 2013

Post by Victoria333 on 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
avatar
Victoria333
Monstars
Monstars

Scorpio Snake
Posts : 267
Join date : 2013-05-12
Age : 28
Location : Victoria
--Mood-- : Woot

Back to top Go down

GMT + 8 Hours Re: CS502 Assignment # 02 Solution Spring 2013

Post by ChIntoo on 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
avatar
ChIntoo
Monstars
Monstars

Posts : 92
Join date : 2011-02-13

Back to top Go down

GMT + 8 Hours Re: CS502 Assignment # 02 Solution Spring 2013

Post by Sponsored content


Sponsored content


Back to top Go down

View previous topic View next topic Back to top


Permissions in this forum:
You cannot reply to topics in this forum