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



Jan
27
(2 Views / 0 Upvotes)
0 Replies

10. COGNITIVE | CLOUD COMPUTING
709a4b58-3423-4963-9e29-bd995cadb5fc-image.png
Cloud computing is the on-demand availability of computer system resources, especially data storage and computing power, without direct active management by the user. The term is generally used to describe data centers available to many users over the Internet.

Aug
19
(33 Views / 0 Upvotes)
2 Replies

Dear Students if you have any query regarding Final Term Exam
Please Feel Free to Ask Cyberian’s

Sep
18
(29 Views / 0 Upvotes)
0 Replies

یہ ۵ جی کیا ہے؟
دوسرے سیلولر نیٹ ورکوں کی طرح ، 5 جی نیٹ ورک سیلولرکلز کرنے کے انتظامات کو استعمال کرتے ہیں جو اپنے ڈومین کو علاقوں میں الگ کرتے ہیں اور ریڈیو لہروں کے ذریعہ انکوڈڈ معلومات بھیجتے ہیں۔ ہر سیل سائٹ کو سسٹم کی ریڑھ کی ہڈی سے وابستہ ہوتا ہے، اس سے قطع نظر کہ وائرڈ یا ریموٹ بیک ہاؤل ایسوسی ایشن کے ذریعے۔ 5 جی نیٹ ورک ایک قسم کی انکوڈنگ کا استعمال کریں گے جسے آف ڈی ایم کہتے ہیں ، جو انکوڈنگ کی طرح ہے جس میں 4 جی ایل ٹی ای کام کرتا ہے۔ تاہم ، ہوائی انٹرفیس کا مقصد...

Dec
17
(15 Views / 0 Upvotes)
21 Replies

Live Updates:
Pakistan’s former dictator Pervez Musharraf was on Tuesday sentenced to loss of life in the excessive treason case by way of a special court docket here, turning into the first navy ruler to get hold of the capital punishment in the country’s history.
567e9088-009d-47b4-a689-988ca233129e-image.png
A three-member bench of the special courtroom, hea...

Sep
6
(44 Views / 0 Upvotes)
0 Replies

فیس بک ڈیٹنگ اپنی پسند کی چیزوں کے ذریعہ پیار تلاش کرنا آسان بناتا ہے - اپنی مشترکہ چیزوں ، جیسے مفادات ، واقعات اور گروہوں کے ذریعہ معنی خیز تعلقات شروع کرنے میں مدد کرتا ہے۔ یہ ڈیٹنگ پروفائل بنانے میں کام کرتا ہے اور آپ کو زیادہ مستند نظر دیتا ہے کہ کوئی کون ہے۔
a5068e0f-944c-4e27-b28d-bec69b167543-image.png
آج ، ہم امریکہ میں فیس بک ڈیٹنگ کا آغاز کر رہے ہیں۔ ہم لوگوں کو انسٹاگرام ...

Aug
22
(101 Views / 1 Upvotes)
1 Replies

I’d say as a blogger and a IT student that it’s a great achievement for a local operator. As we know, communication is expanding globally and we do need faster networks to communicate.
IMG_20190822_194412.jpg

I’d say as a blogger and a IT student that it’s a great achievement for a local operator. As we know, communication is expanding globally and we do need faster netwo...

Sep
6
(15 Views / 0 Upvotes)
0 Replies

b244dd88-39a0-47bb-95f5-5af7cf1991c7-image.png

Image: justin sullivan / Getty Images

کمپنی نے منگل کو اعلان کیا کہ فیس بک اپنی چہرے کی شناخت کی خصوصیات کو بند کرنے میں آسان تر بنا رہا ہے اور اب وہ خود بخود نئے صارفین کو فیس ٹیگنگ کا انتخاب نہیں کرے گا۔

فیس بک اپنے صارفین کے اپ لوڈ کردہ فوٹو میں چہروں کی شناخت کے لئے چہرے کی پہچان کا استعمال...

Aug
6
(22 Views / 0 Upvotes)
0 Replies

Join the celebration at the all-new Apple Aventura.
Our new location opens Saturday, August 10 at 10:00 a.m.
Join us for the grand opening of our new store - located in a bigger space right across from the Aventura Slide Tower. Come celebrate your creativity during opening weekend with free Today at Apple sessions in music, photography, art, and more. And enjoy our vibrant Latin Music Fridays happening throughout the month of August.

Sep
6
(21 Views / 0 Upvotes)
0 Replies

آئی فونز اور ہیکرز پر حالیہ ہیک حملے کی وجہ سے جس کو دنیا میں سب سے زیادہ محفوظ فون سمجھا جاتا تھا اس کی سیکیورٹی کو نظرانداز کیا جارہا ہے۔ کیا آپ کو ایسی کوششوں سے بچایا گیا ہے؟ آپ خود کو ڈیجیٹل طور پر کیسے محفوظ کرسکتے ہیں؟

آئی فون ہیکنگ آپریشنوں کی ایک حالیہ لہر جنہوں نے جنوری تک “ایک ہفتے میں ہزاروں صارفین” کو متاثر کیا ، گوگل کے پروجیکٹ زیرو سیکیورٹی ٹیم کے محققین نے انکشاف کیا ہے۔ ایپل کے آئی فونز کو بڑے پیمانے پر وہاں کے سب سے محفوظ آلات سمجھا جاتا ہے۔ واقع...

Jul
31
(143 Views / 0 Upvotes)
1 Replies

To register your device, go to this link and create your account as an individual user. Select your user type International traveler
On submission of Signup form, a confirmation link will be received in your provided email address. Cl...

    Recent Topics


  • 15
  • 2
  • 2
  • 2
  • 2
  • 8
  • 1
  • 6
| DMCA.com Protection Status