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.

(5ed p.270 #8): Give a recursive definition of {a} (n∈N), if an = 4n-2. an = 1 + (-1) an = n·(n-1) an = n 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 Closed form: an expression (program) with no loops, recursion (nor ... of course). if-then statements are fine. 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.) a.append( b.append(c) ) vs (a.append(b)).append(c) ======= /// SHORTHAND: "a0" means "a.first", and "a*" means "a.rest". a.append( b.append(c) ) = (Cons(a0,a*)).append( b.append(c) ) // By = Cons( a0, a*.append(b.append(c)) ) // By def'n of code. = Cons( a0, (a*.append(b)).append(c) ) // By Ind. hyp. (a.append(b)).append(c) = ((Cons(a0,a*)).append(b)).append(c) = (Cons(a0,a*.append(b))).append(c) = (Cons(a0,x)).append(c) // let x = a*.append(b), to clear our heads. = Cons(a0, x.append(c)) // by def'n of code = Cons(a0, (a*.append(b)).append(c)) // by def'n of code append(List z) { List rr = (this.rest()).append(z); // rr: resultOfRecursion return new Cons( this.first(), rr ); }

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) ) 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. .

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 Closed form: an expression (program) with no loops, recursion (nor ... of course). if-then statements are fine. — 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?

First, look at some sites like tinyurl.com or snurl.com which take long URLs and create new short names for them. You might wonder how quickly such sites will run out of short names.

How many different characters are used in the shortened-URLs (the part after the domain name (and the following slash))? How many shortened-URLs have exactly 6 characters? (again, counting only the part after the domain name and the following slash)

If there are 1010 static web pages, and every single one of them were registered on such a site, how long would be the longest small URL be? (Just count the encoded part of the name, without the initial ``http://www.snurl.com/'' prefix.)

We might then start to wonder, is 1010 a reasonable upper estimate on the number of web pages? After all, one of the best use of these sites is for abbreviating dynamic URLs which contain (long) queries embedded inside them (e.g. mapquest URLs). So we'll ask the same question, but now suppose that 1010 people each generate one dynamic request per second, for 1010sec (about 325 years — e.g. since William of Orange took the English throne in 1688). How long will the longest short-URLs be now?

To think about to yourself:
Does one of these sites do a better job than the other? Which do you prefer?