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

h04: Sorting

ready? assigned due points
true Thu 05/04 09:30AM Tue 05/09 09:30AM

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

MAY ONLY BE TURNED IN IN THE LECTURE/LAB 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 three lowest scores (if you have zeros, those are the three lowest scores.)

https://ucsb-cs32-s17.github.io/hwk/h04/

Reading: Sorting, DS 13.2-3

  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.
    • WRITING (not circling!) either 11, 12, 1, or 2, to indicate your discussion section (lab) meeeting time.
    • Writing your first and last initial in large capital letters.

    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.
    For gradescope self-submission: PLEASE get the pages in the correct order. First page of your PDF file is p1, the next is p2.

  2. Circle the big-O worst-case running time for for sorting an array of n elements, using these algorithms:
    1. (2 pts) Mergesort
          O(1)      O(log n)      O(n)      O(n log n)     O(n2)      O(n2 log n)      O(n3)
    2. (2 pts) Quicksort
          O(1)      O(log n)      O(n)      O(n log n)     O(n2)      O(n2 log n)      O(n3)
    3. (2 pts) Heapsort
          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. (2 pts) Mergesort
          O(1)      O(log n)      O(n)      O(n log n)     O(n2)      O(n2 log n)      O(n3)
    2. (2 pts) Quicksort
          O(1)      O(log n)      O(n)      O(n log n)     O(n2)      O(n2 log n)      O(n3)
    3. (2 pts) Heapsort
          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. (5 pts) Imagine how you might respond to the question, say in a job interview, "What is the main idea behind divide-and-conquer?" (Nota bene: you will NOT have a textbook with you at the interview, so you can't just copy from the book to here. Answers that look too "copied" may lose some points.)
      2.  
    2. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Mergesort.
      3.  
    3. (5 pts) Describe briely how the divide-and-conquer idea, as you explained in part (a), applies to Quicksort.
      4.  
    4. (5 pts) Given that the way divide-and-conquer applies to Mergesort and Quicksort is similiar, briefly hilight the difference(s) between Mergesort and Quicksort.
  5. (5 pts) Describe briefly, as in a job interview (i.e. no copying), the role of the pivot element in Quicksort.
  6. (3 pts) Describe briefly how to represent a binary tree in an array. Draw a picture if you need to.