1. Prove that the classic recursive algorithm for the Tower of Hanoi puzzle (Section 2.4) makes the minimum number of disk moves needed to solve the problem.
2. Find a trivial lower-bound class for each of the following problems and indicate, if you can, whether this bound is tight.
a. finding the largest element in an array
b. checking completeness of a graph represented by its adjacency matrix
c. generating all the subsets of an n-element set d. determining whether n given real numbers are all distinct