CS502 Assignment No. 02 Solution and Discussion


  • Cyberian's Gold

    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:

    0e4a496c-d936-4a99-ac0c-2e198ae8fc43-image.png
    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


  • Cyberian's Gold

    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)


  • Cyberian's Gold

    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,

    b8c2d4d9-76e3-4841-94a7-e8c1a8202f51-image.png

    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)


  • Cyberian's Gold

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

  • Cyberian's Gold

    @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
    }
    }
    

  • Cyberian's Gold

    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)


  • Cyberian's Gold



    Recent Topics


  • 3
  • 1
  • 14
  • 1
  • 1
  • 1
  • 2
  • 1
| DMCA.com Protection Status