Monday, July 28, 2008

Doors Problem

Problem:
There are N doors in a hallway all closed. There is a robot that iterates through every ith door and it is programmed to invert that door's state. After i=N the robot stops. For i=1 the robot opens all the doors. For i=2 all even doors get closed. For i=3, door 3 gets closed and door 6 is opened etc. Which doors are left open after the robot is done going through all the doors?

Solution:
I knew that once an ith door was reached whatever state it received became it's final state. Which means door #1 is always open and doors #2 and #3 are always closed.
It wasn't immediately obvious to me which doors would remain open, so I wrote a little python program to help me see a pattern.

import math
def doors(x):
for n in range(1,x+1):
dstate = False
for m in range(1,n+1):
if n % m == 0:
dstate = not dstate
if dstate:
print "%.2f^2" % math.sqrt(n),

doors(1000)

Output
1.00^2 2.00^2 3.00^2 4.00^2 5.00^2 6.00^2 7.00^2 8.00^2 9.00^2 10.00^2 11.00^2
12.00^2 13.00^2 14.00^2 15.00^2 16.00^2 17.00^2 18.00^2 19.00^2 20.00^2 21.00^2
22.00^2 23.00^2 24.00^2 25.00^2 26.00^2 27.00^2 28.00^2 29.00^2 30.00^2 31.00^2
Clearly the pattern is obvious. The mathematical reason why this is so is more interesting than a simple empirical trend. Every integer has an even number factors... except squares.
4:1,2,4
6:1,2,3,6
7:1,7
8:1,2,4,8
9,1,3,9

This is because 3 is it's own factor pair.

Thursday, July 24, 2008

Windows NT Startup Process

I while back I wrote about the fact that I didn't really know how Windows startup works. As with many things wikipedia clears it all up. It looks like this is what I should have examined in the registry:
1) HKLM\SYSTEM\CurrentControlSet\Control\ServiceGroupOrder\List
2) HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\RunOnce
3) HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\policies\Explorer\Run
4) HKLM\SOFTWARE\Microsoft\Windows\CurrentVersion\Run
5) HKCU\Software\Microsoft\Windows NT\CurrentVersion\Windows\Run
6) HKCU\Software\Microsoft\Windows\CurrentVersion\Run
7) HKCU\Software\Microsoft\Windows\CurrentVersion\RunOnce
8) All Users ProfilePath\Start Menu\Programs\Startup\
Now I know.

Tuesday, July 22, 2008

Bridge Crossing Puzzle

I was reading Introduction to the Design and Analysis of Algorithms book and found a neat puzzle.

Problem:
There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses either 1 or 2 people must have a flashlight. The flashlight must be walked back and forth, cannot be thrown. Person 1 takes 1 minute to cross. Person 2 takes 2 minutes. Person 3 takes 5 min. Person 4 takes 10 min. A pair must walk together at the slower person's pace. For example if person 1 walks with person 4 it takes 10 minutes for both of them to cross. If person 4 takes the flashlight back, a total of 20 minutes has elapsed and the mission failed.

Solution:
The most interesting part to me is the concept. You want to minimize the impact of the two slowest walkers, you try to avoid having either of them make more then one trip. You can mitigate the 5 min walker by sending him with the 10 min walker. The second optimization you try to do is decrease the "bringing-the-flashlight-back" time, so the fastest people should bring it back.

----------- symbolizes the bridge the bridge
0) ----------- 1 min 2 min 5 min 10 min
1) 1 min 2 min ----------- 5 min 10 min
Time: 2
2) 2 min ----------- 1 min 5 min 10 min
Time: 3
3) 2 min 5 min 10 min ----------- 1 min
Time: 13
4) 5 min 10 min ----------- 1 min 2 min
Time: 15
5) 5 min 10 min 1 min 2 min -----------
Time: 17

Friday, July 18, 2008

tailor svn to hg

I few weeks ago I discovered tailor. After installing the latest tarball. Following this tutorial I was able to checkout from a svn repository from work into my hg repo. I was not interested in pushing back changes, in my case the project ended, however it should be easy enough to do.

I called my config file: projectname.tailor

