Announcements

• Exam 3: next Thursday! Bring one page of notes.
• Project 4: will be assigned next Monday, due Monday, May 11
  • Problem Set involving questions about Big Oh / running time.
• Final Exam May 7 (12 - 2:30 PM)

Recursion

There are several options; most involve divide-and-conquer algorithms. Divide-and-conquer means we split the list into smaller parts, and (recursively) sort these smaller lists. There are several ways to do this, we will describe one: the merge sort algorithm.

Merge sort

1. Split the list in half.
2. (Recursively) merge sort each half.
3. Merge the two halves to produce one, sorted list.

Pseudocode?

• Just focus on the merge part.
• Pseudocode for merging two sorted halves?
• Running time?

Exercise

Implement the merge algorithm. Recall: given an array, sorted from \([start, mid)\) and \([mid, end)\):

• Put them in order in \(tmp\) (from start to end).
• Then copy back from \(tmp\) to \(array\).

public void merge(int[] array, int[] tmp, int start, int mid, int end)

Testing

Starter code Make sure your method works by testing the code with the testMerge method.

Exercise

On paper: write pseudocode for the merge sort algorithm. (No need to re-write the merge method.)

Exercise

Implement the mergesort algorithm. Then make sure your method works by testing the code with the testSort method.

Example

\(n = 8\):

• How many steps spent merging at each “level”?
• How many “levels”?
• Running time?

Details

• \(T(8) = 2T(4) + 8\)
• \(= 2(2T(2) + 4) + 8\)
• \(= 4T(2) + 8 + 8\)
• \(= 4(2T(1) + 2) + 8 + 8\)
• \(= 8T(1) + 8 + 8 + 8\)
• \(= 8T(1) + 3 \times 8\).

Notice: \(T(1)\) (the base case) is \(O(1)\), and if \(n = 8\), then \(3 = \log_2{8}\).

Code

• In the code, let’s see if we can add a way to “count” the amount of merging that is done.
• Each call to merge should take roughly (end - start) steps.

In general

• In general, if \(N = 2^k\):
• \(k\) “levels” of splitting
• Each “level” does \(N\) steps of merging in total.
• \(k \times N\) steps total!
• \(k = \log_2(N)\), so…
• \(O(N \log(N))\) steps total.

Whose turn?

Pseudocode for the game:

currentPlayer = two;
while (game is not over) {
  print "Player ???, what do you want to raise the bid to?"
  currentBid = currentPlayer.raise(currentBid);
  if (currentPlayer == one) {
    currentPlayer = two;
  } else {
    currentPlayer = one;
  }
}

Solution: Modular design

public String playerName(Player current)

• If current == one, return “Player One”, otherwise return “Player Two”
• play method: print(playerName(currentPlayer) + ": what do you want to raise the bid to?");
• Or could be a method in the Player interface.

Determine winner

After loop:

• Determine winner: who made the last bid?
• Is it the currentPlayer?
  • Depends on when you do the “swap turn” part.
• Test out your game. See if it gives the correct answer.

Linked List

• Data organized into nodes.
• Each node has a data item and a link to the next node.
• Last node links to null.