Monday October 15
To sign up for a problem, send email to alubiw "at" uwaterloo.ca.
I will update this list to indicate the first person who signs up.
- [James Pearson]
(from lecture 7) Tell us about the inverse Ackermann function.
-
[Albert Tam]
(from lecture 9) Show how to do 1-dimensional range search in a binary
search tree, and analyze the worst case time for balanced binary trees.
- [Daly Chang]
(from lecture 9)
Show (by example) that a 2-dimensional range query in a kd tree
can take Omega(sqrt(n) + k) time.
- [Simina Branzei]
(based on lecture 11)
Give an 8 minute version of the deterministic linear time selection
algorithm (section 9.3 in CLRS).
- [Taylor Gordon]
(from lecture 12) Tell us about the polynomial time primality test. Who
discovered it? (Remember that you only have 8 minutes! -- You can spend most
of this time on non-technical stuff.)