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


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
SEMESTER Spring 2020

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 instructions

Your 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

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:

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.

 

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

 

+ 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: 1699

.

+ 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)

Attachments:

Replies to This Discussion

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)

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

Solution File: https://drive.google.com/open?id=1QaIg-J4DeJTxeX-SxPsrqm15RRhi3T8K

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

below link 

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  

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 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)

RSS

Today Top Members 

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

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

.