View Single Post
Old 04-20-2013, 08:44 PM
markact markact is offline
Junior Member
Join Date: Apr 2013
Posts: 3
Default Page 47 / Lecture 6 (10 min) Partitioning the table

I am struggling with one of more simpler bits of chapter 2.

On page 47 (Lecture 6 - 9 ~ 12 mins), I do not understanding how the table is constructed.

"Some dichotomies on these N-1 points appear only once" Okay, so to me, this implies we have 2^(n-1) rows for the first set (S1).

"The remaining dichotomies on the first n-1 appear twice, once with +1 and once with -1" How can this be true...?

To me, "the remaining dichotomies on the first n-1" would mean (2^n) less (2^n-1) = 2^n-1. But these appear twice! So we have 2*(2^n-1) = 2^n for set S2.

This seems as though we are counting twice.

S1 = 2^n-1
S2 = 2^n

The total of S1 + S2 is greater than 2^n.

Surely, I must be missing something really simple here. But what...? Please help.


Reply With Quote