[svn-to-hg]
root-directory = /home/me/projectname
source = svn:projectname
target = hg:projectname
state-file = svn-to-hg.state

[svn:projectname]
repository = https://svnserver/svn/main/projectname
module = /trunk
subdir = svnside
trust-root = True

[hg:deamc]
repository = /home/me/projectname
subdir = hgside

At the terminal:
 $ tailor --configfile=projectname.tailor svn-to-hg
This will create two directories in /home/me/projectname/ hgside and svnside.

XeLaTeX fun

After reading this post I wanted to dabble with TeX again. I haven't used it since university days so I thought it was time to polish off the rust. I am on a Debian box, so these are the steps I took to get XeLateX to work.
$ apt-get install texlive-full texlive-formats-extra
$ mkdir ~/.fonts && cd ~/.fonts
$ wget http://www.gust.org.pl/projects/e-foundry/tex-gyre/pagella/qpl1.103otf.zip
$ unzip qpl1.103otf.zip
$ rm qpl1*.zip
After about 20 minutes I had everything set up and was ready to follow the tutorial.
My sample.tex file looks like this:
\documentclass{article}
\usepackage{fontspec}
\setromanfont{TeX Gyre Pagella}
\begin{document}
Testing XeLaTeX!

Greek: τεχ
\end{document}
Now to make sure everything works...
$ xelatex sample.tex
This is XeTeXk, Version 3.141592-2.2-0.996-patch1 (Web2C 7.5.6)
%&-line parsing enabled.
entering extended mode
(./sample.tex
LaTeX2e <2005/12/01>
Babel and hyphenation patterns for english, usenglishmax, dumylang, no
yphenation, arabic, farsi, croatian, ukrainian, russian, bulgarian, czech, slo
ak, danish, dutch, finnish, basque, french, german, ngerman, ibycus, greek, mo
ogreek, ancientgreek, hungarian, italian, latin, mongolian, norsk, icelandic,
nterlingua, turkish, coptic, romanian, welsh, serbian, slovenian, estonian, es
eranto, uppersorbian, indonesian, polish, portuguese, spanish, catalan, galici
n, swedish, ukenglish, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/size10.clo))
(/usr/share/texmf-texlive/tex/xelatex/fontspec/fontspec.sty
(/usr/share/texmf-texlive/tex/generic/ifxetex/ifxetex.sty)
(/usr/share/texmf-texlive/tex/latex/tools/calc.sty)
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.sty
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.tex
(/usr/share/texmf-texlive/tex/latex/xkeyval/keyval.tex)))
(/usr/share/texmf/tex/latex/lm/lmodern.sty)
(/usr/share/texmf-texlive/tex/latex/base/fontenc.sty
(/usr/share/texmf-texlive/tex/xelatex/euenc/eu1enc.def)
(/usr/share/texmf-texlive/tex/xelatex/euenc/lm/eu1lmr.fd))
fontspec.cfg loaded.
(/usr/share/texmf-texlive/tex/xelatex/fontspec/fontspec.cfg)) (./sample.aux)
[1] (./sample.aux) )
Output written on sample.pdf (1 page).
Transcript written on sample.log.
Success!
Next time I'll create something a little more substantive.

Wednesday, July 16, 2008

Things that surprised me

These are concepts from Math,Comp Sci, Physics that have surprised me over the years:

