Don't Panic.

"Good News" -- there's a workshop and lab on this material.

** The Idea:**
Java loves generality, wants to avoid multiple virtually identical
routines for multiple types of objects that, abstractly, could be
treated "the same" (* is "the same" for 3*2 and 3.14159... *
2.71828...).

** The Problems:**

1. Java loves absolute tight-assed control over all types. So rather than, say, an interpreter like Matlab that quietly, discreetly, automagically converts types to do "what (it thinks) you want" with a polymorphic operator, Java enforces a truly impressive and arcane syntactical structure to allow the capability. There are mysteries in Matlab, also...

2. IMO, Data structures is NOT about the syntax or features, especially arcane and distracting features, of a programming language. Need careful balance: code, pseudo-code, English, pictures...

** The Excuse:**
The only excuse I can imagine is that Weiss wants to show Pseudocode-
level abstract algorithms, but wants 'em to run. With Java, he's
really
stuck and doesn't hesitate to make you pay.
Bad call, IMO. Maybe in some spinach-serving mode he believes
that you're on your way to write production-level code for a living,
and generics "are good for you." Who knows, really?

On positive note (*moi?*), function pointers are very useful anywhere, so Section 1.6 is worth
knowing.

** The Solution I:**
It says here that you 172'ers should embrace the opportunity to learn
new things, so you are warmly invited to grok generics in
their fullness, understand sections 1.4 and 1.5 thoroughly enough to
rederive the syntax out of your head, yada yada.

** The Solution II:**
For the rest of us, life's short. One could:

A. Get familiar with the syntax in a "passive" manner, enough
to read the text, understand the examples, remember the intention of
the syntax, and not get hung up on it.

B. Make a code template or two you can paste in when you need to produce a
generic solution for labs or workshops.

"In most of this chapter, we present the graph algorithms *using
pseudocode.* We will do this * to save space*
and, * of course, to make the
presentation of the algorithms much clearer.*"

-- Mark Allen Weiss, * Data Structures and Algorithm Analysis
in JAVA(TM), Chapter 10
(CB's emphasis.)
*

*
"Out of thine own mouth will I judge thee, thou wicked servant."
-- Luke 19:22
*

*
" 'Nuff said!"
-- Stan Lee, Stan's Soapbox, Marvel Comics 1965-67
*

Reference: FOCS Ch. 4, first half; 2nd half is related: probability.
Look For: Readings! On the course Web Page! Hint: *Foundations of
Computer Science (FOCS)* , by Aho and Ullman.

Why? First, It's vital to count things. Better, Combx is really fun and basically simple. Not advanced math at all, just a set of ways to think about the problem. Usually only * and + with integers!.

Useful? Well, if you know how many
poker hands there are and you know how many ways to get a pair, then
the *probability* of being dealt a pair is pairs/hands. The
*odds* of
getting a pair is pairs/(hands-pairs). Easy to convert between odds
and probabilities...

Given list of *items*, each of which is assigned
any one of a fixed
set of
*values* (duplicate values may be used).
How many assignments can be made? E.g. how many
different 8-long, 0-1 bitstrings are there?

** How To:** The number of ways to assign any one of *k*
values to *n* items is *k ^{n}*. Prove by induction.
Or think: k values to choose for 1st assignment, for each choice there
are k ways to choose the second...

So there are 2^{8} different bytes, from 00...00 to 11...11.

You're headed to *Muchas Tapas*, which has 19 tapas choices.
You're
going to choose three dishes, not necessarily all different. Plus
you've
got a coupon for a pitcher of either Cervezas Alhambra or Estrella
Galicia. Hell, why not?...you can skip dessert. How many dinner choices
do you have? Back-of-envelope: 2*.85*8000 = 13,600: Why? In factual
act, it's 13,718: Again, Why?

Given *n* distinct objects, how many ways can they be ordered
(placed in a line?). E.g. if we want to sort a list, how many
different
inputs (initial orders of the list) can there be? Call that number
Π(n).

** How To:** Π(n) = n!= n(n-1)(n-2)...3.2.1, n≥1. Proof by
induction.
Or just think: n ways to choose 1st place, leaves n-1 ways to choose
2nd place for each choice of first, or n(n-1) ways to choose the first two
items...etc. Last item: 1 choice.

**Big finish...** from just this you can prove a general lower time
bound
(best possible performance) for ALL sorting algorithms that work by comparing
elements,
AND you don't need to know ANY sorting algorithms to prove it! (FOCS
163-4).

How many ways can we select m items from a set of n items and put the selected items in some order? This is either a simple extension of Permutations, or a simple application of Assignments.

**How To Case I:**
We talk of "selection with replacement"
when we can select the "same thing" more than once, as in the 0's
and
1's and tapas choices in the Assignments section. In that case, the
ordered selection problem is just a case of assignment, so we get
n^{m}.

**How To Case II:** In "selection without replacement", once an item is picked, it
disappears from the list of pickable items. In that case, we'd expect
n choices for the 1st item, (n-1) for 2nd, down to (n-m+1) for the
mth.
Or the m-term, "partial factorial"-looking

n(n-1)...(n-m+1). Or the
elegant n!/(n-m)!.

How many ways to select m items out of n total, disregarding differences of order?

This is a key, highly-useful concept. Notation I like is the binomial coefficient, which looks something like

n ( ) m

