2023年11月25日

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 different 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 different hashing approaches?
 Prove the upper bounds on the expected execution times (assuming random hash
functions) for the different hashing approaches discussed in the lecture.
 What does it mean that a class of hash functions is called c-universal?