Data Structures – 390 Assignment #7
Due: Wednesday November 29
Proof by Induction
- Become familiar with rigorous mathematical proof and in particular with induction
- Assume that you have a sorted array of n elements. Prove that a binary search of an array of n elements is less or equal than log n
- Prove by induction that the sum 20+21+22+23+...+2h is equal to 2h+1-1
- The recursive solution of the Towers of Hanoi problem which starts with n disks on peg A, requires than n-1 pegs are moved to peg B, then the last remaining on A is moved to peg C and then the n-1 disks from B are moved to C. Thus the number of steps S(n) for the n pegs is S(n) = 2S(n-1) +1. Prove by induction that S(n)=2n-1.
- Prove that the above recursive solution for the Towers of Hanoi problem is optimal in the sense that any other algorithm cannot do better than S(n).