2023年11月25日

算法代写 | 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.