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?


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

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


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论