SUNY Geneseo Department of Computer Science

Problem Set 5 -- Induction and Algorithms

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Monday, February 5

Purpose

The purpose of this exercise is to improve your ability to use induction to prove things about algorithms.

Background

This exercise is based on material in section 7.1.2 of our text. This material was also covered in lecture on February 2.

Exercise

Use induction to prove each of the following...

Proof 1

Prove that the following pseudocode algorithm prints the integers from 0 up to n, given the preconditions that n is an integer and n ≥ 0:

    printUp( n )
        if n > 0
            printUp( n - 1 )
            print n
        else
            print 0

Proof 2

Prove that the following pseudocode returns 2ⁿ - 1, given the preconditions that n is an integer and n ≥ 0:

    compute( n )
        if n == 0
            return 0
        else
            return 1 + 2 * compute( n - 1 )

Follow-Up

I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office. Please bring written answers to each of the problems to the meeting.