算法代写 | Assignment 1 COSC 3P03 Algorithms

本次加拿大代写是算法相关的一个assignment

1. (7) What is the Big Oh function for each of the following functions of n. It should be as tight and as simple
as possible. For example, if t(n) = 3.5n log3n5 + log log n + 100√n, the answer should be n log3n.

All log functions are base 2. And if you use log functions in your answers, they should be base 2 as well.
There is no need to justify your answers.

2. (13) Indicate, for each pair of expressions (A,B) in the table below, whether A is O, o, Ω, or Θ of B. See
example answers for A = 2n and B = 2n+1. Assume that k > 1 and c > 1 are constants. Your answer should
be in the form of the table with ”yes” or ”no” written in each box. Also, please list all the functions in Column
A from the lowest to the highest asymptotically.

blank

3. (15) Consider the following recursive algorithm C(i, j, x) that checks whether the array segment A[i..j] contains
key x, where i ≤ j. It return YES if x is found and NO otherwise (note that floor(x) is the floor function that
returns the largest integer that is less than or equal to x):

else
return NO
else
if C(i, floor((i+j)/2), x) = YES
return YES
else
return C(floor((i+j)/2) + 1, j, x)
if i=j then
if A[i] = x
return YES

Let t(n) be the worst case time for C(1, n, x) and assume that n is a power of 2. (a) Give a recurrence for
t(n). Don’t forget the initial condition; and (b) solve t(n) using the following methods: iteration, recursion
tree, and the masters method. No credit will be given if your recurrence is incorrect.C(i, j, x)


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


blank

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

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


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

blank

发表评论