We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More

CS502 Assignment No. 02 Solution & Discussion Due Date: Dec 07, 2015

CS502 - Fundamentals of Algorithms Assignment No. 02 Solution Fall 2015 Due Date Dec 07, 2015

Assignment No. 02
Semester: Fall 2015

CS502: Fundamentals of Algorithms

Due Date:07/12/2015

Instructions

Please read the following instructions carefully before submitting assignment:

 

It should be clear that your assignment will not get any credit (zero marks) if:

  • The assignment is submitted after due date.
  • The submitted assignment is other than .doc file.
  • The submitted assignment does NOT open or file is corrupted.
  • The assignment is copied (from other student or ditto copy from any other source).

 

Objective

 

The objective of this assignment is to enable students:

 

  • Write and solve recurrence relations of recursive algorithms using iteration method
  • Design algorithm using Divide and conquer approach

 

Submission

 

You are required to submit your solution through LMS as MS Word document.

 

For any query about the assignment, contact at CS502@vu.edu.pk

                                                             GOOD LUCK

 

Question 1:

 

Consider the following recursive algorithm for computing the sum of the first n squares:

Sum(n) = 12 + 22 + . . . + n2.

 

Algorithm: SUM(n)

if n = 1 return 1

else return SUM(n − 1) + n ∗ n

 

Write recurrence relation for above algorithm and solve it using Iteration Method.

 

Question 2:

 

In Divide and conquer strategy, three main steps are performed:

 

  1. 1.      Divide: Divides the problem into a small number of pieces
  2. 2.      Conquer: Solves each piece by applying divide and conquer to it recursively
  3. 3.      Combine: Combines/merges the pieces together into a global solution.

 

Write an algorithm to find minimum number from a given array of size ‘n’ using divide and conquer approach.

 

 

Lectures Covered:  This assignment covers first 15 Lectures.

Deadline:             Your assignment must be uploaded/submitted at or before 07 Dec, 2015. 

+ How to Follow the New Added Discussions at Your Mail Address?

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?


See Your Saved Posts Timeline

Views: 17816

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

+ Click Here To Join (Our facebook study Group)

Replies to This Discussion

by iteration it doesn't take the required algo

koi 2nd question b discuss kar dy 

apka first ho gia hai ?

Is Question no.2 answer is Selection Sort Algorithm.?

divide n con

Yeh Assignment ajeeb and tuff  hai.

sab students sa request hai k woh sir ko mail kar ka boley k 2nd Assignment ko cancel kar ka koi aur  assignment dey.

idea 

First of all, if n == 1 you should probably return 1. And yes, this recursive function computes 1 + 2^3 + 3^3 + ... + n^3. How do we know that?

Well, take an example like n = 5;

  • R(5) returns R(4) + 5^3
  • R(4) returns R(3) + 4^3
  • ....
  • R(2) returns R(1) + 2^3
  • R(1) returns 1

If you add them up => R(5) returns 5^3 + 4^3 + .. + 2^3 + 1.

 

EXPLANATION:

Denoting S(n) the sum of the first n cubes, S(n) must be a polynomial of the fourth degree in n, let

S(n) = an^4+bn³+cn²+dn.

This is because

1) S(0)= 0, so there is no independent term,

2) When computing S(n)-S(n-1), which must equal , you get a polynomial of the third degree, by cancellation of the quartic term:

S(n)-S(n-1) = a(n^4-(n-1)^4)+b(n³-(n-1)³)+c(n²-(n-1)²)+d(n-(n-1)).

Developing and simplifying,

a(4n³-6n²+4n-1)+b(3n²-3n+1)+c(2n-1)+d = n³. 

Let us identify the coefficients:

n³:  4a        =1 
n²: -6a+3b =0
n: 4a-3b+2c =0
1: -a +b -c+d=0
Solving this triangular system is straigthforward:
a=1/4 
b=1/2
c=1/4
d=0.

and finally

S(n) = (n^4+2n³+n²)/4 = n²(n+1)²/4.

 Check iteration method of power 2 k=log n

T(n) = 2kT (n/(2k)) + (n+n+n+....+n)

= n + n log n

see on page 31


Lecture number 8 the solution s given 
EXAMPLE FROM BOOK:

plz guide us ya working to nahe karne 

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

first question ka exact answer kia hai.?

iteration method sy krna hai question but jo problem arhi wo sum ki hai

how to solve n convert that into exact format 

Itni mushkil assignment :(
aik lafz ki bhi samajh nahi aa rahi :(

RSS

Latest Activity

Farhan Amin replied to Farhan Amin's discussion your vu email address will deleted
1 hour ago
Farhan Amin replied to Farhan Amin's discussion your vu email address will deleted
1 hour ago
+ ! ! ! ! ! AaiMa AnsaRi liked + M.Tariq Malik's discussion CS201 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 14-11-2019
1 hour ago
+ ! ! ! ! ! AaiMa AnsaRi replied to + M.Tariq Malik's discussion MGT211 GDB Fall 2019 Solution & Discussion in the group MGT211 Introduction To Business
1 hour ago
+ ! ! ! ! ! AaiMa AnsaRi joined + M.Tariq Malik's group
1 hour ago
+ ! ! ! ! ! AaiMa AnsaRi liked + M.Tariq Malik's discussion MGT211 GDB Fall 2019 Solution & Discussion
1 hour ago
+ Abb@s replied to Farhan Amin's discussion your vu email address will deleted
1 hour ago
+ Danial replied to Farhan Amin's discussion your vu email address will deleted
2 hours ago
Shine--Ex-VUStudent liked + "J ɨ y ą ⋆'s discussion meliiiiiiii dailyyyyyyyyyyyyyyyyy milkkkkkkkkkkkkkkkkk :(
2 hours ago
+ Danial replied to Farhan Amin's discussion your vu email address will deleted
2 hours ago
Shine--Ex-VUStudent liked +"Certified Gangster"++'s discussion New invention of Microsoft
2 hours ago
Moji posted a discussion
2 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to + M.Tariq Malik's discussion MGT211 GDB Fall 2019 Solution & Discussion in the group MGT211 Introduction To Business
2 hours ago
Muhammad Usman Shahzad replied to + M.Tariq Malik's discussion CS601 Assignment No 01 Fall 2019 Solution & Discussion Due Date: 14-11-2019 in the group CS601 Data Communication
2 hours ago
Muhammad Usman Shahzad joined + M.Tariq Malik's group
2 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to sayyad saqib hussain shah's discussion HRM 626 HANDOUTS REQUIRED PLS
3 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to Farhan Amin's discussion your vu email address will deleted
3 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to + M.Tariq Malik's discussion MTH302 Business Mathematics & Statistics Assignment No 01 Fall 2019 Solution & Discussion in the group MTH302 Business Mathematics & Statistics
3 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to + M.Tariq Malik's discussion MTH302 Business Mathematics & Statistics Assignment No 01 Fall 2019 Solution & Discussion in the group MTH302 Business Mathematics & Statistics
3 hours ago
+ "αяsαℓ " Ќąƶµяɨ •" replied to + M.Tariq Malik's discussion MTH302 Business Mathematics & Statistics Assignment No 01 Fall 2019 Solution & Discussion in the group MTH302 Business Mathematics & Statistics
3 hours ago

© 2019   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service