home—info—lectures—hws—exams
hw10
Reading about counting
extra credit: structural induction
Note:
Usually, this homework would mostly involve problems from last weeks
lecture (strong induction, structural induction),
plus a few reading problems.
This week has no (non-extra-credit) problem froms last week's lecture.
The reason is that although it's an important concept,
the other 122 section isn't covering that material,
and I want to keep the homeworks roughly equivalent between sections.
-
Extra credit --
(you can do this problem to replace hw09 #4 (induction),
if you now realize you didn't nail it):
Look at
hw09 #6
and (for any of a,b,c) prove the conjecture.
-
Extra credit for self-learners:
Conjecture a closed-form formula for
hw09 #6d,
and prove your conjecture correct using induction.
The section on Recurrence Relations shows how to find such a
closed-form
1
solution.
We won't be covering that material this semester.
-
Extra Credit:
For class Tree
in class,
-
write and test the method boolean contains(String target).
-
write and test the method boolean countOccurrences(String target).
-
Modify the above code so that it one of these two methods is
only (and entirely) defined in the abstract class.
-
Extra Credit:
write and test a recursive method append for
SList.
(Hint:
the code is extremely short, both for EmptyTree
and for Branch.
Right down the recursive call, and then think about how to use that
result to constructor your overall result.
You might find it helpful to write out a test case,
and the result of the recursive call on the test case.)
-
Extra Credit, continuing from previous:
Use structural induction to prove that for any SLists a,b,c,
(a.append(b)).append(c) is the same list as
a.append( b.append(c) )2.
As in
the structural
induction from lecture,
you'll start with a statement P(sl).
Then you'll have two main branches:
-
show that P(el) holds,
where et is any EmptyList,
and
-
show that P(c) holds,
where c is any Cons;
your inductive hypothesis is
P(c.rest).
(As in the notes and Rosen,
write out what this statement is,
before showing that
P(c.rest) → P(c).)
-
Reading:
-
(5ed §4.1) The Basics of Counting
-
(5ed §4.2) The Pigeonhole Principle
-
(5ed §4.3) Permutations and Combinations (through permutations,
and perhaps just glance at combinations).
-
(5ed, p.310 #12) variant:
- How many bit strings are there of length exactly five?
- Of length exactly six?
- Of length six or less?
-
Of length n or less?
(Give a closed-form solution
3
— no “...” or “Σ”.)
(Whether or not you were aware of it, the first two questions
involve the product rule;
the third involves the summation rule.
The last is just applying our summation of powers-of-two.)
- (5ed p.310 #14) variant:
How many bit strings are there of length n or less
which both start and end with a "1"?
(Hint: Your answer should include an if or case
statement, to handle the base case(s) correctly.)
-
(5ed p.319 #4)
A bowl contains ten red balls and ten blue balls.
A woman selects balls at random without looking at them.
- how many balls must she select to be sure of having at least
three balls of the same color?
- how many balls must she select to be sure of having at least
three blue balls?
-
(5ed p.325 #10)
There are six different candidates for governer of a state.
In how many different orders can the names of the candidates be arranged
on the ballot?
-
There are 10 students in my class, but only three seats;
that's not actually a problem since on any given day only three students
show up (never more, never less).
-
How many times might class meet before I see the exact same students
sitting in the exact same seats?
-
How many days different days might just
Alfred, Beatrix, and Chloe
be the three showing up, without having to repeat a seating arrangement?
1Closed form:
an expression (program)
with no loops, recursion (nor “...” of course).
if-then statements are fine.
↩
2
Object-oriented notation is obscuring the fact that we're saying
“show append is commutative”, that is
a++(b++c) = (a++b)++c, where “++” stands for
“append”.
↩
3Closed form:
an expression (program)
with no loops, recursion (nor “...” of course).
if-then statements are fine.
↩
home—info—lectures—hws—exams