Hi, Alex,

It's a great book! It's been my pleasure reading it. Here is a couple of comments I have:

======================> Slide 7  <==================================

All algorithms can be translated 1-to-1 to Python.

======================> Slide 28  <==================================

Let u = number of significant bits in n

maybe would be clearer for a typical programmer:

Let u = number of significant bits in abs(n)

Also the formula is correct only for n !=0 (or else p<0 a="" definition="" for="" natural="" of="" span="">
"significant bits" of 0.


======================> Slide 63  <==================================

No need to do int(x)

======================> Slide 133-134 (annotated_plus) <==================================

It would be cleaner and will reduce code a bit, if you store and pass ostream by
[non-const] reference.


======================> Slide 143 (Fibonacci Matrices) <==================================

Here is how you can continue refining the algorithom (just like the refinement do in the rest
of the book):

First, a short, and simple thing to do is to get rid of the check:

if (n==0)
  return 0;

and use power_nonegative() instead of power_positive.


by introducing zerowth Fibonacci matrix F_0 = |1 0| (identity matrix)
                                              |0 1|

For power_nonnegative() (Slide 126) to compile, one needs to define
identity_element (Slide 86), for op being fibonacci_multiplies (Slides 142-143).

template // I models integer
pair identity_element&>
{ return pair(0, 1); }

I think, it's very a valuable refinement because
1. it provides a nice, simple  and first non-trivial example of identity_element(op).
  This non-trivial example will be important for people who still need to get comfortable
  with monoids.
2. Nicely drives the point of your book about algorithm refinement, axioms, etc... slightly
further.


For more advanced readers, now that we extended isomorphism F: n -> F_n from semigroups to
monoids,
we can extend it to the whole groups, which will give us a chance to
1. use power() (Slide 127) instead of power_nonnegative()
2. introduce first non-trivial example of inverse_operation(op) (Slide 127, 87, 88), 
  reciprocal, inverse (Slides 87-89)


First we need to extend Fibonacci numbers n -> f_n to negative n. It it trivial by formula
f_n = f_{n-2} + f_{n-1} <=>
f_{n-2} = f_n - f_{n-1} <=>
f_{-n} = -(-1)^n f_n

Now we see that
1. F_0 is the identity matrix, just as above. Before we didn't really provide much justification
  for it.
2. F_{-n} = inverse(F_n) under matrix multiplication (see proof later)
3. F_m F_n = F_{m+n} is still true because everything on Slide 139 is still true, now that
  we proved item 2.

Proof of item 2:

Fibonacci matrices commute, so it's enough to show the reciprocity from the left.

Following Slide  141:

We need to show that (only second row is shown)
identity matrix = (0, 1) = 
F_{-n}F_{n} =
      ( f_{-n}f_{n+1} + f_{-n-1}f_{n}  ,  f_{-n}f_{n} + f_{-n-1}f_{n-1} ) =
(-1)^n (-f_{n} f_{n+1} + f_{n+1} f_{n}  ,  -f_{ n}f_{n} + f_{ n+1}f_{n-1} ) =
(-1)^n ( 0                              ,  -f_{ n}f_{n} + f_{ n+1}f_{n-1} )


So we need to show that 
-f_{n}f_{n} + f_{ n+1}f_{n-1} = (-1)^n

The proof is by induction:

Let's A(n) = f_{ n+1}f_{n-1} - f_{n}f_{n} 
Induction base:
A(0) = 1
Induction step:
A(n+1) = 
f_{n+2}        f_{n} -  f_{n+1}      f_{n+1} =
(f_{n+1}+ f_{n})f_{n} - (f_{n-1}+f_{n})f_{n+1} =
          f_{n} f{n}  -  f_{n-1}      f_{n+1} =
= -A(n) QED.


Now we can get back to the Slide 143 and have our generic algorithm for any n, including negative,
power() instead of power_nonnegative() and no special cases for n>0, n>=0, etc...

In order for power() to compile and work (Slide 127) we need to define 

template inverse_operation(const fibonacci_multiplies&)

Following Slide 88, and taking into account that
the formula for the inverse is (only second row is shown):
inverse(F_n)=F_{-n} = (f_{-n}, f_{-n-1}) = (-1)^n (-f_{n}, f_{n+1})

#define FIBONACCI_TYPE(I) typename pair // I models Integer

template // I models Integer
class reciprocal : unary_function 
{
public:
    FIBONACCI_TYPE(I) operator()(const FIBONACCI_TYPE(I)& x) const {
      f_n = x.first
      f_n_prev = x.second
      f_n_next = x.first + x.second
      sign = f_next*f_prev - f_n*f_n // (-1)^n

      return FIBONACCI_TYPE(I)(-sign*f_n, sign*f_n_next)
    }
};
template // I models Integer
reciprocal inverse_operation(const fibonacci_multiplies&)
{ return reciprocal(); }


======================> Slide 155 (Ordering) <==================================

Another excellent example would be a set of subsets of a given set. It's very useful
example for the further discussion of partially ordered sets (esp. which are _not_ weakly
ordered) as well as lattices.

======================> Slide 155 (Asymmetric) <==================================

I would call it antisymmetric, but it's your book :-)

======================> Slide 155 (Symmetric Complement) <==================================

Useful Exercises:

let s(a,b) be  asymmetric complement of r
s(a,b) = !r(a,b) && !r(b,a)

1. Prove that s is symmetric
2. Prove that r is strict => s is reflexive
3. Show for which of the examples on slide 155 s is transitive
(if you include subsets, there will be two non-transitive examples)

======================> Slide 63 (Weak Ordering) <==================================

Useful Exercise:

Prove that strict ordering is asymmetric.

Proof:

r is strict              <=>
r(a,b) => !r(b,a)        <=>  (X=>Y = !X||Y)
!r(a,b) || !r(b,a) = true <=>
r(a,b) && r(b,a) = false

Proof from the opposite. Suppose
r(a,b) && r(b,a) = true => (transitivity)
r(a,a) = true (contradicts that r is strict)


======================> Slide 169 <==================================

successor was not yet defined at this point in the book

======================> Slide 171 <==================================

Useful Exercises:

Lemma: a>b, a<=b, a>=b are orderings.
Lemma: if "<" is strict => then ">" is strict

======================> Slide 172 (Intervals) <==================================

I think it would be useful to point out that 
a (transitivity) a

You might also point out that "these definitions generalize to" partial orderings,
not just weak orderings.

======================> Slide 196 <==================================

I think it would be useful to point out that although weak orderings allows
binary_search(x, container), unlike for total ordering, the complexity is not log2(N),
as people might immediately assume, but log2(N) + M, where M is the cardinality of the
intersection of equivalence class of x under symmetric complement of the ordering and 
the container itself. In the worst case scenario it might be linear. You can again
refer the math reader to the examples on Slide 155 (or programmer reader to Slides 164-165).

======================> Slide 204 <==================================

Should read "Vectors OF A GIVEN DIMENSION with integer coordinates..."

======================> Slide 207 <==================================

Up until this slide, all C++ code was explicitly generic. Here we see an pretty abrupt
implicit transition to using overloaded operators. That's a perfect time to do it,
since the target reader is supposed to be able to transition by now, without
losing the understanding of genericity,  but it would still help to dedicate a couple of slides
to operator overloading. The Slide 171 (Overloading) does talk about reserving
< for the natural total ordering, but says nothing about -, +, 0, etc.. 

Around Slide 207 is a good time to explicitly transition to implicit operator overloading,
otherwise, the way the code in the future slides would be unreadable, and more importantly,
would not take advantage of the reader's intuition:

Slide 207 is the last one which is readable both ways:

template // T models Ordered Additive Group
T abs(const T& x)
{
  if(less(x, identity_element()>()) return inverse_operation(plus())(x)
  else                                        return x;
}

or even

template // T models Ordered Additive Group
T abs(const T& x,
      binary_function r  = less(),
      binary_function<  T, T, T> op = plus())
{
  if(r(x, identity_element(op)) return inverse_operation(op)(x)
  else                          return x;
}


======================> Slide 211 (Archimedean Group) <==================================

I think here it would be great to provide examples for all 4 combinations a, b positive
and negative, and compare it to  how programmers and different programming languages
(at least C/C++) treat / % div(N, D) for Integers (Z). Programmers have 3 ways to do it:
Truncating (towards zero), Floor, and Modulus. For example C/C++ division is truncation towards
zero (ISO C99 standard: ISO/IEC 9899:1999 paragraph 6.5.5.6), while yours is Floor.
Knuths' MMIX is Floor too. No languages or hardware that I know of, uses, Modulus,
(where the remainder is always positive) nor ever did I see it used in Math (Z/nZ),
because n was always positive.

========================================================

Misc:
The following items are missing in index:
Lattice
successor

========================================================

If I understand correctly, the book is not finished yet? There will be more material, right?
I have 410 Slides.

- posted by Oleg Zabluda @ 2:54 PM | permalink | | | technorati | bloglines | feedster