Generics

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.

Notable Quotes

"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

Combinatorics

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

The Assignment Operation

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 kn. Prove by induction. Or think: k values to choose for 1st assignment, for each choice there are k ways to choose the second...
Warning: It's no-of-values (k) to the no-of-things (n), not the other way around. Easy to get it backward.

So there are 28 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?

Permutations

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

Ordered Selections

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

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

Unordered Selections

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

Pascal's Triangle

Raise (x+1) to successive powers and you get 1, 1x+1, 1x2+2x +1, 1x3+ 3x2+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 2n? 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.

Orderings with Identical Items

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 i1, i2, ..., ik; items within groups are not distinguishable but those in different groups are. How many orders of the n items?
n!/[i1! i2!... ik!].
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 ik! orders for group k. Have to divide by (the product of) them all. Obvious extension of previous ideas.

Distributions of Objects to Bins

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 |

Distributions of Distinguishable Objects to Bins

We have n objects, m bins, k different classes of object, ik 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)!i1!i2!... ik!].

Summary Distinctions

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

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

Practicalities: Combining Rules

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

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 (43) (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