Mgccl's Ivory Tower

Small script for sharing screenshots

Mgccl — Fri, 07 Jan 2011 20:58:05 +0000

I posted a script over at github.

I have named it shot and placed in /usr/local/bin

It take a screenshot of the whole desktop and upload to imageshack.us, then it put the link into the clipboard.

shot

If you only need a shot of a selection of the screen, do

shot s

If I need it to delay a few second, then take the screenshot of the whole desktop, I do

shot 10

where 10 can be replaced by any amount of delay in seconds.

An absurd method for finding the square root of a integer

Mgccl — Tue, 26 Oct 2010 09:54:49 +0000

A common interview question.

Find the square root of a integer n, without using the built in sqrt function. (Result has to be a float or double)

There are many ways to do it(in fact I thought of every one of them in 10 seconds).

I want to come up with a way no one else would think of. Something that could amaze the interviewer.

I present the following solution. I put the code on Gist.

How does it work?

We know is a integer. Therefore, by Lagrange's four-square theorem, for integer . . Thus is the magnitude of the vector . can be calculated by brute force search(therefore runs in O(n^2) time). There exist a better randomized algorithm. I don't have access to the paper so I can't do anything about it.

Note a simple improvement of the naive algorithm can reduce the computation time to . I can't be bothered to write it.

A recursive algorithm using the following relation can find the magnitude of any vector,

FUN!

I challenge people to come up with even more absurd way to calculate square roots.

Time Lapse Screenshots

Mgccl — Wed, 25 Aug 2010 02:37:33 +0000

I wrote a script for time lapse screenshots.

The newest version can be found on github.

The version as of writing.
timelapse.sh usage(requires scrot)
./timelapse dir_name second_interval limit
Note if limit is negative, it is the same as having no limit.

