CS502 Assignment No. 02 Solution and Discussion
-
Assignment No. 02
SEMESTER Fall 2019
CS502- Fundamentals of Algorithms
Total Marks: 20Due 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 [email protected]
GOOD LUCK
-
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 termsT(n) = O (n2)
-
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 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 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 } }
-
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 termsT(n) = O (n2)
-
