COMP 250 - winter 2007

Solutions

January 19	Solutions to Assignment 1	Player.java, PokerTable.java, Tournament.java (Card.java and Deck.java were not modified)
February 7	Solutions to Assignment 2	RecursiveMax.java, CosTaylorSeries.java
February 20	Solutions to Assignment 3	Helper.java, Stack.java, Queue.java (Node.java, Customer.java, and EmptyStackException.java were not modified)
March 9	Solutions to Assignment 4	BST.java (Queue.java, BinTreeNode.java, Node.java, and EmptyStackException.java were not modified)

Corrections to Solutions

solutions to assignment 5
- There is an error in the solution to question 4f. The B_3 tree is not in maximum heap ordering.
midterm solutions
- There is an error in the derivation of the solution to question 4b. The solution should read:
  t(n) = n + 3t(n/3)
  = n + 3[n/3 + 3t(n/3²)]
  = n + 3[n/3 + 3[n/3² + 3t(n/3³)]]
  = n + 3[n/3 + 3[n/3² + 3[n/3³ + 3t(n/3⁴)]]]
  = 4n + 3⁴t(n/3⁴)
  = kn + 3^kt(n/3^k)
  [...]
  = n log₃n + 3^log₃nt(n/3^log₃n)
  = n log₃n + n t(1)
  = n log₃n + n
  (which is O(n log n))