Exercise 1 Integer Multiplication
1. Describe the recursive school multiplication algorithm for multiplying two n-digit
numbers. Develop the recursive formula for the number of primitive operations.
2. Describe the Karatsuba multiplication algorithm for multiplying two n-digit num-
bers. Develop the recursive formula for the number of primitive operations. Why is
the Karatsuba multiplication asymptotically faster than the school multiplication?
Exercise 2 Master Theorem
Revisit the master theorem and its proof.
Consider example recursive formulas and apply the master theorem to obtain a
tight asymptotic bound.
Exercise 3 Invariants
What are invariants, pre-conditions, and post-conditions?
How do you use them to show that a program is correct?
Show the correctness of an example program from the course using invariants.
Exercise 4 Skip Lists
Describe the basic properties of a Skip List.
What is the probability that the Skip Lists exceeds a certain height h after the
insertion of n elements?
Show by example how nd, insertion, and deleting works for Skip Lists.
Exercise 5 Hashing
Describe the diﬀerent hashing mechanisms given in the lecture and compare them.
Consider an example where hashing has to deal with collisions. How are collisions
resolved by the diﬀerent hashing approaches?
Prove the upper bounds on the expected execution times (assuming random hash
functions) for the diﬀerent hashing approaches discussed in the lecture.
What does it mean that a class of hash functions is called c-universal?
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx