1
h10
CS32 F18
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h10: Mergesort and Quicksort

ready? assigned due points
true Tue 10/30 08:00AM Tue 11/06 02:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the four lowest scores (if you have zeros, those are the four lowest scores).

Reading: Mergesort and Quicksort, DS 13.2

  1. (10 pts) Fill in the information in the header. The following are required to get the 10 "participation" points.
    • Filling in your name and umail address.

    Also: For paper submission PLEASE submit on ONE SHEET OF PAPER, double-sided if at all possible. If you must submit on two printed sheets write name on BOTH sheets and no staples, paperclips, or folded corners.

  2. Circle the big-O worst-case running time for for sorting an array of n elements, using these algorithms:

    1. (3 pts) Mergesort

      O(1)  O(log n)  O(n)  O(n log n)  O(n2)  O(n2 log n)  O(n3)
    2. (3 pts) Quicksort

      O(1)  O(log n)  O(n)  O(n log n)  O(n2)  O(n2 log n)  O(n3)
  3. Circle the big-O average case ("expected case") running time for sorting an array of n elements, using these algorithms:

    1. (3 pts) Mergesort

      O(1)  O(log n)  O(n)  O(n log n)  O(n2)  O(n2 log n)  O(n3)
    2. (3 pts) Quicksort

      O(1)  O(log n)  O(n)  O(n log n)  O(n2)  O(n2 log n)  O(n3)
  4. Both Mergesort and Quicksort are divide-and-conquer algorithms.

    1. (6 pts) What is the main idea behind divide-and-conquer?
    2. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Mergesort.
    3. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Quicksort.
    4. (6 pts) Given that the way divide-and-conquer applies to Mergesort and Quicksort is similiar, briefly highlight the difference(s) between Mergesort and Quicksort.
  5. (6 pts) Briefly describe the role of the pivot element in Quicksort.