recursion-algorithm代写  – 递归算法代写 – algorithm代写
recursion-algorithm代写

recursion-algorithm代写 – 递归算法代写 – algorithm代写

Assignment

 

 

recursion-algorithm代写 .a) Suppose a finite deck of numeric cards 1, 2, 3, … have been shuffled randomly. Repeat the following step: If the top card is ···

 

1.Loop termination may be non-trivial: Recursion algorithm代写

2.a) Suppose a finite deck of numeric cards 1, 2, 3, … have been shuffled randomly. Repeat the following step: If the top card is numbered 1, the game terminates. But if it is any number n > 1, then reverse the ordering of the top n cards on the deck and iterate. Example: 42153 ®51243 ®34215 ® 24315 ® 42315 ® Is this game guaranteed to eventually terminate? Prove your answer.

3.b) Collatz Conjecture [1973]: Does the loop below terminate on every input?

recursion-algorithm代写
recursion-algorithm代写

4.Are any of the following implications always true? recursion-algorithm代写

Prove or give a counter-example. a) f(n) = Θ(g(n)) Þf(n) = cg(n) + o(g(n)), for some real constant c > 0. b) f(n) = Θ(g(n)) Þf(n) = cg(n) + O(g(n)), for some real constant c > 0.

5.For each pseudo-code below derive the simplified asymptotic running time in Q(?) notation.

6.Derive the most simplified answers to the following summations. Mention which methods you used to derive your solution.

7.Recursion Time Analysis:  recursion-algorithm代写

A certain recursive algorithm takes an input list of n elements. Divides the list into n sub-lists, each with n elements. Recursively solves each of these n smaller subinstances. Then spends an additional Θ(n) time to combine the solutions of these subinstances to obtain the solution of the main instance.

As a base case, if the size of the input list is at most a specified positive constant, then the algorithm solves such a small instance directly in Θ(1) time. a) Express the recurrence relation that governs T n , the time complexity of this algorithm.

  1. b) Derive the solution to this recurrence relation: T n = Θ(? ). Mention which methods you used to derive your solution.

 

更多其他:代写作业 数学代写 物理代写 生物学代写 程序编程代写 Python程序代写

合作平台:天才代写 幽灵代  写手招聘  paper代写

发表回复