Mgccl's Ivory Tower

pdb development diary 1

Mgccl — Tue, 16 Mar 2010 07:16:27 +0000

Originally, my idea for the problem database is actually something stored in some common database system, and I create tools to access it easily.

Later I found it's possible to store it like open source programs.

There is no database, it's only a collection of links and a collection of standard interfaces.

In fact, on the implementation side:
Each problem has it's own git repository, acting as a submodule of the problem database. There is a supermodule with links to each git repository, with a basic set of meta data of each submodule to speed up basic operations.

Then there will be a system indexing all the submodules, for searching purposes.

Every user only need a git client to find the newest updates.

Since each problem has it's own git repository, people who started the problem have complete control over who has permission to read/edit the problem.
This also means people can create their own set of problems. It's just another git repository.

The question of storage has been solved.

Now there is a need of some standards, like where should each piece of information be. I will try to figure out later.

There are a few reasons bring open source development idea on contents not a good idea.
Most problems only need to be updated once. The convenience of problem creation matters a lot more than fast problem editing.

My current design are not bad for editing, but creation of a problem manually is a nightmare.
A problem with nothing but a problem statement in latex requires:
First create a directory with the problem ID, move into it.
Then create a directory called "latex", move into it.
create a file called "problem_statement_0.tex", open it, put in the latex code required to generate the problem.
It becomes more difficult if there are other information of the problem that have to be stored in other ways.
Editing is super easy, open that file and edit it like it's a normal tex file.

The other extreme is to aggregate all information and store it in a human editable JSON file. Editing it manually is not a simple task, one have to understand JSON and have the ability to escape strings.

There is a way combine the best of both world, which is to create a user interface allow rapid problem creation. Which I did. I made a (horrible) interface that is good enough for me to get 5 years worth of Putnam problem in JSON format in less than 10 minutes. Then I wrote a program to convert JSON to the directory based form, which means it can be converted to git repositories really easy.

I will release some kind of demo when I get all the Putnam problems + some IMO problems in. There need to be some amount of data for me to actually produce something interesting.

I suck at calculus

Mgccl — Fri, 12 Mar 2010 09:46:59 +0000

Calculus are for engineering(especially physics related) students. I thought a Math/CS majors like me would never use calculus after the completion of the calculus sequence. I don't intend to learn calculus to the point that I can do integrals like my second nature.

