Analyze This

Answer the below in analyze.md.

Questions

  1. Suppose that Stelios has just finished playing a board game that has cards, each of which has a unique 2-digit number from 00 through 99. Thanks to expansion packs, Stelios has more than 100 such cards, so some of the cards have the same 2-digit numbers. The cards are all out of order now, and Stelios would like to put them away in sorted order, from smallest (00) to largest (99). Stelios adopts the following strategy:


    1. Stelios divides the cards into ten piles based on the cards' last (i.e., rightmost) digit, turning each card face-down as he places it onto its pile. When finished with this process, he thus has ten piles of cards with at least ten cards in each. Within each pile, every card thus has the same last digit.

    2. Stelios then turns each of those ten piles face-up and creates one big stack, placing the "ends with a 9" pile on the bottom, then the "ends with an 8" pile on top of that, and so on.

    3. Stelios next goes through that big stack in order, from top to bottom, dividing the cards into ten new piles based on the cards' first digit (i.e., leftmost), turning each card face-down as he places it onto its pile. When finished with this process, he thus has ten piles of cards with at least ten cards in each. Within each pile, every card thus has the same first digit.

    4. Stelios then turns each of those ten piles face-up and creates one big stack again, this time placing the "starts with a 9" pile on the bottom, then the "starts with an 8" pile on top of that, and so on.

    5. Stelios then puts a rubber band around the stack and puts it away.


    1. (1 point.) Is this algorithm correct?

    2. (2 points.) Independent of this algorithm’s correctness, what is the upper bound on this algorithm’s runtime? Why?

  2. Speaking of sorting, suppose that Maria has noticed a problem with bubble sort! She’s observed that if the array being sorted has some of its largest elements near the beginning of the array, it takes a very short amount of time for those elements to "bubble up" to their correct positions toward the end of the array, because they will be swapped multiple times in a single pass of bubble sort’s algorithm. On the other hand, if the array being sorted has some of its smallest elements near the end of the array, it takes a very long time for those smallest elements to "bubble down" to their correct positions, since they will be swapped at most once in a single pass of bubble sort’s algorithm.

    Maria would like to improve upon bubble sort in order to fix this problem she’s seen. Her new sorting algorithm would start out like bubble sort, bubbling the largest element to the end of the array. But instead of going back to the beginning of the array to bubble up the next largest element, the next thing she does is "invert" the algorithm, instead proceeding right-to-left across the array, making swaps to bubble the smallest element to the beginning. From there, the algorithm would oscillate back and forth between bubbling the largest unsorted element to the right, and then the smallest unsorted element to the left, until there are no more elements to sort.

    1. (1 point.) Is this algorithm correct?

    2. (2 points.) Independent of this algorithm’s correctness, what is the upper bound on this algorithm’s runtime? Why?

  3. Natalie has a mixed-up pile of playing cards (that may or may not contain every card in the deck), and is looking for her favorite one: the queen of hearts. Her strategy for finding it, in pseudocode, is the below:

    0  look at the top card of the deck
    1  if it is the queen of hearts
    2      succeed
    3  else
    4      discard the top card of the deck
    5      if the deck is now empty
    6          fail
    7      else
    8          shuffle the rest of the deck
    9          go to line 0
    1. (1 point.) Is this algorithm correct?

    2. (2 points.) Independent of this algorithm’s correctness, what is the upper bound on this algorithm’s runtime? Why?

Debrief

  1. Which resources, if any, did you find helpful in answering this problem’s questions?

  2. About how long did you spend on this problem’s questions?