CSC300: Homework [1/2] Previous pageContentsNext page

+ Read Algorithms through the end of 2.5 (including 2.2,2.3)
  You should pay closer attention to 2.2 than 2.3 since mergesort will
  be on the final exam, but quicksort will not.

+ Do these problems on paper, to hand in on Monday, November 12, 2018:
  Be sure to do the starred ones.
    2.4.2 (Don't confuse find-the-max and remove-the-max)
    2.4.4
    2.4.5

    2.4.9* (Draw min heaps.)
    2.4.11 (Also say why.  Don't confuse find-the-max and remove-the-max)
    2.4.12 (Also say why.  Don't confuse find-the-max and remove-the-max)
    2.4.15* (The method MinPQ.isMinHeap does this recursively.  What would
            an iterative solution be?  You should make sure you understand
            this and can do it without looking at MinPQ.isMinHeap.)
    2.4.27* (Argue that your solution is constant time/space.)

+ OPTIONAL (not for credit):
  Do the MyDeckSort assignment and hand in MyDeckSort.java
  Your goal is to implement the sort(MyDeck) method of MyDeckSort.
  You can use only the public method of MyDeck.
  You should not change the functionality of MyDeck.
  Hand in only MyDeckSort.java

  This is based on problem 2.1.14 from the text.

  To get started, download MyDeckSort from d2l.
  You need only edit the MyDeckSort class.
  Leave the Deck class (in the same file) alone.

  The Deck class has the following API:
  
    MyDeck (int N)                 // create a randomized Deck of size N
    int size ()                    // return the size of N
    int ops ()                     // return the number of operations performed on this Deck
    boolean topGreaterThanNext ()  // compare top two items
    void swapTopTwo ()             // swap top two itens
    void moveTopToBottom ()        // move top item to bottom
    void isSorted ()               // check if isSorted (throws exception if not)

--------------------
MyDeckSort Hints:

Assume that the deck d has d.size() cards.
So you might say:

for (int i=0; i<d.size(); i++) {
  if (d.topGreaterThanNext()) {
     d.swapTopTwo ()
  }
  d.moveTopToBottom ()
}


Note that you can go through the whole deck using a loop:

for (int i=0; i<d.size(); i++) {
  ...
  d.moveTopToBottom ()
}

You can also go through the deck d.size() times!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

You can do different things at different point of the process!

for (int i=0; i<d.size(); i++) {
  for (int j=0; j<i; j++) {
    ...
    d.moveTopToBottom ()
  }
  for (int j=i; j<d.size(); j++) {
    ...
    d.moveTopToBottom ()
  }
}

Previous pageContentsNext page