CS 151 hw solutions

https://docs.google.com/folder/d/0Bx7eKFQAo1e-bTNDcDRWN2NVQ2c/edit


(a) Prove that if n is an integer and 3n + 2 is even then n is even, using a proof by:........


As you well know, I have a perfectly rectangular back yard.
First it all had only grass growing in it. I have decided to get creative and plant some
flowers in half of it. So I split my back yard exactly in half (cutting the long edge
in half) and planted flowers on one half, leaving the other with grass. I liked it, so
I decided I wanted tomatoes and maybe cucumbers, and perhaps some peppers. To
create new plots, I always split the grass plot in half, always cutting the long edge. Let
pn be the number of plots in my back yard after n splits.
.........................

Say precisely what’s wrong with each of the following proofs by identifying
the first sentence that does not follow from previous statements. (I’m looking for an
answer like “2+3 is not 4” and not “you didn’t say what variable you were doing
induction on”—you should explain why the proof is wrong, not why it’s badly written,

The cases in the inductive case aren’t exhaustive. When n = 5, the (n − 1)-cent
stamp pile is just a single four-cent stamp (so it doesn’t include either a three-cent
stamp or two four-cent stamps). If you....etc

(b) Suppose you are searching through k websites w1 , w2 , w3 , ..., wk , and each website
contains many pages: site wi contains pi pages. For example, the website www.cs.
uic.edu contains

A cellular automaton is a formalism that’s sometimes used to model complex systems—
like the spatial distribution of populations, for example. Here is the model, in its
simplest form. We start from an n-by-n toroidal lattice of cells: a two-dimensional
grid, that “wraps around” so that that there’s no edge. (Think of a donut.) Each cell
is connected to its eight immediate neighbors.


Suppose a code is needed to encode 30,000 items. A codeword is a string of characters
from an alphabet of 5 letters. If all codewords are the same length, what is the smallest
length those codewords can be? Explain.
https://docs.google.com/folder/d/0Bx7eKFQAo1e-bTNDcDRWN2NVQ2c/edit