Scribd Logo
Upload

Welcome to Scribd!

  • 10 views

    تمرین اول - مهر ۱۴۰۲

    Uploaded by

    ugd.mirzaee
    This document contains exercises on analyzing recursive relations, analyzing algorithms, finding the majority element in an array, and stability of sorting algorithms. It asks to: 1) Analyze two recursive relations. 2) Analyze the time complexity of an algorithm for finding indices of an array. 3) Provide algorithms to find the majority element in O(n log n) and O(n) time. 4) Explain whether bubble sort and merge sort have the stability property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    تمرین اول - مهر ۱۴۰۲

    Uploaded by

    ugd.mirzaee
    10 views2 pages
    This document contains exercises on analyzing recursive relations, analyzing algorithms, finding the majority element in an array, and stability of sorting algorithms. It asks to: 1) Analyze two recursive relations. 2) Analyze the time complexity of an algorithm for finding indices of an array. 3) Provide algorithms to find the majority element in O(n log n) and O(n) time. 4) Explain whether bubble sort and merge sort have the stability property.

    Original Title

    تمرین اول _ مهر ۱۴۰۲ (1)

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains exercises on analyzing recursive relations, analyzing algorithms, finding the majority element in an array, and stability of sorting algorithms. It asks to: 1) Analyze two recursive relations. 2) Analyze the time complexity of an algorithm for finding indices of an array. 3) Provide algorithms to find the majority element in O(n log n) and O(n) time. 4) Explain whether bubble sort and merge sort have the stability property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    10 views2 pages

    تمرین اول - مهر ۱۴۰۲

    Uploaded by

    ugd.mirzaee
    This document contains exercises on analyzing recursive relations, analyzing algorithms, finding the majority element in an array, and stability of sorting algorithms. It asks to: 1) Analyze two recursive relations. 2) Analyze the time complexity of an algorithm for finding indices of an array. 3) Provide algorithms to find the majority element in O(n log n) and O(n) time. 4) Explain whether bubble sort and merge sort have the stability property.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    ‫ﺑﻪ ﻧﺎﻡ ﺧﺪﺍ‬

    ‫ﺳﺎﺧﺘﻤﺎﻥ ﺩﺍﺩﻩ ﻭ ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎ‬


    ‫ﺗﻤﺮﻳﻦ ﺍﻭﻝ‬
    ‫ﺩﺍﻧﺸﮕﺎﻩ ﺻﻨﻌﺘﻲ ﺍﻣﻴﺮﻛﺒﻴﺮ‪ ،‬ﺩﺍﻧﺸﻜﺪﻩ ﺭﻳﺎﺿﻲ ﻭ ﻋﻠﻮﻡ ﻛﺎﻣﭙﻴﻮﺗﺮ‬
    ‫ﻣﻬﺮﻣﺎﻩ ‪۱۴۰۲‬‬

    ‫ﺗﺤﻠﻴﻞ ﺭﺍﺑﻄﻪﻱ ﺑﺎﺯﮔﺸﺘﻲ‬ ‫‪۱‬‬


    ‫ﺭﻭﺍﺑﻂ ﺑﺎﺯﮔﺸﺘﻲ ﺯﻳﺮ ﺭﺍ ﺗﺤﻠﻴﻞ ﻛﻨﻴﺪ‪.‬‬

    ‫‪T (n) = 4 ∗ T (n/4) + n ∗ (logn)2 .۱‬‬

    ‫‪T (n) = T (⌈n/2⌉) + 1 .۲‬‬

    ‫ﺗﺤﻠﻴﻞ ﺍﻟﮕﻮﺭﻳﺘﻢ‬ ‫‪۲‬‬


    ‫ﺁﺭﺍﻳﻪ ]‪ w[1..n‬ﺩﺍﺩﻩ ﺷﺪﻩ ﺍﺳﺖ‪ idx[i] .‬ﺭﺍ ﺍﻳﻨﮕﻮﻧﻪ ﺗﻌﺮﻳﻒ ﻣﻲﻛﻨﻴﻢ ﻛﻪ‪:‬‬

    ‫}]‪idx[i] = max{j : 1 ≤ j < i ∧ w[j] ≤ w[i‬‬

    ‫ﺍﻟﮕﻮﺭﻳﺘﻢ ﺯﻳﺮ ﺭﺍ ﺑﺮﺍﻱ ﭘﻴﺪﺍ ﻛﺮﺩﻥ ]‪ idx[i‬ﺍﺟﺮﺍ ﺧﻮﺍﻫﻴﻢ ﻛﺮﺩ‪:‬‬

    ‫ﺍﻟﮕﻮﺭﻳﺘﻢ ‪ ۱‬ﺑﺮﺭﺳﻲ ﻛﺮﺩﻥ ﺩﺭﺳﺘﻲ ﻭ ﭘﺎﻳﺎﻥﭘﺬﻳﺮﻱ‬


    ‫‪1:‬‬ ‫‪idx[1] = −1‬‬
    ‫‪2:‬‬ ‫‪for i = 2 to n do‬‬
    ‫‪3:‬‬ ‫‪j =i−1‬‬
    ‫‪4:‬‬ ‫‪while w[j] > w[i] ∧ j ̸= −1 do‬‬
    ‫‪5:‬‬ ‫]‪j = idx[j‬‬
    ‫‪6:‬‬ ‫‪idx[i] = j‬‬

    ‫‪ .۱‬ﻧﺸﺎﻥ ﺩﻫﻴﺪ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺑﺎﻻ ﺧﺎﺗﻤﻪ ﭘﺬﻳﺮ ﺍﺳﺖ‪.‬‬

    ‫‪ .۲‬ﻧﺸﺎﻥ ﺩﻫﻴﺪ ﺍﻟﮕﻮﺭﻳﺘﻢ ﭘﺎﺳﺦ ﺻﺤﻴﺢ ﺭﺍ ﺗﻮﻟﻴﺪ ﻣﻲﻛﻨﺪ‪.‬‬

    ‫‪ .۳‬ﻣﺮﺗﺒﻪ ﺯﻣﺎﻧﻲ ﺷﺒﻪﻛﺪ ﺭﺍ ﭘﻴﺪﺍ ﻛﻨﻴﺪ‪.‬‬

    ‫‪۱‬‬
    ‫ﻋﻨﺼﺮ ﺍﻛﺜﺮﻳﺖ‬ ‫‪۳‬‬
    ‫ﻳﻚ ﺁﺭﺍﻳﻪﻱ ‪ n‬ﻋﻀﻮﻱ ﺑﻪ ﻋﻨﻮﺍﻥ ﻭﺭﻭﺩﻱ ﺩﺍﺩﻩ ﺷﺪﻩ ﺍﺳﺖ‪ .‬ﻣﻴﺨﻮﺍﻫﻴﻢ ﻋﻨﺼﺮ ﺍﻛﺜﺮﻳﺖ ﺭﺍ ﭘﻴﺪﺍ ﻛﻨﻴﻢ ﻳﺎ ﻣﺸﺨﺺ‬
    ‫ﻛﻨﻴﻢ ﻫﻴﭻ ﻋﻨﺼﺮﻱ ﺍﻛﺜﺮﻳﺖ ﻧﻴﺴﺖ‪ .‬ﻳﻚ ﻋﺪﺩ ‪ a‬ﺍﻛﺜﺮﻳﺖ ﺍﺳﺖ ﺍﮔﺮ ﺑﻴﺶﺗﺮ ﺍﺯ ‪ n/2‬ﺑﺎﺭ ﺩﺭ ﺁﺭﺍﻳﻪ ﺁﻣﺪﻩ ﺑﺎﺷﺪ‪.‬‬

    ‫‪ .۱‬ﺍﻟﮕﻮﺭﻳﺘﻤﻲ ﺍﺯ )‪ O(nlgn‬ﺍﺭﺍﺋﻪ ﺩﻫﻴﺪ ﻛﻪ ﻋﻨﺼﺮ ﺍﻛﺜﺮﻳﺖ ﺭﺍ ﭘﻴﺪﺍ ﻛﻨﺪ‪.‬‬

    ‫‪ .۲‬ﺍﻟﮕﻮﺭﻳﺘﻤﻲ ﺍﺯ )‪ O(n‬ﺍﺭﺍﺋﻪ ﺩﻫﻴﺪ ﻛﻪ ﻋﻨﺼﺮ ﺍﻛﺜﺮﻳﺖ ﺭﺍ ﭘﻴﺪﺍ ﻛﻨﺪ‪.‬‬

    ‫ﭘﺎﻳﺪﺍﺭﻱ ﺍﻟﮕﻮﺭﻳﺘﻢ‬ ‫‪۴‬‬


    ‫ﺁﻳﺎ ﺍﻟﮕﻮﺭﻳﺘﻢﻫﺎﻱ ‪ bubble sort‬ﻭ ‪ merge sort‬ﺩﺍﺭﺍﻱ ﺧﺎﺻﻴﺖ ﭘﺎﻳﺪﺍﺭﻱ ﻫﺴﺘﻨﺪ؟ ﺗﻮﺿﻴﺢ ﺩﻫﻴﺪ‪.‬‬

    ‫‪۲‬‬

    You might also like