Discrete Structures
HW #11
Last Update: 10 April 2009
Note:
or
material is highlighted

Reminder: Each HW problem solution should consist of:
 a restatement of the entire problem (you may copy it word for word),
 followed by a complete solution with all intermediate steps shown.
REMINDER: NAME, DATE, RECITATION SECTION AT TOP RIGHT OF
EACH PAGE;

STAPLE MULTIPLE PAGES

All exercises are from §4.3 (recursive definitions and structural
induction).
 (3 points)
p. 308: 4d
 This gives you a recursivelydefined function and asks you
to compute some of its values.
 (9 points)
p. 308: 8d
 This gives you an "explicit" formula for the nth term of a
sequence and asks you to find a recursive definition of it.
 Hint: Create a 2column table, with one column
for n and one column for a_{n}.
Then look for a pattern that defines a_{n}
as a function of a_{n–1}.
 3 points for table;
3 points for base case of
definition;
3 points for recursive case of definition
 (6 points)
Give a recursive definition of the set of even negative integers.
 3 points for base case;
3 points for recursive case.
 (6 points)
Give a recursive definition of the set of positive integer powers of 2.
 3 points for base case;
3 points for recursive case.
 (15 points)
p. 309: 26a, c
 This problem defines a set recursively.
 Part (a) asks you to list some of its elements (3 points)
 Part (c) asks you to use structural induction to prove
a proposition about the set:
3 points each for stating and proving the base case;
3 points
each for stating and proving the recursive
case;
total = 12 points.
For problems 6, 7, and 8,
first read the paragraph about
Ackermann
functions—which play an important role in the the theory of computation—on
p. 310, beginning in the left column after problem #47 and ending
in the right column just before problem #48.
(You might also want to read the articles about it that you can access
by linking to "Ackermann" and "function", above.)
 (12 points)
p. 310: 48a–d
 Problems 48a–d ask you to compute a few values of an
Ackermann
function.
 3 points each
 (12 points)
p. 310: 50
 This asks you to prove (using mathematical induction, of course!) an interesting
theorem about the Ackermann function from problem #48.
 3 points each for stating and for proving the base case;
3 points each for stating and for proving the recursive
case
 (Required Extra Credit Problem!)
p. 310: 52
 This is a deceptively simple problem:
You're merely
asked to compute the value of A(3,4) for the Ackermann
function from the 2 previous problems.
It is simple to do, but may take you a while.
 If you get it right, with all the steps spelled out,
I'll give you 12 points of extra credit.
 If you stop, or
get lost, in the middle of the computation
and explain why you stopped computing the value, you will
neither get nor lose any extra points.
 BUT YOU MUST ATTEMPT THIS PROBLEM; otherwise, I
will deduct 12 points from your total!
(I really
want
you to get a feel for why Ackermann functions are weird.)
 Hint: You might want to try #51a and especially
#51b first and then check your answer in the back of the book.
Grand total = 63 points.
Tentative grading scheme:
A 61  63
A 57  60
B+ 54  56
B 50  53
B 47  49
C+ 43  46
C 36  42
C 29  35
D+ 22  28
D 12  21
F 0  11
DUE: AT THE BEGINNING OF LECTURE, FRIDAY, APRIL 17 
Copyright © 2009 by
William J. Rapaport
(rapaport@cse.buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/S09/hw11.html20090406