only with big parens enclosing the upper and lower
values. In the combinatorics context this would be read "n choose
m".
This value is a *binomial coefficient*, and is often called
one. Here in html, we can use C(n,m) -- "The combinations of n things
taken m at a time" -- one of many notational variants using C,m, and
n.

**How To:** C(n,m) = n!/[(n-m)!m!].

Why? First, we want to choose m items out of n. By last section, the elegant way to count the choices, with every order being different, is n!/(n-m)!. BUT orders AREN'T different, so we definitely overcounted. We must divide by the number of ways to order m items, or m!, which gives the formula above. C(n,0) is 1, as is C(n,n).

Raise (x+1) to successive powers and you get 1, 1x+1, 1x^{2}+2x
+1, 1x^{3}+ 3x^{2}+3x +1... Pitch the x's and put the
(binomial) coefficients in a table:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...

*Voici* Pascal's triangle. The numbers in the mth column of the nth row
are C(n,m). What's the 'rule' for computing its entries? Justify it
semantically (cf FOCS p.172), getting an inductive proof.
Prove it by induction using the "factorials
formula".

Knuth vol. I (Chapter 1.2) is a wonderful resource for some
combinatorics and
especially bin coef topic, and Pascal's
triangle is
a treasure-trove of pretty results. Did you notice that the sum of
each row is 2^{n}? Super-easy proof by induction using the
"upstairs neighbors rule" for computing C(n,m). There are properties
of the diagonals, I don't know what all...And many identities.

How many different orders are possible if some items are identical? E.g. there are 3!=6 orders of the letters A, L, L... but only 3 different resulting "words" (where both L's are the same).

**How To:** With n items divided into k groups of sizes
i_{1},
i_{2}, ..., i_{k};
items within groups are not
distinguishable but those in different groups are. How many orders of the n
items?

n!/[i_{1}!
i_{2}!... i_{k}!].

Prove by induction. Or, think:
suppose we label each group member with unique ID. So we get (number-in-group)! possible
orders.
Now we need to divide out the number of orders of the kth group, for
all k. There are
i_{k}! orders for group k. Have to divide by
(the product of) them all. Obvious extension of previous ideas.

How many ways can we divide up n identical objects to distribute into m different bins? I.e. How many distributions are there?

It sometimes takes a little effort to see our problem using this bin metaphor. An easy example: we have three kids and four apples. How many ways are there to distribute apples amongst kids? Here kids are clearly the bins.

**The Trick:**
Pick a symbol, say A for apple, to represent the objects. So we have
four A's
in this problem. Let * be a "bin-separator" symbol, so we need two
for three bins. Notice that every string of 4 A's and 2 *'s
represents a different distribution. E.g. AAAA** says kid One gets 'em
all. A*A*AA says One gets 1, Two gets 1, and Three gets 2.

**How and Why To:** For n items, m bins: string is n+m-1 long with n A's
and m-1 *s to be distributed between the A's. Choose any n positions
for the A's and the rest get the *s. OR choose any m-1 positions for
the *'s and the rest get A's. Thus get

C(n+m-1, n) choices = C(n+m-1,m-1).

What's a bin? In chuck-a-luck, where 3 dice are rolled in a birdcage, how many outcomes are there? Here bins are numbers 1-6 on the die (!) and each die is an item. The roll assigns each die to a number, i.e. each item to a bin. So it's C(6+3-1,3) or 56 different outcomes.

Below the | are the five bin separators, the six bins are numbers on a die face, and we want to count how many ways to distribute the three identical dice into the bins.

D D D V 1 | 2 | 3 | 4 | 5 | 6 |

We have n objects, m bins, k different classes of
object, i_{k} members in each class.

**How To:** We'll just apply the "Identical Items" formula to
strings of
n+m-1 items, of which (m-1) are *'s and thus are a class
of identical items, and the rest may be put into the k identity
class of items.
So we count the different possible orders of such a string
with all elements different = (n + m -1)!, and then notice that all
orderings of identical elements in the string are equivalent, so we
need to divide by the product of those counts for every class,
including the bin-divider class.
Get:

(n+m-1)!/[(m-1)!i_{1}!i_{2}!... i_{k}!].

Our six different problems can all be considered as assigning objects to certain positions. For the first (Assignments), we have n different items (positions) and we need to fill each with one of k different values. Classify each proboem along three axes

- Does it place all the given objects?
- Is the order in which objects are assigned important?
- Are all the objects distinct, or are some "the same"?

Generally need several rules for a problem. Combx has some pretty sophisticated strategies and problems we didn't cover, (see a Combx text). Knowing what we do, we can often usefully

- Express count as sequence of choices
- Express count as difference of counts
- Express count as sum of counts for subcases

E.g. how many one-pair poker hands? The pair is 2 cards of same rank.
The hand thus has 3 more cards, each
of different rank, and not the pair's rank.
Think (and Compute by multiplying) in order:

Select the rank of the pair, (13 choices)

select three cards from remaining 12
ranks, (C(12,3) choices)

select the suits of 2 cards in the pair, (C(4,2))

select the suits of the other
3 cards (4^{3}) (FOCS p. 184-5).

Multiply these numbers of independent selections.

That's 1,098,240, or about 40% of all 2,598,960 poker hands.

Note (read on in FOCS) that the straight. flush. and straight flush hands need different treatment.

Subcases: just be organized: E.g. toss a quarter 12 times: how many times are there 8 or more heads? Boring, but easy, to calculate how many tosses give exactly 8, 9, 10, 11, and 12 heads.

Last update: 5/23/14