Lesson 1

• Ordered hashing was discussed. For 5 credit course, copies on ordered hashing distributed.
• Exercise 1.2-2 discussed. (Much easier if you have a calculator! :-)
• Exercise 3.1-1 discussed, and I probably had a black-board blindness or something. A simple way to show the lower bound is that

  f(n)+g(n) < max(f(n),g(n)) + max(f(n),g(n))
  

  which gives

  c(f(n)+g(n)) < max(f(n),g(n))
  

  for c less than a half.
• 4.2-1 was solved.

• 4.3-1
• 5.2-5