Homework 3, CSC 517

Problem 1

Prove that a complete binary tree of depth i has 2i+1-1 nodes. Prove this by induction.
Hint: A complete binary tree of depth i is made up of two complete binary trees of depth i-1 and one additional node that connects them together.

Problem 2

Express n3 as a falling power. That is, find a, b and c such that, 
    n3 = n(3) + a n(2) + b n + c

Problem 3

Use falling powers to sum, 
    &Sigma0≤i≤n i3
Hint: Use the previous result.

Problem 4

Prove that, 
   Σ h/2h = 2
Hint: This proof was given in class.

Problem 5

Inspired by the proof in class, sum the series, 
   Σ h(2)/2h

Definition:

Recall that in class we gave the definition of the falling power: 
    n(2) = n(n-1)
    n(3) = n(n-1)(n-2)

Problem 6

Write pseudo code for selection sort. Develop the code using the method of loop invariants. The loop invariant is: 
     The i smallest elements of the array are now in
     locations a[0], ..., a[i-1] in sorted order
You should have a loop which begins asserting the loop invariatn true for i=0. Each time through the loop make i larger.

Show where the loop invariant is asserted and argue why the loop invariant is true when asserted. Argue why the loop must terminate and why on termination the loop invariant implies the entire array is properly sorted.

People taking the practicum: program your algorithm.

Problem 7

Write pseudo code for insertions sort. Develop the code using the method of loop invariants. The loop invariant is: 
    The first i elements of the array are now sorted order.

Show where the loop invariant is asserted and argue why the loop invariant is true when asserted. Argue why the loop must terminate and why on termination the loop invariant implies the entire array is properly sorted.

People taking the practicum: program your algorithm.