Oleg Zabluda's blog

Tuesday, July 03, 2007

"Elements of Programming" (2009), Alexander A. Stepanov, Paul McJones

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

pairidentity_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

templateinverse_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

reciprocalinverse_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_functionr = 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.