bash and gentoo

Arguably the best bash tutorial that I have ever seen. Concise but touched very advanced usage. Excellent examples.

http://www.ibm.com/developerworks/library/l-bash3.html

Also Gentoo seems to be worth exploring.

http://www.gentoo.org/doc/en/gentoo-x86-quickinstall.xml

book: how to solve it by computer

How to Solve it by computer.
By R. G. Dromey, 1982

I forgot how I get introduced into this book but this is the book that I wish I could read the first day when I started learn programming. Many fundamental but important techniques and guidelines are introduced via examples, with ingredients taken from almost every area in computer science, algorithm and data structure, formal verification. Very fine details are mentioned. Nowhere else have I seen these things.

One example is on Fibonacci numbers:
f(0) = 1, f(1) = 1, f(n) = f(n-1) + f(n-2)

Everybody knows how to compute the n-th fibo number using a loop running n times, but can you do it in O(log n) time?

I have a terrible memory of this problem because this was used in google codejam 2008 round 1A, and I didn't solve it. Neither can I read other people's solutions because I do not understand the magic numbers they use.

Now there are at least two ways to do it. Both using the idea of fast exponentiation.

1. Matrix representation. (I learned this from Dr. Chrobak in his Advanced Algorithm class).

/        \      /      \   /        \
| f(n)   |      | 1  1 |   | f(n-1) |
| f(n-1) |  =   | 1  0 |   | f(n-2) |
\        /      \     /    \        /

To compute n-th fibo number you just need to fast exponentiate the matrix.

2. Using the identity f(2n) = f(n)^2 + f(n-1)^2.
To derive it, observe this:

f(2n) = f(2n-1) + f(2n-2) = f(1)f(2n-1) + f(0)f(2n-2)
f(2n) = f(2n-2) + f(2n-3) + f(2n-2) = 2f(2n-2) + f(2n-3) = f(2)f(2n-2) + f(1)f(2n-3)
See the pattern?
f(2n) = f(i)f(2n-i) + f(i-1)f(2n-2-(i-1)) (*)
Now take i=n, you have the identity. You can prove (*) by induction.

AMPL the modeling language

Very natural to set up models which deals with large scale optimization problems. Close to algebraic notation.

Students version comes for free but limit is 300 variables and 300 constraints.

[lyan@localhost LPSolver]$ cat dualfit.mod
param k;
var f >= 0;
var d {1..k} >= 0;
var a {1..k} >= 0;
var x {1..k,1..k} >= 0;

maximize Dual: sum {j in 1..k} a[j];
subject to deno: f + sum {j in 1..k} d[j] <= 1;
subject to fac {j in 1..k}: sum {i in j..k} x[i,j] <= f;
subject to maxzero {j in 1..k, i in j..k}: x[i,j] >= a[j] - d[i];
subject to trig {j in 1..k, i in 1..j}: a[j] <= a[i] + d[i] + d[j];

[lyan@localhost LPSolver]$ cat dualfit.dat
param k := 20;

[lyan@localhost LPSolver]$ cat runk.sh
#!/bin/bash
if [ $# != 3 ]
then
echo "Usage: runk "
exit 1;
fi

START=$1
END=$2
OUTFILE=$3
if [ -f $OUTFILE ]
then
rm $OUTFILE
fi

for i in `seq $START $END`
do
echo "param k := $i;" > dualfit.dat
cat dualfit.dat >> $OUTFILE
ampl dualfit.run >> $OUTFILE
done

how to check webpage update time

In the address bar, type
javascript:alert(document.lastModified)