For the below problems from section 2.1, you must write your
algorithms in well-formed pseudocode using the syntax described in
Appendix 2, pages A-5 through A-10.
- §2.1, Ex. 2 - Identify missing characteristics of algorithms.
- §2.1, Ex. 6 - Write an algorithm to reorder a triple.
- §2.1, Ex. 10 - Write an algorithm to find the minimum of a list.
- §2.1, Ex. 14 - Write an algorithm to find min and max simultaneously.
- §2.1, Ex. 16 - Write an alg. to find the longest word in a sentence. (Assume the input is a sequence of characters a1, ..., an, each of which is a letter or a blank.)
- §2.1, Ex. 20 - Improve the binary search alg. on p. 104.
- §2.2, Ex. 12 - Identify the best-case (as opposed to worst-case) time complexity of some algorithms.
- §2.2, Ex. 14 - Optimality of algorithms.
- §2.2, Ex. 20 - Find time complexity of an alg. for sec. 2.1 ex. 26. (As part of this, you should give the algorithm.)
For the below problems from sections 3.1 and 3.2, your proofs
must be good, clear, well-written proofs, as according to the
guidelines in the handout "How to Write Good Proofs".
- §3.1, Ex. 20 - Prove sum of rationals is rational.
- §3.1, Ex. 26 - Prove or disprove that 2n+1 is always prime.
- §3.1, Ex. 30 - Proof by cases involving squares and remainders.
- §3.1, Ex. 32 - Proof by cases involving floor and ceiling.
- §3.1, Ex. 36 - Proof about squares and negatives.
- §3.1, Ex. 42 - Proof about primes.
For the below problems, you must use the correct structure for
an inductive proof (see examples in text), and you must make
use of your inductive assumption!
- §3.2, Ex. 2 - A simple induction to prove a summation.
- §3.2, Ex. 4 - Induction to prove a summation.
- §3.2, Ex. 12 - Induction to prove an inequality.
- §3.2, Ex. 14 - Induction to prove an inequality.
- §3.2, Ex. 22 - Induction to prove 6 divides n cubed minus n.
- §3.2, Ex. 32 - Induction for a proof about coins.