Recursion
My first formal introduction to recursion was through Fibonacci numbers. While the uses of these numbers are quite surprising( i.e. Euclidean algorithm's running time ). I was never really impressed with them. They seem simple enough. What really floored me about recursion, was the solution of the Tower's of Hanoi problem and subsequently the 8 Queens problem. On the surface they seemed so difficult to write a good simple solution for but where made almost trivial with recursion. Recursion still amazes me today.

Mathematical Induction

Induction ties into recursion above, but it needs it's own category in my list. Induction did not even seem fair when I first learned it. It was as if I was cheating. I could prove statements that I knew almost nothing about with minimal effort just by slogging through the algebra steps. At the end I still felt like I haven't really grasped the problem. A good example at the time was the sum of cubes.

Lambda Calculus
If there is one good way to study recursion it's lambda calculus. This field has augmented my understanding of every single item bellow and still continues to. From combinators to formal renaming schemes to deriving natural numbers(more on this later).

Lisp
I have learned as much about Computer Science from this language as I did with everything else I've encountered in this field combined: Functional Programming, OO, macros, closures, higher order functions, bottom-up programming, parsers, syntax. Each of these areas has either been completely revolutionized in my head or planted there, where before was nothing.

Dedekind Cuts
I have never imagined that it's possible to derive Real and Complex numbers out of Integers. What an amazing feat (see: Foundation of Analysis by Landau).

Derivatives and Integrals
These two things are reason I decided to also get a Math degree. I really wanted to understand why and how these work.
I remember what I thought when I saw derivatives in high school like it was yesterday. "So I take a function f(x) change an argument I am passing to it to x+h where h is so small that I can never write down a number y greater than zero that is smaller than h. Subtract f(x) and then divide this sum by another effectively zero "number" and I get rate of change with respect to x. Great!" Once that became clear, I ran into another issue.

The situation got worse with Leibniz notation. I could do things like "cancel out" infinitesimals (dx/dt)*(dt/dy)=dx/dy but I could not do this with derivatives with a higher order than 1. Makes perfect sense!

For integrals it was worse. "I take f(x) multiply it by something that makes no sense by itself and add up all the columns in the interval and BAM!... I got the function I was looking for. Great!"

Taylor's Theorem
I was delighted when I found this was possible. I always wanted to prove it. When I finally got to in Real Analysis and was able to prove it, it was one of the most satisfying experiences of my college career.

Fourier Series/Transform
This started in my Differential Equations course and made worse by my Signals and Systems EE class. In DEq I was told about Laplace transforms. In EE I was told about FTs. I had no idea how these could possibly work. Fourier series was also quite disturbing. If I add a bunch of infinitely smooth functions I can get non-smooth ones. This was a pretty big deal. These transforms are still on my list to prove.

Lagrangian and Hamiltonian Formulation of Newtonian Mechanics

I am still working on these concepts. I was never satisfied by their explanations in class. You'll have to watch the Sussman lecture to understand why.

Noether's theorem
Out of all the physics discovered this in my mind is the most amazing theorem. Even in simplified form I am in awe.

Of course the list has more entries but these are my top 10.

Sunday, July 13, 2008

aria2 download tool

I ran into an interesting downloading application, Aria2. I was reminded of a GetRight utility I ran into years ago. The thing I really liked about GetRight at the time was the ability to download linux ISOs from multiple mirrors and merge the results into one coherent file. It really sped up downloading new Slackware releases :-) This to me is the most compelling feature of Aria2 and it works thus:
aria2c -s2 http://host/image.iso http://mirror1/image.iso http://mirror2/image.iso
The main page has plenty of examples with many different transfer protocols. Too bad the parallel download features seem to have disappeared with the invention of bit torrent.

Wednesday, July 9, 2008

Countable Rational Numbers

In my Real Analysis class in college I remember seeing the proof that rational numbers are countable via a diagonalisation argument. Proving something is true and implementing a counting algorithm that will assign any given Rational a unique positive integer are two very different things.

This link is class room explanation behind all the math without dumbing anything down. Here's the original amazing paper by virtue of simplicity and elegance. The only things needed to understand it is the most rudimentary understanding of binary trees and Euclid’s gcd algorithm.

I wrote up some scheme code to print out the "parents" of the node, which allows one to assign a unique positive integer to every/any Rational.


;Tree
(define (display-all . args) (display args))
(define (p-parents m n)
(cond ((or (zero? m) (zero? n)))
((= m n) (display-all 1 "\n") 1)
((< m n) (display-all m " " n "\n")(p-parents m (- n m)))
((> m n) (display-all m " " n "\n")(p-parents (- m n) n))))

;Print the parent nodes of 49/19
(p-parents 49 19)

Tuesday, July 8, 2008

Sussman Thought Process

I found a great lecture by Gerald Sussman about thought processes and computers. I stumbled upon it when reading about the Feynman algorithm of solving problems.
The Feynman Algorithm:

1. Write down the problem.
2. Think real hard.
3. Write down the solution.

