ipe: the diagram kit for latex

Ipe is a nice kit for drawing diagrams for latex. It exports both as eps and pdf. You can then includegraphics to get the diagram. The nice thing is that it allows you to use latex command to write math symbols and formulae.

Installation for Debian/ubuntu is straightforward, a couple of apt-get. However if you do not have root previlige and you are using Redhat system, here is what you can do:

fontconfig: http://www.fontconfig.org/release
Install the latest version, I use 2.8.0 and installed to /opt

Qt: http://get.qt.nokia.com/qt/source/qt-everywhere-opensource-src-4.6.3.tar.gz
in projects.pro, add a line
LIBS += /opt
so that qt will find your fontconfig before hits the old one in /usr/
compile Qt take a while.

LUA: put in /opt as well.

Here is my change for config.mak under ipe/src
LUA_CFLAGS ?= -I/opt/include
LUA_LIBS ?= -L/opt/lib -llua
QT_CFLAGS ?= $(shell pkg-config --cflags QtGui QtCore)
QT_LIBS ?= $(shell pkg-config --libs QtGui QtCore)

MOC ?= moc

there might be build errors when you type 'make'. Just go to the source file and comment out offending lines, or enable some lines that says 'Alternative'

Finally, the ipe script to run ipe, the PIEANCIENTPDFTEX is necessary if your pdflatex is older than 1.4

$ cat ~/bin/ipe
============================
#!/bin/bash
export LD_LIBRARY_PATH="/opt/lib:/opt/ipe7/lib:$LD_LIBRARY_PATH"
export IPEANCIENTPDFTEX=1
/opt/ipe7/bin/ipe $* &
============================

palindrome

Given a string, find the shortest prefix that is an even palindrome, in linear time.

The problem can be seen as asking for a minimum overlap of S and S^R. Then we can slide S^R to match a prefix of S by using Knuth-Morris-Pratt's algorithm to achieve O(n) time.