Mgccl's Ivory Towerso tired

Around a year ago, I had a vision of a problem database(it's like wikipedia for problems). I made a prototype on top of Drupal.
It was nice, but there are many problems, one of them is to extend the attribute of every type of problem. This is not a difficult task. Drupal's CCK fixed this up rather nicely.
The relations between every problem are hard to map out. Soon I found Drupal's limit, and abandoned it for the project.

I try to write my own program for it. I found in order to make each type of problem have flexible set of attributes, I have to re-implement Drupal's CCK in my program. There must be a better way. In the end I'm convinced that a relational database doesn't suit my need, because of following reasons.
1. Each set of problem can have different set of properties. Some doesn't present in other .
2. Relational database are horrible for graph structures. In fact, relational database are horrible for any structure that can't be presented as a table naturally.

Then I found CouchDB and MongoDB. Both are document databases, it address problem 1 by schema free design. Problem 2 it cannot take care naturally, thus I have to write the code to handle the graph structures. It's still going to be slow.

Just today, I found there are graph databases. Like neo4j. neo4j store everything as graphs. The relations are mapped out as graph in the database. It is also schema free.
It addressed both problem 1 and 2. Awesome.

Looks like I got everything to build the thing I wanted. Hmm... The technology is as mature as I need.

For some partial reason, there is a need to build relationships between objects. Objects of any kind. For example, math problems. Is a problem generalization of another math problem? stuff like that. It's usually relations between 2 different objects.
Generally, there are 4 kind of relations I need to consider about:
Type 0: Not commutative or transitive.
Ex: Like. I like chicken, chicken like bugs. I don't like bugs and chicken doesn't like me.

Type 1: Commutative but not transitive
Ex: Married to.

Type 2: Transitive but not commutative
Ex: Ancestor of.

Type 3: Transitive and commutative
Ex: Same age?

Now I need to find a way to map each kind of relation easily.
Let V be the set of all objects. then
Type 0: is a digraph that maps out every relationship.
Type 1: is a graph that maps out every relationship.
Type 2: is a digraph maps, all the relation can be found by calculating it's transitive closure.
Type 3: is a partition of the set V.

For type 0,1 and 3, insertion and deletion of items are easy.(Move = deletion + insertion).

For type 2, delete an element(or relation) need to be defined.
Its either delete 1 relation and remove all a set of other relations because it depend on the transitive property.
Or delete 1 relation, and maintain all other relations in tact.
Delete an object is the same as deleting a lot of relations.

Type 2 is pretty useful. For example:
There is a bunch of sets, we know the definition of each set by it's unions.
We know every set's definition from the union of other sets. For instance
A = B union {1,2}
B = C union D
C = {5,6}
D = {5,7}
E = {3,4} union D
then A = {1,2,5,6,7}
Each set becomes a object.
Union A and E = {1,2,3,4,5,6,7}
if we do it naively, by finding A then find E. then there is a need of 5 unions. Since we already know E contains D. only 4 unions are required.
When there is a lot of unions, and it's very likely a large amount of them will overlaps, having a nice program to do type 2 relations can greatly reduce the amount of unions required.

This sound like something fun to do for CSE Honors project in my senior year. but I have a feeling someone did it before.

Problems are here.

Here is what happened:
1. I don't get No.1 at all...
2. Easy problem, cost me 5 tries because I forgot to end the lines.
3. I got WA, but I got over the test case and few other cases. There must be something I didn't think of... humm...
4. EZ, again, one of the bash able problem.
5. HOLY Shit. I totally know how to solve this problem except I can't put it in practice. Yes, find the convex hull. order them using slopes, then find the distance. Other than I can't think of a way to find convex set in 2 seconds, so I chose to bash some ez problems.

I got 2 out of 5 problems. No.1 in Freshman/Sophomore grade, beat another person by 2 minutes.
A guy got 3 out of 5 problems, he is a graduate student.

Awesome. I won a free book. The Algorithm Design Manual
by Steven Skiena(I would call him the coach of the SBU's ACM team)

Now I'm going to do my MAT 205 homework. Damn I'm getting raped by all those homeworks.

As a CS major who want to concentrate in the more theoretical stuff. (remind me of a song, Theory Girl). I need to think of 4 introductory(doesn't mean it's easy...) books that can widen one's view.

Why 4?
I'm a superfluous person at times, especially when I'm trying to make puns or word plays.
It's a Chinese word play with allusions, anyone who read Chinese, Hong Kong's (MANLY!!) manga Fung Wan and do OI,ACM would get. (yeah, it is esoteric, k thx bye.)
Here it is.

只有切题万道,范围包罗万象. 才能得到隼人天隐的逆天绝学"万道森罗". 可惜,还是被大当家的"四大皆凶"击败 故事告诉我们. 不看SICP,TAoCP,CLRS和Concrete Mathematics还是不行的.

To make it simple, I'm trying to express that doing thousands of problem is not enough, there are still 4 books required to make one strong.
Yeah, and I have listed them.
(links with kickbacks)

SICP: Structure and Interpretation of Computer Programs
The purple book!
I haven't read the book yet, but just watching those video lectures I have improved greatly in how I can think about problems.
Lisp(in SICP, a variant, Scheme) is so powerful. It's like seeing the world from the top.
That's not surprising. Lisp is originated from a math paper. Using Lisp is like program the world with math! WOW.

TAoCP: The Art of Computer Programming
There is a saying in the Chinese OI community.
Everyone need to have a set of TAoCP. Not for reading, but for worshiping.
It's written by Knuth. That says it all. Knuth is like god in CS. GOD.
This is the only book I haven't touched yet. The OI community liked the book. So I believe this is quite useful.

CLRS: Introduction to Algorithms

A new edition is coming out in September 30th!
I have the 2nd edition and I did some of the excercises in the end and I have improved significantly.
It is a hardcore introductory book!
It's more like a reference book than a textbook IMHO.

Concrete Mathematics: A Foundation for Computer Science (2nd Edition)
This is the first of the 4 books I got in my hand.
It is hilarious. If you are seeking "WHY is this dude always make lame math puns?". It's from this book.
In the side of every page, there are comments from Stanford students or TA's apply to the section of the book. Some of them are epic math puns.
Other than it is funny. This book have served me well. The skill I have at manipulating sums come directly from this book.
This is the book got me good with math and arosed my interest for it. Highly recommended even if you are not doing CS, as it is the one of the best book for discrete math.

Here is a more formal view of the last problem.

There exist a undirected graph . For each vertex , the edges of are .
.

Let there be a sequence .
Let , , Where .

Can you provide a algorithm to find the shortest sequence if , given and .

Clearly the lower bound for the size of the sequence is .
I think the upper bound is .
Of course the algorithm is what's important.

I will leave this problem behind because I have to do calculus.

BTW this is a NPC problem.