CSC263 Summer 2022 Worksheet 1
Algorithm代写 | 代写mining | 代做assignment – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 是比较典型的Algorithm/mining等代写方向, 这个项目是assignment代写的代写题目
May 18, 2022
Binary trees
Consider some arbitrary binary treeT. A nodexis anancestorof a nodeyinTif and only ifxis on the path fromytoT.root. (Note: every node is an ancestor of itself.) Ifx, yare nodes in the treeT, then thelowest common ancestorofxandyis the unique nodewinTsuch that
1.wis an ancestor of bothxandy, and
- there isnonodez 6 =winTsuch thatwis an ancestor ofzandzis an ancestor of bothxandy.
For all three of the following exercises, assume that every node in a tree has aleftpointer, arightpointer, and aparentpointer.
Ex. 1 LetTbe a nonempty binary search tree of heighthcontainingnnodes with distinct keys. Given the keyskx, kyof a pair of nodesx, yinT, write an Algorithm that finds the lowest common ancestor ofxandyinTwith worst-case runtime complexity (h).
Answer (Ex. 1) Beginning withw=T.root, check ifmin(kx, ky)wmax(kx, ky). If true, then returnw. Otherwise, ifmax(kx, ky)< w, then setw=w.lef tand repeat. If w <min(kx, ky), then setw=w.rightand repeat.
Ex. 2 LetTbe an arbitrary nonempty binary tree of heighthcontainingnnodes with distinct keys. Givenpointersto a pair of nodesx, yinT, write an algorithm that finds the lowest common ancestor ofxandyinTwith worst-case runtime complexity (h).
Answer (Ex. 2) Usingparentpointers, trace a path fromxtoT.rootand fromyto T.root. Store these paths in two arrays. Return the first node of the longest common suffix of these two paths.
Ex. 3 Given a pointer to the root of a binary treeTthat containsnnodes with distinct keys, write an algorithm that checks whetherT is a binary search tree with worst-case runtime complexity (n).
Answer (Ex. 3) Thecheck(root)algorithm below solves the given task. def check(root): return check_helper(root, -math.inf, math.inf)
def check_helper(root, l, h): if root is None: return True elif root.key >= h or root.key <= l: return False return check_helper(root.left, l, root.key) and check_helper(root.right, root.key, h)
1
Average case analysis
Consider the following algorithm for finding the maximum element in a given arrayarr.
1 def find_max(arr): 2 curr_max = -math.inf 3 for i in range(len(arr)): 4 if arr[i] > curr_max: 5 curr_max = arr[i] 6 return curr_max
Ex. 4 Assume that the arrayarris a permutation of{ 1 ,... , n}selected uniformly at
random. On average, how many times is thecurrmaxvariable assigned on line 5?
Answer (Ex. 4) LetTbe a random variable representing the number of times line 5
is executed. Notice that deter mining the probability of doingjassignments or a formula
for the number of assignments performed for any particular input is difficult.
Instead, letT 1 ,... , Tnbe random variables that indicate whether or notcurrmaxis assigned
during any particular iteration of the loop. That is,Tj = 1 if line 5 is executed during
iterationjof the loop, andTj= 0 otherwise. ThenT=
n
j=1Tj. Hence,
E[T] =E
[n
j=
Tj
]
=
n
j=
E[Tj] (linearity of expectation)
=
n
j=
P r[Tj= 1].
The last equality holds because a single assignment is performed during iterationjif and
only ifTj= 1. Notice thatP r[Tj= 1] is equal to the probability thatarr[j-1]is greater
thanarr[0], ..., arr[j-2]. Since each permutation is equally likely, this is simply equal
to^1 j. For example,P r[T 1 = 1] =^11 = 1, which means that line 5 is always executed in the
first iteration of the loop. We have
n
j=
P r[Tj= 1] =
n
j=
1
j
=Hn then-th harmonic number
= (logn)