His talk about Structure and Interpretation of Classical Mechanics reminds me of a quote by Knuth: "Science is what we understand well enough to explain to a computer. Art is everything else we do."

World Magnetic Model

In about a dozen or so math courses I remember having to prove (always by induction) that the sum of N numbers (1+2+3+...+N) is equal to n(n+1)/2 and always thinking, this is pointless. I stand corrected.

At work I was tasked to calculate magnetic declination using java instead of the C implementation NOAA used. The program is pretty much a function: MagDec:(double,double,double)->double (elevation,latitude,longitude)->magnetic_dec. A key component used to calculate the declination is a file with spherical harmonics gathered by satellites. It looks something like this:

          G(m,n)   H(m,n)       G_dot(m,n)  H_dot(m,n)
1 0 -29556.8 0.0 8.0 0.0
1 1 -1671.7 5079.8 10.6 -20.9
2 0 -2340.6 0.0 -15.1 0.0
2 1 3046.9 -2594.7 -7.8 -23.2
2 2 1657.0 -516.7 -0.8 -14.6
3 0 1335.4 0.0 0.4 0.0
3 1 -2305.1 -199.9 -2.6 5.0
3 2 1246.7 269.3 -1.2 -7.0
3 3 674.0 -524.2 -6.5 -0.6
4 0 919.8 0.0 -2.5 0.0
4 1 798.1 281.5 2.8 2.2
4 2 211.3 -226.0 -7.0 1.6
....
....
12 10 -0.1 -0.9 0.0 0.0
12 11 -0.3 -0.4 0.0 0.0
12 12 -0.1 0.8 0.0 0.0


My goal was to create S = G(m,n) - G_dot(m,n) and C = H(m,n) - H_dot(m,n) for each value of m and n.
Since Java IO isn't the most convenient thing in the world, instead of sscanf() I was forced to use java.util.Scanner, which IMO is not nearly as convenient for this type of data organization.
I realized that if I have a flat list it looks something like this:

Col. A Col. B
G(1,0) -29556.8
8.0
G(1,1) -1671.7
10.6
G(2,0) -2340.6
-15.1
G(2,1) 3046.9
-7.8
G(2,2) 1657.0
-0.8
Written in a different way:
G(1) G(2) G(3) ... G(12)
2 3 4 ... 13

which means there are 13(13+1)/2 - 1 coefficients for G. If I am presented with a single column of numbers like Col B. and I want to pick G(2,1) all I need to do is is realize that there are 3(3+1)/2 coefficients up to G(2,2) which means G(2,1) is 3(3+1)/2-1. Of course it would've been a lot easier if I could do the straightforward thing easily like:

WMM = open("WMM.COF")
coeffs = []
try:
for line in WMM:
nline = []
for each in line.split():
nline.append(float(each))
coeffs.append(nline)
finally:
WMM.close()
but it's not to be.

Monday, July 7, 2008

School Algebra Story Problems

This was taken from Marvin Minsky's Why programming is a good medium for expressing poorly understood and sloppily-formulated ideas.

Mary is twice as old as Ann was when Mary was as old as Ann is now. If Mary is 24
years old, how old is Ann?

Not exactly obvious.

Saturday, July 5, 2008

IpChains

Task

Write a iptables script that blocks everything except ping (icmp) and ssh (port 22), http (80) and https (443).

Solution
  #!/bin/bash
export ipt=/sbin/iptables
$ipt -F #Flush all the rules one by one
$ipt -X #Zero all standard chains and statistic counters
$ipt -Z #Erase all user created chains
#Three commands above anything that might have existed prior to running the script to make sure there is a clean slate.
$ipt -P INPUT ACCEPT #Create a behavior for INPUT policy, which is to accept
$ipt -P OUTPUT ACCEPT #Create a behavior for OUTPUT policy, which is to accept
$ipt -P FORWARD ACCEPT # Create a behavior for FORWARD policy, which is to accept