Then today I was doing AMS 311's HW 5. It requires immense calculus power. I wasn't aware of how much calculus was required for this course. Now it replaced CSE 541 as the hardest course ever.(CSE 541's midterm is pretty ez, in fact, I feel CSE 541 is really really ez now... as long as I understand the tower of definition and really long proofs)

I should have seen it coming, it's a AMS classes that have to work with continuous functions. AMS don't use analysis to prove thing, they calculate stuff. Calculus is RIGHT THERE.

This is not the first time I noticed how I suck at calculus.

I never got calculus. so what if I got 9 in math placement because of the AP test. If I go and take a MAT 131 final right now I would surely fail.

This lack of calculus skill have struck me at least 3 times since I'm in the university.

1. While doing MAT 305, I found it's impossible to do some integrals without a table of integral around me. I also have to look up integration by parts.
2. People around me who are in calc 1 or calc 2 would ask me calc problems. and I can't answer them without help of mathematica. In fact, why ask me when one can use Wolfram Alpha? I can't provide any more insight than rephrase the question in a way a computer would understand.
3. During Putnam, I skipped any problem has differentiation or integration.

I remember I was having breakfast last semester, and someone gave me this simple limit problem, and I can't solve it even when I have finished breakfast. What a disappointment, people believed I can do MAT 131 level problems because I was in more advanced math courses. No, I just do different kind of math.

I'm sure I can improve my calculus problem solving technique to among the best by finish Demidovich's book of around 5000 calculus problems. I see no point in that though, since AMS 311 might be the last time I will ever really do calculus.

Web design and interface

Mgccl — Wed, 10 Mar 2010 22:26:58 +0000

There are many different websites running on different themes.
Some websites have the same kind of sections, but presented in a different way.
For example, the navigation is on the right instead of left. Recent comment bar is showing on the bottom instead of top or w/e.
Each time I go on a website I have to get used to the interface.
If I'm only going to use this website once, it still take time to find information I need.

Semantic web is nice. Because I can ignore all the web design, and apply my own set of templates on all of them.

Semantic web NOW!

I have to complain because I have nothing better to do. Now I'm happy and going back to study for the midterm.

I wish I can get paid for complaining.

Random: Recording problems

Mgccl — Sat, 06 Mar 2010 03:50:41 +0000

I like to record the problems so I can use them in the future.
I like data to be portable. I should create some standard so I and possibility someone else can use to store problems for really easy manipulation later.(Minimal migration required).

Currently I haven't developed the system I need to manipulate those data. There will be some function map each JSON file to a directory of files.(each resource is a file) Someone going to write it, likely me.
Problems can be recorded with JSON or XML. I prefer JSON.

top level there are the field id, name, output and resources
where id is a unique string(here I use a 64bit integer in hex form).(btw I have this 64bit integer in hex script that generate it for you)
name is the name for the problem. In English or Romanization/translation of the name of the problem.

Output is an array of objects, each have 4 fields: type, format, language, and out. Type can be "problem_statement, sample_in, sample_out, input, output" and others I can't think of.
format include any possible plain text output format that might be useful. I think "latex, html" are pretty much it for now. out is either a string or an array of strings.
Language is the language it is in. Seems reasonable.

Resource field is there to store binary files. It's an dictionary of binary files. Currently I don't need it. It is possible to use it for the future.

BTW JSON is a context free language.

{
    "id": "7455689cc5d35040",
    "name": "Putnam and Beyond Problem 12",
    "output": [
        {
            "type": "problem_statement",
            "format": "latex",
            "language": "English",
            "out": [
                "Prove that $|\\sin nx| \\leq n |\\sin x|$ for any real number $x$ and positive integer $n$."
            ] 
        },
        {
            "type": "citation",
            "format": "plain",
            "language": "English",
            "out": [
                "Putnam and Beyond ISBN:9780387257655 p.6"
            ] 
        } 
    ]
}

Nice.
Of course, it can be XML files.

This will become useful later.
I'm keeping set of problems in some database. So I can keep a queue of problems I didn't figure out the first time by just record their ID's somewhere.

Idea: Interactive problem solving sessions on campus

Mgccl — Tue, 23 Feb 2010 05:02:57 +0000

I found it boring to only solving problems by myself.

Only a few classes I have attended have interactive problem solving sessions, those classes ROCKED.

---List of problem solving sessions I had on campus--- ignore if you don't care---
CSE 150, I think this is the best course I have taken in my entire life. I assume this class is somewhat like classes in AwesomeMath or other math camps. Students engaged and anticipated in solving the problems.
CSE 350, especially the recitation, is similar to CSE 150.

There are two other classes related to problem solving, but not that interactive.
CSE 392. Most of the thinking for the problems are done outside classroom. The class is basically explaining how someone solved it.
MAT 160. I been to the class only twice. It seems to be like: Do the hw, discuss how it is done. Instead of doing it in class. What's good about the class, is there are people who are enthusiastic about solving the problems.

I expect to try MAT 260 and see how it works.

Other than courses, there are 2 other places I had done some problem solving.
Math club. Last semester the preparation for Putnam, the clubbers have done some problems.
ACM practice was also similar.
--------------------end list---------------------

I feel it's not enough. There is a lack of interactive problem solving sessions on campus. Won't it be nice if there is some club that meet sometimes every week and work on some problem collaboratively. Problems of math, computer science and physics nature. i.e. Union of math/cs/physics club and intersect it with problem solving.

Some possible format.
ARML/HMMT team competition like.
People can organize them into smaller groups, working on a set of problems at a time.
Then people explain their ideas.

Seminar like. Someone pick out some set of problem, and direct the flow of the solvers, ask for participation, until the problem get solved.(Similar to last semester's math club)

Just putting the idea out there. I would totally come to events like this.

Revision repositories and text backup

Mgccl — Fri, 12 Feb 2010 20:14:51 +0000

Instead of using cvs, svn, git just for large open source projects. It can be used as a personal system for backups of text files.(that include source codes to essays)

Github gave each free user 300MB of space. Pretty nice. That should be enough for just storing texts, right?
It might be abusing the ToS a little. Github free should be used for free and open source projects. All the files one commit are open to everyone. Make sure only to back up things you allow others to see.

Let's assume one doesn't store the end product the first time they commit their work. And each commit should only create a small change in the work. To be safe, let all the revisions of a file 2 times the size of the original file. Then we have 100MB of space.

For some people, they use only ascii, thus 1 byte per characters. That would be 100 million characters.
I envy people who only know English, because they will never need to use any other language, thus live in ascii world happily. They never have to worry about charset, input method and some software might not support what ever they are going to type.
I digress.
Suppose someone use UTF in some of them. Then it need 50 million characters. Let's not consider them, just consider English and source codes.

Is it possible to write 100 million characters in one's life time?
Sure.
If one type at the speed of one character per second on average over a period of 3 years, it will surpass the limit.

Likely, that's not going to happen, especially if one use their brains before writing down anything. I use lots and lots of scrap papers. My notebooks are scrap papers. I only store information on the computer in electronic format.

The source of all the hw I have done from last semester to now is 0.2MB. All the source I submitted to any online judge this semester is 0.025MB. Certainly I have written other stuff, like my blog posts. Those doesn't require back up because it's in my blog. Suppose those do require backup, I would believe it is less than 0.25MB.
Thus a total of around 0.5MB of original data was generated for a period of around 6 months.

That means I can use github for backup for 100 years if my productivity stays the same.

The amount of keystrokes I had was "6163302", last updated 2010/01/23.(I don't have a linux version yet :() It was on the computer that I use less often after college, but I would believe it contained at least 6 months of keystrokes. Even if all those keystrokes are realized, it is only a 6MB file.
Github is at least good enough for 10 years. At least I can use it until I start to earn money to pay for extra storage. COOL.

If I got a new laptop, or I need to do something on someone else's computer. All I have to
do to sync is a few command line code. Nice.

Some people did all their work in Word or w/e, where do they back them up? Google Docs. LaTeX gave me more freedom because LaTeX codes are plain texts. WIN. That's why I stopped using word. Except I dislike how kile don't have automatic spell check function yet.

How come I'm doing bad in AMS 311?

Mgccl — Fri, 12 Feb 2010 03:57:19 +0000

It should be in future tense, I was right on almost all problems on the last hw I submitted. Those are some classical counting problems.

I'm dying from AMS 311 hw no.2(due tomorrow). I'm getting almost every single question wrong during the first attempt and require extensive amount of time to correct them in a period of 8 hours with help of various people(#math in freenode). I need to find a systematic way to deal with this when I find some time.

It's still possible there are errors in my extensively corrected hw.

What's the probability of being dealt one pair from poker?(a,a,b,c,d. where a,b,c,d are distinct values)

Seven balls randomly withdraw from an urn, find the probability that 3 red, 2 blue, and 2 green balls are withdrawn.

Suppose that n balls are randomly distributed into N compartments. Find the probability that m balls will fall into the first compartment. Assume that all N^n arrangements are equally likely.

I got all those question wrong the first time I tried(and these just tip of the iceberg).

They are suppose to be easy problems, it's hw problem from a introductory probability text.

How can I not get it? I have no problem doing CSE 555 problems(although hard, but at least I don't get wrong answers). I can do MAT 160 problems(btw, they are interesting) with a reasonable amount of confidence. In my opinion those problems suppose to be way harder than the ones in AMS 311.

There is something wrong with my counting skills. I can't count correctly. Inclusion exclusion principle and other counting principles are not what I didn't master. I always have stupid reasoning during counting.

For example, for the balls and urn problem. I thought, there are 12 ways to chose the first red ball, 11 for 2nd red ball, 10 for 3rd red ball and etc. The probability would be . At the moment I found it perfectly reasonable, then I did a calculation. WRONG, it's greater than 1.

Then I realized it's
Interesting how I got the question just before the balls one correct the first attempt.

A forest contain 20 elks, 5 are captured, tagged then released. Then 4 of the 20 elks are captured, what's the probability that 2 of these 4 have been tagged?

That question is almost isomorphic to the balls one. Why do I have a complete different set of reasoning for the 2 problems?

I don't get it.
Do I not understand counting?

What if when I did some probability wrong, but it is something smaller than 1? I will get the problem wrong and only realize it when I get my hw back.

I feel like I will fail the first midterm.
Oh well, seems like I have to do every single problem in the textbook.

I'm using Linux

Mgccl — Sun, 31 Jan 2010 22:27:22 +0000

I have switched to Ubuntu for 2 days now. It's awesome, I'm using awesome window manager. I'm more efficient than usual. I have got wireless to work(not manually), battery status to work, start up programs to work and more. It's a interesting experience.

It's not the first time I used linux, but this is the first time my only machine is running Linux. So I have no way to get back to windows except on library machines.

I shall get a new laptop this November and I will put Debian on it.

I'm using bitlbee+irssi for IM. Meebo when I'm in the library.

Currently I'm learning to use vi, and I just realized how to paste in urxvt.

It still take me a few seconds to do some basic operations. If i do them often enough, I will get used to them.

I'm using Texlive+Kile+graphviz+dot2tex for homeworks. I have already produced AMS 301 hw with directed and undirected graphs! Epic! Soon I will be able to create finite state machine diagrams in LaTeX and in pdf. When I graduate I will have every single hw I have ever written in PDF files! (although I have no idea what the questions are because I never record them, but looking though those work formatted is AWESOME.)

I won't be using Chinese anytime soon. The input method for Chinese on windows system is much superior than the Linux version. I will wait till Google Pinyin have a Linux version.

Something not awesome:
1. SBU access irc requires SSL.
2. Airnet pptp thing is not working. I can't be on IRC while I'm in the library and places.
3. I still use the mouse.
4. Stony Brook doesn't offer Linux version of Maple and Mathematica.

I wish I can get k desktops and use Synergy to connect them all together. I can even use different operating system at the same time. AWESOME.

Computation during sleep

Mgccl — Thu, 28 Jan 2010 03:12:24 +0000

I had a dream a few nights ago, where I was asked the problem 100/6 to the nearest integer. (I was buying moon cakes, 300 for 50 dollars. Yeah, very strange dream)
It was 17. In the dream there was no calculation at all, the answer just popped up.
I woke up, and did the calculation, it was correct.
So where does 17 come from? Did I calculated it subconsciously? I didn't know I can do subconscious calculations. Maybe it's my subconscious memory of some calculation I did a long long time ago.

It could be just a random guess, because I'm sure the answer is between 10 and 20, and 11% chance getting it right.

There are instances when I go to sleep, and dream of more complex problems and solve it. I usually feels like I solved the problem in the dream. When I wake up, I can only remember the important insight. There are times where those insights are correct, and helps me solve the problem.

Do I do computation and math while I'm asleep? Or are those just random guesses that's incredibly lucky?

I wonder if there are books related to this. Google search like computation sleep doesn't help.

Idea: List 2.0

Mgccl — Fri, 22 Jan 2010 13:03:36 +0000

What's the most common type of document you update? I asked a few people, they say source codes. Ha, programmers.

For me, it's just plain text files. More specifically, lists (or "tuples" if you like math) of simple strings with no structure at all.

Lists are useful in many ways. It is SIMPLE. The only thing simpler would be a set of elements. Which is usually represented as a list anyway.

I maintain lists like books I want to read, topics I want to learn, things I want to buy, etc. They are everywhere. Everytime I need to group any objects together, I use lists.
Of course, there can be lot of structure in the above examples. Like I can assign books with what topics it concerns(even if it's just strings, like I can write "mathematical analysis #math", that's how twitter people introduced structure in first place, since twitter is just a list of status), which can make it into a list of lists, or even graphs. That will be a completely different story and it's not a concern in this topic.

Any structure beyond a set and one specific ordering is a overkill in my standards. In fact, most of the time I don't even consider the ordering of the list. Sometimes I just stumble upon a wikipedia article (currently, Language of thought) and want to put it in a list known as "Concepts I have to remember". Ordering comes helpful if I maintain a list like "What I did today"

So I'm going to write some methods and features of a really cool list
Methods: suppose list is similar to ArrayList in java.
1. insert
insert a string to the list. optionally add where to insert it to.
2. search
find and list string match some criteria
3. delete
remove a string
4. update
update a specific item in the list

That's all the operation there is, but it's possible to implement some features on top of it
1. Lists can be accessed anywhere
2. Lists can be edited anywhere, even by more than one person

oh hey, that's all...
wait, I missed out something
3. Manage the list is extremely ez, and can be done by command line, most importantly. Updating the list should be so ez, that "too much effort" can never be the excuse to not write down a list. I heard from one of my friend who says he want to create a list of books to read, but too lazy to write it down. I assume he would like it more if he can add something to the list without delay. I sometimes want to record something down, and then I get discouraged when I realize I have to open a new file, write something, then save, then give the file a name.

Hmm, with those creteria, one can make 500 different implmentations.
This sounds like remember the milk but even simpler. To-Do and task lists are lists with chronological features. That make RTM too complicated for just lists.

How do I maintain such lists? A few current simple options:
1. Use a text editor to edit the list. It's really simple. It's what I preferred before internet is widely available.
It is still inconvenient. I have to find the text file, and double click it, write something and save it. It doesn't allow collaboration
2. Use stuff like Google docs, evernotes and other online services for documents
Inconvenient.
3. FAST Command Line Database
Convenient for insert and search. Organizing the elements is a pain. Collaboration is possible if more than one person have permission to edit the file. It does what it suppose to do though, really convinent to insert and search.

So if we build something like FAST, but data is stored elsewhere on the web(or the cloud), adding a few more features(deletion and updates), it be epic to use. We will see, seems like a ez project I shall do soon.

Something like this would happen.
I set up a account and password, and I call command line window with some hotkey, then write stuff like
l -a books Mathematical Analysis
and press enter, it insert "Mathematical Analysis" into the list books

Non-related rant: AMS 311 is full! I'm no.1 on the waiting list. I hope someone switch out.