SUNY Geneseo Department of Computer Science

Problem Set 6 -- More Induction and Algorithms

CSci 240, Spring 2007

Prof. Doug Baldwin

Due Wednesday, February 7

Purpose

The purpose of this exercise is to further develop your ability to use induction to prove things about recursive algorithms. The exercise does this by asking you to construct some proofs about algorithms in which there are more complicated patterns of recursion than in the first "Induction and Algorithms" problem set.

Background

These problems draw on material in section 7.1 of our textbook. This material was also covered in the February 5 lecture.

Exercise

Solve each of the following problems.

Problem 1

Exercise 7.9 on page 224 of our textbook.

Problem 2

Consider the following algorithm, which operates on the first n characters of string s.

    String amplify( String s, int n )
        if n <= 1
            return s[0] + s[0]
        else
            return amplify( s, n-1 ) + amplify( s, n-1 )

In this algorithm, indexing a string extracts a character from it. Characters are indexed from 0 through 1 less than the length of the string. Thus, for example, the expression s[0] in the algorithm extracts the first character of the string. The + operator applied to characters and strings is concatenation.

Part A

Prove that this algorithm returns a string of length 2ⁿ.

Part B

The string that this algorithm returns consists of a large number of copies of a single character from the original string. Which character is that? Prove your answer.

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.