#We call iptables and tell it to Append to the INPUT policy.
#This line allows traffic to go through port 22
$ipt -A INPUT -m state --state NEW -m tcp -p tcp --dport 22 -j ACCEPT
$ipt -A INPUT -m state --state NEW -m tcp -p tcp --dport 80 -j ACCEPT
$ipt -A INPUT -m state --state NEW -m tcp -p tcp --dport 443 -j ACCEPT
$ipt -A INPUT -m state --state NEW -m tcp -p tcp -j DROP

#Allow pings
#Ping requires the ability to accept packets and send packet back out.
#Ping is a layer 3,ICMP operation.
#In order to allow it our protocol now becomes icmp instead of tcp. We do not need any modules.
#Ping packets are able to be received.
$ipt -A INPUT -p icmp -j ACCEPT

#Ping packets are able to be sent
$ipt -A OUTPUT -p icmp -j ACCEPT
-m says load a module state which allows access to the connection tracking state of the packets
--state precedes a comma separated list of the connection states to match. In this case it's NEW.
NEW the packet has started a new connection or a connection that has not seen packets going in both directions
-m tcp load the tcp module (just like we loaded the state module) this module allows us extra functionality with tcp
-p tcp specifies protocol, in my case TCP
--dport 22 feature provided by the -m tcp module, in this case I want the rule to be applicable to port 22 (ssh).
-j ACCEPT means the results of this chain is to accept the packets. (-j specifies the target of the rule if the packet matches the rule. If I said -j DROP we would block all traffic to port 22).

Norton Internet Security

Last night I was asked to debug a problem with a Windows XP laptop that had Norton Internet Security installed. The problem? "The internet didn't work." Unfortunately I didn't realize about Norton Internet Security part until later. While the fix was simple, disable Norton Internet Security, the symptoms of the problem weren't obvious to me.

Connection acquisition wasn't a problem "ipconfig /release" and "ipconfig /renew" just worked. Pinging IPs worked but pinging hostnames failed. Putting and IP in the browser like 72.14.207.99(google.com) worked.
I thought... classic dns issue. "ipconfig /flushdns" should just solve it. Wrong. I was really surprised when "nslookup google.com" worked. So I could resolve hostnames to IPs, I can connect to IPs but when I put it all together it fails.

At this point Safe Mode with Networking to the rescue. In safe mode everything just works. Clearly something starts up in regular mode that screws up the connection.
Not seeing Norton Internet Security Icon in the in taskbar in regular mode, because it's hidden, I went the msconfig route. Disabling everything possible and restarting still didn't solve the problem.

The lesson here was that Norton gets it's claws so deep into the system that it's not obvious it's running at all, when in fact it is and the firewall itself can act in pretty unintuitive ways.

Thursday, July 3, 2008

Saving Real Media streams

I like to watch Berkley's stream lectures. I do not like to have to start
at the beginning of a lecture and wait for the buffer to catch up to where I
was last time before I got interrupted. After some googling I was able to find
out how to save real media streams with mplayer.

Bellow is a bash script I wrote in order to download EE 140 lectures:

url="rtsp://169.229.131.16:554//bibs/s2004/group1/ee140"
for fname in "20040120" "20040122" "20040127" "20040129" "20040203" "20040205"
"20040210" "20040212" "20040217" "20040219" "20040224" "20040226" "20040302"
"20040304" "20040309" "20040311" "20040316" "20040318" "20040323" "20040325"
"20040330" "20040401" "20040406" "20040408" "20040413" "20040415" "20040420"
"20040422" "20040427" "20040429" "20040504" "20040506" "20040511"
do
mplayer -bandwidth 2000000 -cache 3000 -noframedrop -dumpfile "$fname.rm" -dumpstream $url/"$fname.rm"
done

-bandwidth 2000000 set the download rate to 2Mbps without this data downloads
in real time which means it takes 60 minues to download a 60 minute lecture.
-cache 3000 is useful because you are downloading a lot faster than real time
-noframedrop and -dumpfile should be pretty self explanatory
-rtsp is the proprietary protocol which real media streams with
$url is taken from inspecting the .rm files

As far as I know this method can be employed for any streaming media mplayer
can playback. I haven't tried it on anything except the Berkley lectures.

Refereces:
http://ubuntuforums.org/showthread.php?t=635058
http://thomer.com/howtos/capture_realstream.html <-- howto stream audio only