RU beehive logo ITEC dept promo banner
ITEC 122
2007fall
ibarland

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.

  1. 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.
  2. 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.
  3. Extra Credit: For class Tree in class,
    1. write and test the method boolean contains(String target).
    2. write and test the method boolean countOccurrences(String target).
    3. Modify the above code so that it one of these two methods is only (and entirely) defined in the abstract class.
  4. 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.)

  5. 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:

    1. show that P(el) holds, where et is any EmptyList,
      2. and
    2. 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).)

  6. Reading:
  7. (5ed, p.310 #12) variant:
    1. How many bit strings are there of length exactly five?
    2. Of length exactly six?
    3. Of length six or less?
    4. 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.)
  8. (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.)
  9. (5ed p.319 #4) A bowl contains ten red balls and ten blue balls. A woman selects balls at random without looking at them.
    1. how many balls must she select to be sure of having at least three balls of the same color?
    2. how many balls must she select to be sure of having at least three blue balls?
  10. (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?
  11. 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).
    1. How many times might class meet before I see the exact same students sitting in the exact same seats?
    2. 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

©2007, Ian Barland, Radford University
Last modified 2007.Nov.03 (Sat)		 Please mail any suggestions
(incl. typos, broken links)
to iba�rlandrad�ford.edu		 Powered by PLT Scheme