英国代写code范文精选:“C++算法小程序”,这篇论文主要介绍了与CS347有关的算法小程序。文章编写了四个C++算法小程序,并写出了规定的时间复杂度算法。
Fibonacci numbers The Fibonacci numbers are defined by the following recurrence: F(0) = 0 F(1) = 1, and F(i) = F(i−1) + F(i−2) for i ≥ 2. (a) Consider the following algorithm for computing the nth Fibonacci number. Algorithm 1 Fibonacci 1 2 3 4 5 6 procedure Fibonacci(n) if n = 0 then return 0 if n = 1 then return 1 return Fibonacci(n − 1) + Fibonacci(n − 2) Derive a recurrence for Fibonacci(n) and determine the time taken by Fibonacci(n) in terms of the input n, expressed in Θ()-notation. (b) Prove that for any n ≥ 2, F(n) equals A, where A is the nth power of the following matrix. (c) Use part (b) to obtain an algorithm that computes F n in O(log n) time. Selection from two sorted lists Design an O(log n) time algorithm to select the median from a set of 2n keys given in the form of two sorted lists, each of length n. For convenience, you may assume that all of the keys are all distinct. Briefly justify the correctness of the algorithm. Analyze its running time. A fault-tolerant OR-gate Assume we are given an infinite supply of two-input, one-output gates, most of which are OR gates and some of which are AND gates. Unfortunately the OR and AND gates have been mixed together and we can’t tell them apart. For a given integer k ≥ 0, we would like to construct a two-input, one-output combinational “k-OR” circuit from our supply of two-input, one output gates such that the following property holds: If at most k of the gates are AND gates then the circuit correctly implements OR. Assume for simplicity that k is a power of two. For a given integer k ≥ 0, we would like to design a k-OR circuit that uses the smallest number of gates. (a) Design a 1-OR circuit with the smallest number of gates. Argue the correctness of your circuit. (b) Using a 1-OR circuit as a black box, design a 2-OR circuit. Argue the correctness of your circuit. (c) Generalizing the above approach, or using a different approach, design the best possible k-OR circuit you can and derive a Θ-bound (in terms of the parameter k) for the number of gates in your k-OR circuit. Argue the correctness of your circuit. Reconstructing a total order A group of n runners finished a close race. Unfortunately, the officials at the finish line were unable to note down the order in which the racers finished. Each runner, however, noted the jersey number of the runner finishing immediately ahead of her or him. (There were no ties.) The race officials ask each runner to give an ordered pair, containing two pieces of information: (i) first, his or her own jersey number and (ii) second, the jersey number of the runner who finished immediately ahead of him or her. The winner of the race, who did not see anybody finish ahead of her, did not turn any information in. You have been asked to design an algorithm that takes as input the n − 1 pairs and returns the order in which the runners finished the race. Assume each runner is honest. (a) Give a deterministic O(n log n) time algorithm. (b) Give a randomized algorithm with expected running time O(n). You need not prove the correctness of your algorithms. In each case, analyze the running time of your algorithm. 51Due作为专业的留学教育辅导机构,专业辅导语言学论文代写、硕士paper代写、英国matlab作业代写,自2004年至今,坚持以学生为中心,全天候服务,为海外留学生完成了数万篇assignment代写、essay代写、report代写、dissertation代写等论文,以优质的英国代写服务赢得留学生的信赖,如有英国代写code需求或者英国it课程补习需求,欢迎咨询51Due哦。
0 Comments
Leave a Reply. |
Author51Due是一家以海外中国留学生创业团队为主导,总部设在美国纽约的留学教育咨询机构,同时也是海外拥有强大综合教员实力的论文代写机构。主要业务包括海外课业咨询,提供Essay代写与辅导,Paper代写与辅导,Report代写与辅导,Assignment代写与辅导,论文代写,论文修改,计算机编程代写,同时涵盖了Personal Statement代写等留学文书以及转学申请文书的代写,海外求学咨询与新留学生辅导等各个留学环节的专业咨询。 ArchivesCategories
全部
|