#!/bin/sh
mkdir $1
i=0
t=-1
if [ $# -eq 3 ]
	then
	t=$3
	fi
while [ $i -ne $t ]
	do
	sleep $2
	a=`date +%Y%m%d_%H%M%S`
	#a=$i
	scrot $1/$a.png
	i=$[$i+1]
	done

video.sh usage(requires mencoder)
./video.sh dir_name width height fps filename

#!/bin/sh
mencoder mf://$1/*.png -mf w=$2:h=$3:fps=$4:type=png -ovc lavc -lavcopts vcodec=mpeg4:mbd=2:trell -oac copy -o $5

An demo.

Confidence destroyer

Mgccl — Tue, 20 Jul 2010 05:22:55 +0000

I know this person, let's call her JJ. When ever I feel confident about myself, I talk to her.

It's a habit. If I don't talk to her, I would go
"Hey, I'm on the top of the wooooooorld~ MUHAHAHAHAHAHA,.. I'm so getting into a good graduate school..."

Some of the talks I remember, goes basically like this. due to my lame memory, I can't recite things word by word.
M = Me

(Talking about a USAMTS problem... the USAMTS t-shirt I have features that problem... if you see me wearing something black with cubes in the back, then you know that's the problem)
M: I don't see how that's possible.
J: flip this way so the face on cube one that's facing forward is now facing down, and then rotate the side facing forward 180° = =, apparently u don't play the rubiks cube..
M: orz

M: OMG there is a IMO gold and IMO silver in Stony Brook.
J: I know a IMO gold live right next door / I had lunch with a putnam fellow/ blah blah with IMO/Putnam people
M: orz

M: I took the Putnam today.
J: me too, a dozen people there are IMO gold or Putnam fellow.
M: orz

M: I'm thinking of doing independent study on analysis next semester.
J: I'm in this analysis class where half of the people have been to IMO. It's hard to stay above average.
M: orz

M: I'm in BNL this summer, I assume you are doing something with the same scale of awesomeness in MIT.
J: I'm in the AI lab, coding, working with Marvin Minsky, the FATHER of AI.
M: orz

My confidence crumbles every time xD. It is a good thing...

I'm in a place where people think I'm pretty good. I become modeled into thinking "Hey, I'm pretty good." It's a scary thought if I'm actually not that good. JJ can always help me adjust to the view I'm suppose to have. Since I will be competing(unsuccessfully...) with people with skills even beyond JJ in the future for positions in the academia, I can't stop short and think "Hey, I'm pretty good."

Thank you for all your support JJ. Also thank you for believing me that I can transfer to MIT when I don't even believe it myself. I will try my best.

I might have ADHD all my life

Mgccl — Mon, 19 Jul 2010 05:54:19 +0000

For some unknown reason i discussed ADHD with my parents when they refuse to understand there are common disorders prevent people from learning.

While discussing it, I found striking similarity of ADHD's symptoms and what I have. I did some wikipedia and convinced I'm likely to have ADHD.

Predominantly inattentive type symptoms may include:
Be easily distracted, miss details, forget things, and frequently switch from one activity to another [YES, I found it impossible reading in a car, a train, a plane or anything where I feel I'm moving around. Or if I can see anything moving or hear any sound.]
Have difficulty focusing on one thing [YES]
Become bored with a task after only a few minutes, unless doing something enjoyable [YES, that's why I fail at everything except things I enjoy]
Have difficulty focusing attention on organizing and completing a task or learning something new [YES]
Have trouble completing or turning in homework assignments, often losing things (e.g., pencils, toys, assignments) needed to complete tasks or activities [YES, no pen can stay with me for more than 3 days unless I don't use that pen.]
Not seem to listen when spoken to [YES, ok this might be of some other reason, most people are boring]
Daydream, become easily confused, and move slowly [YES, but then again, it seems a lot of people are easily confused]
Have difficulty processing information as quickly and accurately as others [YES, especially in fields where I have no background]
Struggle to follow instructions. [YES, I epically fail at every lab class]
Predominantly hyperactive-impulsive type symptoms may include:
Fidget and squirm in their seats [YES, I can't hold one comfortable position during sitting, unless I'm asleep]
Talk nonstop [If I'm talking to you, then yes, else no. If I'm alone, I talk to myself, but that should be another kind of beast.]
Dash around, touching or playing with anything and everything in sight [NO]
Have trouble sitting still during dinner, school, and story time [YES]
Be constantly in motion [YES, unless I'm on my bed]
Have difficulty doing quiet tasks or activities. [NO]
and also these manifestations primarily of impulsivity:[34]
Be very impatient [YES]
Blurt out inappropriate comments, show their emotions without restraint, and act without regard for consequences [don't know, it only happen around people I know]
Have difficulty waiting for things they want or waiting their turns in games [YES, I have to beat this 4 year old in SOULCALIBER]

I have almost all symptoms.
These symptoms are general, I do feel normal people will have a few of them too. Having this many? it strike me as having a problem.

When i was young(elementary school level), I have been described by my parents and teachers as having hyperactivity. Non of them are doctors however. I like how my family have the culture of not seeing any doctors(unless it's FREE checkup). So they don't care if I might have hyperactivity disorder, it's not something that will kill me.

I also fall into my own world during class. Wondering stuff until I was called to answer some question the teacher asked. Ahh, lots of embarrassment.

I doubt any of them considered I have attention deficit disorder. Not many kids can follow orders when they are young. Therefore I have no idea such thing even existed, until I'm in my 11th grade in US. I even doubt such disorder is not something people made up so they can take it easy on school work.

Even if I have ADHD, I can still live out a normal life. My grades are better than average, and if I didn't do well at something, clearly I wasn't working hard enough. There should be no reason for anyone to even assume I might have a disorder. I must have a brain that perform above average, and I just don't use them in things like English, History and stuff, how else can the huge gap between my math and English grade be explained?

I didn't spend much time on the courses I suck at, fits the description "Become bored with a task after only a few minutes". Self disciplines issue? It must be.

Maybe not.

Concentration have always been a problem. I can read a book and mind drift away into something else by one keyword. and when I finish drifting, I already turned the page, everything in between is lost. This is SCARY. I read a book and not remember what I have read, most of the time. How do I learn at all? Read a paragraph k times until I think I have read it. The GEB took me a month to complete, and now i can only remember the main themes. All the details are lost.

This prevent me enjoy fictions. I have stopped reading fictions 5 years ago.(Ok i lied, I read 3 pages of twilight for reasons I don't want to disclose). Things jump around, nothing makes sense. I forget things I read in the beginning. And I start read plot summaries instead on wikipedia because that's about the attention span I can handle.

Of course, this could also be a memory problem.

Concentration are related to boredom. If I can't concentrate on doing one thing, and keep getting distracted by thoughts that appear to be more interesting, of course I found what I'm doing bored.

What about math? I do find it boring to read textbooks. I'm glad in math, you read and understand a few sentences, the rest can be done by pure thought experiments. In high school, I come up with formulas and solutions during the exam.
So is the CS classes I took in college, it's ALL theory classes. It's not that I have read a lot more texts, I just remember some points and try to figure things out in small chunks when I'm reading texts on how language unite people during ESL classes. Wow, epic distractions.

I can't just do thought experiment and suddenly knows what happens in 1800's art culture. These are the kind of knowledge where I must gather though intense text intakes. Not able to concentrate greatly decreases my desire to know.

I never thought this was a problem at all. I thought it applies to everyone. The idea of "learning is not easy" circles around. Then I went to college and see people crunch though dense texts(they don't even like) like nothing. Hearing someone complete John Hull's Options, Futures, and Other Derivatives in a week. (she got a phd in physics from caltech, so this is not a good example of normal person, but it still affects me psychologically). Something must be wrong with me, or I'm just surrounded by people who are way too brilliant in feeding on knowledge(If that's true then I must be a elitist who only make friends with really brilliant people... not a good thing either).

During the summer research, I have even more doubts in my ability. I can code fast, grasp new concepts really quickly and work hard enough that my mentor want me to intern with him during this fall. Except I can't learn well because I can't concentrate. You will see me moving in and out from the office 5 times more frequent than the other 2 people in my room combined. I observe the differences between me and the other researcher, they are not easily distracted. I even get distracted by my own thought during group meetings. It's not they are knowledgeably septate them from me, it's the power to concentrate.

This remind me how the year before, I have hard time reading a book on radiation detection. The mind slips I walks into makes learning a dense topic almost impossible.

During coding I always miss some small stuff, it's hard to write a program that compiles the first time(usually I need to compile k/10 times to make it work, where k is the amount of lines). Finding mistake in my own code is difficult because I always forget my definition of the variable(like what is this variable v correspond to?). People who do programming competitions totally owns me in this category. IDK if I'm better than a normal programmer.

I can IM with someone and forgot I'm IMing someone and start doing something else. Usually it's when I receive a message, and forgot to turn to the window right away, and forgets about it. That certainly get people mad. Later I developed the skill to switch between tasks periodically as soon as a task become non urgent. It greatly decreases my response time, but still, not good enough. This is the reason I decided to stopped using all IM systems a few days ago. Back to good old email.

If it is indeed true that I had ADHD all my life, then I can change for the better. To make myself having the power or a normal human! How awesome is that? The power of owning GRE and get into a good graduate school. mmmmm, normal human ability rocks.

Get diagnosed by doctors in China is cheaper than the US. Hmmmm...

I need a new design for this site

Mgccl — Fri, 04 Jun 2010 10:51:41 +0000

After using Elinks on POJ. I'm very amazed with how POJ turned out. It looks super elegant!
See the image here
I think simplicity is the key to design.
I'm no designer, but I would be perfectly happy if every website can be accessed in elinks style I showed.
So what should the style look like?
Everything have the same fixed size font. It's possible to have bold fonts for strong characters or something. At most 16 colors can be used. Too many colors doesn't help bring up the contents.
Minimum CSS for layout. In fact, there should only be layout for simple positions. It should have 1 column layout because it's awesome.
What about sidebars? you might ask.
Sidebar is overrated. When is the last time I looked at the sidebar? If one need to see list of recent comments, recent blog post and stuff, they should go to a special page that show stuff like this. Most sidebar items are not useful content at all.

Adapting the unix philosophy on content presentation.

"Write a site that show one thing and show it well"

Human Identification Number

Mgccl — Tue, 25 May 2010 01:30:53 +0000

Many country have national identification number for their citizens(even non-citizens).
How about a universal human identification number?

This number should be powerful(as powerful as SSN) and we can show it in the open. Not like SSN, no one can put them online.
Why can we put our AIM user name and other usernames online? Because the number itself isn't the only way to authenticate. There is a password too.

We also need a government agency that authenticate if a person is who they claim to be.
Then it's possible to have 1 ID for EVERYTHING.

There is a similar idea. OpenID.
How about, government create something similar to the OpenID and replace it completely.

We can establish a world identification organization in the united nations... but hey, having a one world government, it be much easier to enforce rules.

Human civilizations have developed for this many years, and there is no unified government yet. Humans, I am disappoint.

Course recommendations

Mgccl — Fri, 07 May 2010 05:36:06 +0000

I'm done with this semester, except the finals.
Computational geometry with Joe Mitchell(I doubt anyone else ever teach that class...)and any class with Skiena rocks.

I took CSE 555, computational geometry this semester with Professor Mitchell.
It is the most interesting class I have taken in college.
It is not the most active in student-professor interactions, but the lecture is awesome enough to cover this flaw.

The first time I met computational geometry is in 9th grade, where I borrowed(an older edition of) the textbook that was used in CSE 555, Computational Geometry: Algorithms and Applications
. As a 9th grader, I found the book hard to understand. The only things I picked up were the existance of convex hulls. I returned the book to the library after a almost getting though the first 2 chapters.

It is quite useful, as later in life, I have meet problems I know it is asking for the convex hull.

I have learned so much in the course. Convex hulls, triangulation, point location, art gallery problem, voronoi, duality, double connected edge list, linear programming and more.

I still can't implement a bug free program for any of the above topics, but this greatly decrease the amount of unknown unknowns to known unknowns. If one knows how to solve a problem, one can use tools made by other people to solve it. During competitions, this is not possible. Thus I have to still implement some of them.

The power to reduce some problem into others made such a huge impact. This is demostrated in a lot of homeworks. Especially the one on linear programming. I especially liked this problem:
Given two set of points on the plane, does there exist a circle that seprate them?
This problem took me 6 hours. I came up with a very lame O(n log n) solution. It can be done in O(n) by converting this problem to a linear programming problem.

I strongly encourage people take CSE 555, or CSE 355 if you want to undergraduate version.
CSE 555 is like taking Skiena's CSE 373, just more specialized in computational geometry problems.

Skiena's CSE 373 is nice. I would enjoyed it much more if I know less algorithm materials. I actually got dynamic programming and other techniques in CSE 392 first. Then when it is explained in CSE 373, I already know them. He explain things really well. Especially turning other people's undecryptable rambling into something really clear.

CSE 392 is a must if you are a newbie to competitive programming competition and knows little about algorithms. This is the course where I first learned backtracking.(I did backtracking in high school. I just never systematically thought about the backtracking idea). I also get the dynamic programming from 392.

I regret taking AMS 311 without Mitchell. Ahh, if only Mitchell also taught AMS 311 this semester.

Currently I'm drafting summer study plans for people, so they can become a good ACM-ICPC contestants if they put in the efforts. I'm looking back at what did I do such that I'm in the place I am now.

Query a DAG with boolean constraints on reachability

Mgccl — Mon, 03 May 2010 23:19:39 +0000

I came up with this problem when I was frantic about DAG based taxonomies.
I have the problem up on stackoverflow.

How to do the following kind of queries efficiently.
The query syntax can be built up recursively(ha, CSE 541 at work).

There are a few connectives
unary connectives: not, reachable
binary connectives: and, or
A query is a set of formulas constructed recursively where A and B are formulas, a is atom. Every atom is a formula.

a
(not A)
(reachable a)
(A and B)
(A or B)

For a DAG implemented as a adjacency list. We want to implement a procedure v(A), such that it evaluates the same as the following function f(A).
U is the set of all vertices.
Let R(a) = the set of all vertices reachable from a
Then the function f(A) such that

A possible expression would be ,

A native implementation of itself is the procedure we want. A analysis we can see it can take time, where is the amount of set connectives and is the amount of reachable used.
is with a DFS and sorted. The rest of the set function are if returns a sorted set.

The question is does there exist a better approach such the complexity is lower? I can see there are lot of overlaps during the search. I have a feeling is the lower bound.
What if an auxiliary objects that take space is allowed. How is that going to change the lower bound? m is the amount of edges.

GConf problem, root partition too small

Mgccl — Mon, 03 May 2010 22:04:38 +0000

Recently my box suddenly have problem with GConf.
In the end it having errors like

Failed to spawn the configuration server (gconfd): Failed to contact configuration server; some possible causes are that you need to enable TCP/IP networking for ORBit, or you have stale NFS locks due to a system crash. See http://www.gnome.org/projects/gconf/ for information.

There is a detail thing, saying error code 6 or something. I can't reproduce it because I have solved the problem.

I tried everything online, Non of them worked, include delete .dbus, delete .gconf and .gconfd(which killed all my preferences, but that doesn't matter, I don't have that many anyways).
This took me hours and upon hours.

So I was checking some logs and stuff, not exactly related to gconf, and found there is a line saying not enough disk space to create something.
I ran df, and my root partition is 0% free.

I did "sudo pacman -Scc" and get root partition to 73% free.

Reboot, the problem is gone.

Next time I need to create a larger root partition. My home partition is only 2% used.