91Ó°ÊÓ

Goldbach's conjecture states that every even number greater than 2 is the sum of two prime numbers. Here is a proposed algorithm that checks whether Goldbach's conjecture is true: 1\. Let \(n=4\). 2\. If \(n\) is not the sum of two primes, output "no" and stop. 3\. Else increase \(n\) by 2 and continue with step 2 . 4\. Output "yes" and stop. Which properties of an algorithm-input, output, precision, determinism, finiteness, correctness, generality - does this proposed algorithm have? Do any of them depend on the truth of Goldbach's conjecture (which mathematicians have not yet settled)?

Write an algorithm that finds the second-smallest element among \(a, b,\) and \(c .\) Assume that the values of \(a, b,\) and \(c\) are distinct

(a) Use the formulas $$s_{1}=2, \quad s_{n}=s_{n-1}+2 n \quad \text { for all } n \geq 2$$ to write a recursive algorithm that computes $$s_{n}=2+4+6+\cdots+2 n$$ (b) Give a proof using mathematical induction that your algorithm for part (a) is correct.

Write a recursive algorithm to find the minimum of a finite sequence of numbers. Give a proof using mathematical induction that your algorithm is correct.

Write a recursive algorithm to find the maximum of a finite sequence of numbers. Give a proof using mathematical induction that your algorithm is correct.

A robot can take steps of 1 meter or 2 meters. Write an algorithm to list all of the ways the robot can walk \(n\) meters.

A robot can take steps of 1 meter, 2 meters, or 3 meters. Write an algorithm to list all of the ways the robot can walk \(n\) meters.

Concern the Fibonacci sequence \(\left\\{f_{n}\right\\}\). Show that the number of ways to tile a \(2 \times n\) board with \(1 \times 2\) rectangular pieces is \(f_{n+1},\) the \((n+1)\) st Fibonacci number.

Select a theta notation from among $$ \begin{array}{l} \Theta(1), \quad \Theta(\lg n), \quad \Theta(n), \quad \Theta(n \lg n) \\\ \Theta\left(n^{2}\right), \quad \Theta\left(n^{3}\right), \quad \Theta\left(2^{n}\right), \quad \text { or } \Theta(n !) \end{array} $$ for the number of times the statement \(x=x+1\) is executed. $$ \begin{array}{c} \text { for } i=1 \text { to } n \\ \text { for } j=1 \text { to } n \\\ \text { for } k=1 \text { to } i \\ x=x+1 \end{array} $$

Concern the Fibonacci sequence \(\left\\{f_{n}\right\\}\). Use mathematical induction to show that for all \(n \geq 1, f_{n}\) is even if and only if \(n\) is divisible by \(3 .\)