CS502 Quiz 2 Solution and Discussion

[zareen]

Assignment No. 02
SEMESTER Fall 2019
CS502- Fundamentals of Algorithms
Total Marks: 20

Due Date: 27/11/2019
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 full 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 # 09 - 14
Deadline
Your assignment must be uploaded/submitted at or before 27/11/2019.

Assignment diagram:

Consider the given diagram having an unsorted array and its sorting procedure through dry run. You are required to answer the following questions.

Question No 01: (Marks: 5)
You are required to determine (write down the name) the algorithm being used while sorting the above given array.

Question No 02: (Marks: 7)
You are required to design (write) the algorithm (Only Pseudo code) determined in Question 1.

Question No 03: (Marks: 8)
You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 02.

=====================================Ended=======================================

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

GOOD LUCK

[zareen]

Solution:
Question No. 01: The name of the algorithm being used for sorting the given array has given below.
Selection sort
Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.

Pseudo code:
1 Selection sort (A)
{
2 For i 1 to A.lenght-1
{
3 imin i
4 for j i+1 to A.length
{
5 If (A[j] < A[imin])
Imin j
}
6 Temp A[i]
7 A[i] A[imin]
8 A[imin] Temp
}
}

Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,

The time taken by each statement (step) is given as follows,

Selection sort (A) Cost Times
{
For i 1 to A.length-1 c1 n
{
imin i-------------------- c2 n-1
for j i+1 to A.length
{ c3 n+n-1+…1=n(n+1)/2
If (A[j] < A[imin])
imin j
}
Temp A[i] c4 n-1
A[i] A[imin] c5 n-1
A[imin] Temp c6 n-1
}
}

Total time T(n) can be calculated as follows,

T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)

This is equivalent to a polynomial an2+bn+c
Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
Note: a, b, c in polynomial represents constants
// Ignoring constant terms

T(n) = O (n2)

[zareen]

https://youtu.be/7T7QTy9z4CM

[zareen]

Solution:
Question No. 01: The name of the algorithm being used for sorting the given array has given below.
Selection sort
Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.

Pseudo code:
1 Selection sort (A)
{
2 For i 1 to A.lenght-1
{
3 imin i
4 for j i+1 to A.length
{
5 If (A[j] < A[imin])
Imin j
}
6 Temp A[i]
7 A[i] A[imin]
8 A[imin] Temp
}
}

Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,

The time taken by each statement (step) is given as follows,

Selection sort (A) Cost Times
{
For i 1 to A.length-1 c1 n
{
imin i-------------------- c2 n-1
for j i+1 to A.length
{ c3 n+n-1+…1=n(n+1)/2
If (A[j] < A[imin])
imin j
}
Temp A[i] c4 n-1
A[i] A[imin] c5 n-1
A[imin] Temp c6 n-1
}
}

Total time T(n) can be calculated as follows,

T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)

This is equivalent to a polynomial an2+bn+c
Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
Note: a, b, c in polynomial represents constants
// Ignoring constant terms

T(n) = O (n2)

[zareen]

@zareen said in CS502 Assignment No. 02 Solution and Discussion:

You are required to design (write) the algorithm (Only Pseudo code) determined in Question 1.

Selectionsort (A , n)
{
For (i=0 to n-1)                                             
{
min  =  i      C1                         
For (  j = i+1 to n-1)                                         
{                                                             
C2
}
C3
}
}

[zareen]

@zareen said in CS502 Assignment No. 02 Solution and Discussion:

You are required to calculate (Step by Step) the worst case time complexity T(n) of the algorithm designed in Question No. 02.

ANS:
C1 =  (n-1)
C2 = (n-1)+(n-2)+…+1
   =  
C3 = (n-1)
T(n) = (n-1) . C1 +  . C2 +  (n-1)C3
T(n) = an2 + bn + c
Here a,b and c are constants in term of C1, C2 and C3
T(n) = O(n2)

[zareen]

Solution:
Question No. 01: The name of the algorithm being used for sorting the given array has given below.
Selection sort
Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.

Pseudo code:
1 Selection sort (A)
{
2 For i 1 to A.lenght-1
{
3 imin i
4 for j i+1 to A.length
{
5 If (A[j] < A[imin])
Imin j
}
6 Temp A[i]
7 A[i] A[imin]
8 A[imin] Temp
}
}

Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,

The time taken by each statement (step) is given as follows,

Selection sort (A)	Cost	Times

{
For i 1 to A.length-1 |c1 | n
{
imin i--------------------> c2 n-1
for j i+1 to A.length
{ c3 n+n-1+…1=n(n+1)/2
If (A[j] < A[imin])
imin j
}
Temp A[i] c4 n-1
A[i] A[imin] c5 n-1
A[imin] Temp c6 n-1
}
}

Total time T(n) can be calculated as follows,

T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)

This is equivalent to a polynomial an2+bn+c
Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
Note: a, b, c in polynomial represents constants

// Ignoring constant terms

T(n) = O (n2)