Homework 5: Recursion, part one, due 10/13 SST

This is the nonprogramming part. This homework is based entirely on problems in your textbook.

Problem 9, page 238 [6, p. 237 in old edition]

This problem is very similar to the AnBn example in the text. Understand that first, and then modify it to solve this problem. The point is to understand how to write grammars and write code that recognizes the language.

Turn in:

  1. A grammar (this takes one or two lines). Turn it in as part of the documentation of the method below.
  2. A Java Boolean method. (No class is needed. You need not actually compile and run it, but may want to do so if you are uncertain).

Problem 15 p. 240 [12, p. 238]

The point is to understand how to do a recursive analysis of an algorithm and prove that the analysis is correct.

m(x) is simply a function that returns the number of multiplications when given a problem size x. To write the recursive definition: (1) write the base case, following the first if clause (how many multiplications are in that clause?); and (2) write the recurrence relation m(x) simply by counting the number of multiplications in the else clause, using m(x) recursively where needed.

The proof is quite easy; you simply say why the formula is true in terms of mathematical induction. (It was so easy that I thought I was missing something when I did it!)

Turn In:

  1. The definition of m(x), which will take two lines (one for the base case and one for the recursive case).
  2. A brief paragraph providing the requested proof.

Problem 18 p. 241 [15, page 238]

The point of this is to get a little more practice with mathematical induction. The formula you are proving is the well known formula for the sum of the first n numbers. There is another proof made famous by a story about Euler, who allegedly invented this formula when told by an exasperated primary school teacher to add up the first 100 numbers (the teacher was trying to keep this troublesome kid busy). He answered within a few seconds.

It's simple to prove by induction: just show the base case is true, then assume by induction that it is correct for f(n-1) and plug in that definition to derive the formula for f(n).

Turn in:

  1. A brief paragraph and lines of algebra describing your proof.

Summary

Submit all of this in one text file, named following Xiaohua's naming convention for your homework. NO ZIP is needed; use the extension .txt.

What's Next?

The programming part of this assignment will be called HW 6 and will focus on recursive problem solving b writing a creature who will find its way out of a maze!

I will also offer doubly linked lists as an extra credit (which I highly recommend).

Due October 13 SST (2:00 am 10/14)

The end.