We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>
+ Link For Assignments, GDBs & Online Quizzes Solution 
+ Link For Past Papers, Solved MCQs, Short Notes & More 
Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion
How to Add New Discussion in Study Group ? Step By Step Guide Click Here.
Assignment No. 02 CS502 Fundamentals of Algorithms 
Total Marks: 20
Due Date: 06/16/2020 

Instructions Please read the following instructions carefully before solving & submitting assignment: 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 corrupt. · The assignment is fully or partially copied from (other student or ditto copy from handouts or internet). · Student ID is not mentioned in the assignment File or name of file is other than student ID. · The assignment is not submitted in .doc or .docx format. Uploading instructionsYour submission must include:
· Assignment should be in .doc or .docx format. · Save your assignment with your ID (e.g. bx180200786.doc). Assignment submission through email is NOT acceptable ObjectiveThe objective of this assignment is · To give basic knowledge and understanding of Algorithms. · To be able to design sorting algorithms. · To be able to understand and calculate the complexity of algorithms.
Note: Your answer must follow the below given specifications. · Font style: “Times New Roman” · Font color: “Black” · Font size: “12” · Bold for heading only. · Font in Italic is not allowed at all. · No formatting or bullets are allowed to use. · Your answer should be precise and to the point, avoid irrelevant detail.
Lectures Covered: This assignment covers Lecture # 08  14 Deadline Your assignment must be uploaded/submitted at or before: 06/16/2020.

Consider the given array having unsorted elements, and answer the two questions asked below.
Question no 01: (10: Marks)
Apply quick sort algorithm on below given array by taking value (30) as pivot element and write down the resulted arrays till first pass only.
Question no 02: (10: Marks)
Write down the recurrence relation of quick sort in case of average or normal case means when the pivot’s element location is the middle of array.
=====================================Ended=======================================
For any query about the assignment, contact at CS502@vu.edu.pk
GOOD LUCK 
Tags:
+ 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?.
+ 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)Please Discuss here about this assignment.Thanks
Our main purpose here discussion not just Solution
Students having same subject can start discussion here to solve assignment, GDB & Quiz and can clear their concepts until solution is provided.
P.S: Please always try to add the discussion in proper format title like “CS101 Assignment / GDB No 01 Solution & Discussion Due Date: ___________”
Then copy Questions from assignment file and paste in Discussion.
+ http://bit.ly/vucodes (For Assignments, GDBs & Online Quizzes Solution)
+ http://bit.ly/papersvu (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)
The link of solution file is given in the given below and in this video we learn about the partition algorithm and quick sort algorithm
Solution File: https://drive.google.com/open?id=1QaIgJ4DeJTxeXSxPsrqm15RRhi3T8K
Hello friends welcome to Raza Academy. You will gain knowledge of mathematics,Computer Science,Information Technology(IT),Software Development and other modern software with full concept. Here in this video tutorial I am uploading second assignment of CS502 Fundamental of Design and Analysis Of Algorithms. Please like my video share with your friends and Subscribe if you are new to the channel.
CS502 Assignment 1 Correct Solution Spring 2020
Please doing with your hand and inshAllah after watching your videos you will be able to konwing each is everthing
Analysis of MergeSort Algorithm is implemented for recurrence relationship in Quicksort.
It is advised that use analysis of QuickSort algorithm for recurrence relation of quick sort in case of average .
QuickSort and MergeSort are two separate algorithms and therefore average case analysis of recurrence are also change for both.
Thanks if someone got my point
Upload correct solution of Assignment.
Recurrence relations based on divide and conquer T(n) = 2T(n/2) + cn
For recurrence relation T(n) = 2T(n/2) + cn
logb(a) = log2(2) // for values of a = 2, b = 2 and k = 1
= 1
= k
So complexity will be Θ(nlog2(n))
T (n) = O (n log_{2} n)
Can you please provide correct solution???
Assignment #2
Smester: Spring 2020
CS502 Fundamentals of Algorithms
Question No: 1
Apply quick sort algorithm on below given array by taking value (30) as pivot element and write down the resulted arrays till first pass only.
30 
48 
10 
20 
70 
15 
80 
40 
∞ 
Solution:
Pivot = 30
30 
48 
10 
20 
70 
15 
80 
40 
∞ 
l=low h=high
i j
Point i will move R.H.S until it gets element greater then Pivot i.e greater then 30
Point j will move L.H.S until it gets element smaller then Pivot .
30 
48 
10 
20 
70 
15 
80 
40 
∞ 
l i j h
30 
15 
10 
20 
70 
48 
80 
40 
∞ 
l i j h
Now if we move point i to the next element which is 10 then it is not greater then pivot and so is for 20 that’s why we will move i to the next element which is 70
And from point j if we move towards next element which is 70 and its not lesser then pivot so we will move to the next element which is 20 and is lesser then pivot.
30 
15 
10 
20 
70 
48 
80 
40 
∞ 
l j i h
Both the points i and j cross each other so replace j with pivot point
and we get,
P
20 
15 
10 
30 
70 
48 
80 
40 
∞ 
l h
Now the partition
Algorithm is given bellow:
Partition (l, h)
{
Pivot = A[1]; i = l, j
= h;
while (I < j)
{
do
{
i++;
} while (A[i]
<=pivot);
do
{
j;
} while (A[j]
>pivot);
if (I < j)
{
Swap
(A[i],
A[j]);
}
}
Swap(A[l], A[j]);
return j;
}
We get the following
resulted array after the first
pass(means partition
algorithm)
P
20 
15 
10 
30 
70 
48 
80 
40 
∞ 
l h
Now apply following quick sort algorithm on resulted array by taking
Value (30) as pivot element
QuickSort (l, h)
{
if (l< h)
{
j = partition
(l, h);
QuickSort (l,
j); QuickSort
(j+1, h);
}
}
Question No 2:
Write down the recurrence relation of quick sort in case of average or normal case means when the pivot’s element location is the middle of array.
Solution:
The recurrence relation of quick sort in case of average or normal case is as given below:
T(n) = 1 if n = 1, 2T(n/2) + n otherwise
T(n) =2T(n/2) + O(n)
=4T(n/4) + O(n)
=4(2T(n/8) +O(n)
=8T(n/8) + O(n)
=8(2T(n/16) + O(n)
=16T(n/16) + O(n)
If n is a power of 2 then let n = 2^{k} or k = log n.
T(n) = 2^{k}T(n/(2^{k})) + O(n)
=2^{k}T(n/(2^{k})) + O(n)
=2^{(log n)}T(n/(2^{(log n)})) + n(log n)
=2^{(log n)}T(n/n) + n(log n)
=nT(1) + n log n
=n + n log n
Or T(n) = O(n log n)
© 2020 Created by +M.Tariq Malik. Powered by
Promote Us  Report an Issue  Privacy Policy  Terms of Service
VU Students reserves the right to delete profile, which does not show any Activity at site nor has not activity more than 01 month.
We are usergenerated contents site. All product, videos, pictures & others contents on vustudents.ning.com don't seem to be beneath our Copyrights & belong to their respected owners & freely available on public domains. We believe in Our Policy & do according to them. If Any content is offensive in your Copyrights then please email at m.tariqmalik@gmail.com or Contact us at contact Page with copyright detail & We will happy to remove it immediately.
Management: Admins ::: Moderators
Awards Badges List  Moderators Group
All Members  Featured Members  Top Reputation Members  Angels Members  Intellectual Members  Criteria for Selection
Become a Team Member  Safety Guidelines for New  Site FAQ & Rules  Safety Matters  Online Safety  Rules For Blog Post