算法代写 | Data Structure And Algorithm

本次加拿大代写主要为数据结构与算法相关的assignment

Problem 1 [4+4+4=12 marks]

a) Consider the Interpolation search on a sorted array A[0,..,n!1] that stores real num-
bers. Suppose that A[i]= ai + b for all i 2 {0,…,n ! 1},where a and b are real
numbers and a> 0. For example if A = {5, 7, 9, 11, 13, 15} then a =2and b =5.
Prove that the interpolation search on A always takes O(1) (no matter if the search is
successful or unsuccessful).

b) Recall that the worst-case search time for interpolation search is ⇥(n). Give an example
of an array A with n distinct values (i.e., by defining A[i]= f(i)forsomefunction f)
as well as a search key k that demonstrates the worst-case time; you need to justify the
runtime. There are infinitely many such examples, but any one of them will su”ce.

c) Suppose A[i]= t
pi for all i 2 {0,…,n ! 1} and some positive number t.Showthat
the runtime to search for t using interpolation search is O(log log n).
Problem 2 [2+2+2+2+3+3=14 marks]

a) Draw the standard trie that is obtained after inserting the following keys into an
initially empty trie:
1001$, 001$, 1111$, 10110$, 10$, 11$, 10100$, 1$, 000$, 101$, 00$

b) From your answer to part (a), draw the trie that is obtained after removing the following
keys:
10100$, 11$, 1001$

c) Repeat part (a), except use a compressed trie.

d) Repeat part (b), but on the compressed tree that is obtained in (c).

e) Find the exact height of the trie with keys that are binary representations of numbers
0, 1, 2, 3, 4,…, 2k ! 1withoutunnecessaryleading0s,andinsertedintothetriein
increasing order. That is, insert 0$, 1$, 10$, 11$, 100$, etc.

f) Repeat part (e) using compressed tries. Also, for this part, prove your result, including
any structural properties of the compressed tries.
Note:Incaseyoudecidedtousemathematicalinduction,solutionsmustclearlystate:
what you are doing induction on;
the base case(s);
the inductive hypothesis;
the inductive step.


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


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

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


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

blank

发表评论