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

    @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

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

    You are required to determine (write down the name) the algorithm being used while sorting the above given array.

    Answer: Selection Sort Algorithm.


  • Cyberian's Gold



    Recent Topics


  • 1
  • 5
  • 12
  • 4
  • 3
  • 2
  • 2
  • 2
|