www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

# CS502 Assignment No. 2 Spring 2020 Due date 13-06-2020

Assignment No. 02
SEMESTER Spring 2020

CS502- Fundamentals of Algorithms

Total Marks: 20

Due Date: 06/16/2020

Instructions

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.

·         Assignment should be in .doc or .docx format.

Assignment submission through email is NOT acceptable

## Objective

The 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:

·          Font style: “Times New Roman”

·          Font color: “Black”

·          Font size: “12”

·          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

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.

 30 48 10 20 70 15 80 40 ∞

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

Views: 2052

Attachments:

### Replies to This Discussion

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)

Due Date 11 June 2020

# Learn CS502 Fundamental of Algorithms with Washi - Solution of Assignment 2 Spring 2020

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

code totally copied from handouts

# CS502 Assignment No 2 Solution Spring 2020 100% Correct

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 solution 1

Cs502 assignment solution 1

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

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 log2 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 = 2k or k = log n.

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

=2kT(n/(2k)) +  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)

1

2

## Latest Activity

10 hours ago
10 hours ago
kashifali left a comment for Momna Arshad
10 hours ago
kashifali left a comment for jiya ali
10 hours ago
kashifali left a comment for jiya ali
10 hours ago
Golden Eye liked Black Bird Scientist's discussion graphic designer required
13 hours ago
Momna Arshad and +** KAKAR **+ are now friends
14 hours ago
23 hours ago