C++代写：CS347 Algorithm

代写四个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

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.