CSC300: Homework [1/2] Previous pageContentsNext page

+ Read Algorithms through the end of 2.5 (you can skip 2.2,2.3).

+ Do the following eight problems on paper, to hand in on Tuesday, March 12, 2019.
  Be sure to do the starred ones.

  If you are not attending class that day, be sure to submit this homework
  online by the due date.  You can scan into a word document or PDF.  Do not
  submit more than one file (no TIFF, PNG, or similar files, please)

  + 2.4.2 Criticize the following idea: To implement find the maximum in
    constant time, why not use a stack or a queue, but keep track of the
    maximum value inserted so far, then return that value for find the maximum?
    (Don't confuse find-the-max and remove-the-max)
  
  + 2.4.4 Is an array that is sorted in decreasing order a max-oriented heap?

  + 2.4.5 Give the heap that results when the keys E A S Y Q U E S T I O N
    are inserted in that order into an initially empty max-oriented heap.

  + 2.4.9* Draw all of the different heaps that can be made from the five
    keys A B C D E, then draw all of the different heaps that can be made from
    the five keys A A A B B.  (Draw min heaps.)

  + 2.4.11 Suppose that your application will have a huge number of insert
    operations, but only a few remove the maximum operations. Which
    priority-queue implementation do you think would be most effective: heap,
    unordered array, or ordered array?  (Also say why.  Don't confuse
    find-the-max and remove-the-max)

  + 2.4.12 Suppose that your application will have a huge number of find the
    maximum operations, but a relatively small number of insert and remove the
    maximum operations. Which priority-queue implementation do you think would
    be most effective: heap, unordered array, or ordered array?  (Also say why.
    Don't confuse find-the-max and remove-the-max)
  
  + 2.4.15* Design a linear-time certification algorithm to check whether an
    array pq[] is a min-oriented heap.  (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* Find the minimum. Add a min() method to MaxPQ. Your implementation
    should use constant time and constant extra space.  (Argue that your
    solution is constant time/space.) 

+ 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:

Try sorting a list of 4 numbers using these capabilities...
Start with the list that is sorted except that the min is at the end.
It will work something like this:

[1, 2, 3, 0]
            [1, 2, 3, 0]
i=0   j=1   [2, 3, 0, 1]
i=0   j=2   [3, 0, 1, 2]
i=0   j=3   [3, 1, 2, 0]
i=0         [1, 2, 0, 3]
i=1   j=1   [2, 0, 3, 1]
i=1   j=2   [2, 3, 1, 0]
i=1   j=3   [3, 1, 0, 2]
i=1         [1, 0, 2, 3]
i=2   j=1   [1, 2, 3, 0]
i=2   j=2   [2, 3, 0, 1]
i=2   j=3   [3, 0, 1, 2]
i=2         [0, 1, 2, 3]
[0, 1, 2, 3]

If you look just at the iterations of the outer loop, you have:

[1, 2, 3, 0]
            [1, 2, 3, 0]
i=0         [1, 2, 0, 3] // 3 in proper place
i=1         [1, 0, 2, 3] // 2 in proper place
i=2         [0, 1, 2, 3] // 1 in proper place
[0, 1, 2, 3]



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