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?
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.
- b) Derive the solution to this recurrence relation: T n = Θ(? ). Mention which methods you used to derive your solution.