CS代考 | COMP SCI 2201 & 7201 Algorithm and Data Structure Analysis

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?

E-mail: itcsdx@outlook.com  微信:itcsdx