Mgccl's Ivory Tower

Course Plans for Spring 2010

Mgccl — Thu, 05 Nov 2009 04:12:48 +0000

Next semester will be quite fun. In fact, it should be easier than this year's stuff. If anyone want to have the same section as me, this is a nice way to start.
I can start enroll at November 18th. I hope all these classes are still available.
This is the plan for Spring 2010, it might change.

22 credits
AMS 301-02
CSE 160-L01 (or CSE 220-01)
CSE 160-01 (or CSE 220-R01)
CSE 350-R01
CSE 350-01
CSE 373-01
MAT 160-01
MAT 200-02 (or MAT 310-01 + MAT 310-R02)
WRT 101-06
ITS 102-?

WRT 101 might become WRT 102 if I stay in SBU in the winter.
There might be a challenge exam for MAT 200. I need to look into it tomorrow. So I can take it and replace it with MAT 310-01.
I do want to skip CSE 160. I know it's possible to take CSE 260 without taking CSE 160. I wonder who to contact.

Awesome, every class fulfill at least something for my graduation all the classes I need and there is no conflict. Mwhahahahahahaha.

Commutative, Transitive but not Reflexive

Mgccl — Wed, 28 Oct 2009 19:25:47 +0000

I remember this problem from Apostol's calculus textbook.

Let be a commutative and transitive relation over a non-empty set. Show this proof is flawed:

is also reflexive over the set.

I asked this online like few months ago. One of the people said something about it is related to logic and I should figure it out by looking over the definition of the relations.

I thought of this again, and put it up on Facebook. Thx to Sackel sending me part of this Wikipedia article on equivalence relation.

The empty relation R on a non-empty set X (i.e. aRb is never true) is vacuously symmetric and transitive, but not reflexive.

awesome, now I see how this is not true.
First, here are the definition of the 3 kind of relations.
(reflexive)
(commutative)
(transitive)

but that doesn't mean . So the last step of the proof was wrong.

Logic. I see.

Come on Google, FASTER

Mgccl — Tue, 27 Oct 2009 03:36:26 +0000

Today I missed this "Time management" thing that starts at 7. There are free ice creams there.
Oh, if I have something to remind me what is happening today it be awesome.
Ideas:
1. Temporary tattoo of daily agenda
2. Pen and paper, the paper is linked to my body in some way so I can always find it easily.
3. Cell phone: Blackberry? iPhone? Android?

I'm poor, I don't get cell phones like normal people do.
Of course I will get one soon, like next year.

Work faster Google. I wana AWESOME Android phones by next year.
and GOOGLE WAVE!!!
and CHROME OS!!!

Relations between 2 objects

Mgccl — Sat, 24 Oct 2009 21:43:37 +0000

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.

A puzzle from CSE 150

Mgccl — Wed, 14 Oct 2009 20:00:15 +0000

Professor Johnson gave us a puzzle to think about. He says it have something to do with the material in class.

A island with very logical people. There are some traditions.
No one talk about other people's eye color.
Anyone who have blue colored eyes have to jump into a volcano when they find it out.(I will just say they die...)
There is nothing reflective on the island for anyone to tell what their own eye colors are.
There is a team of researchers got on the island, and they told the islanders "someone has blue eyes" and left. (researchers always tells the truth...:) )
Question, what will happen?

The first 2 response I can think of when I heard the puzzle.
"Everyone dies" and "no one dies."
Both are wrong, of course.

Hypothesis: People only die if they know for certain that they have blue eyes.
It is reasonable: everyone on the island is logical.

Clearly, the first one is false if someone don't have blue eyes.
The 2nd one is also false, suppose there is one person with blue eyes, he can figure out he is the one with the blue eyes because no one else have it.

So I would naturally believe all people with blue eyes dies.
Interestingly, trying to prove that also prove something else awesome.

Let's suppose these people meet together, each time someone calls out "AWESOME", people who knows they have blue eyes dies.
Then after exactly "AWESOME", all of the blue eyed person dies in the same time.
Let the set of blue eyed person be
Let be the predicate
, then everyone in dies on the th "AWESOME"

Base case: is clearly true.
Inductive step: Suppose is true.
Then is also true:
, knows . are still alive at the th "AWESOME". Then , thus , and implies , and he realize himself is in and kills himself.
Hence is true for all .

I thought this thing can be translated into a graph theory problem. My first idea is to map this problem into.
For a -complete graph. For each step, remove edges from vertices, such that the degree of each vertex decrease by . There will be no edge left in steps.
FAIL.

Random stuff don't fit anywhere else:
A joke I saw in Professor Skiena's Algorithm Design Manual. (I love how he have to mention his book during every practice...)
"A computer scientist is a mathematician who only knows how to prove things by induction."

I heard Courtney Gibbons[A blog last updated 2 years ago] is out of math puns for Brown Sharpie[No 3 on my list of most awesome webcomics, right behind Abstruse Goose and xkcd]. I might have a chance to immortalize my math puns if she needs ideas.

Understanding doesn't result forgiveness

Mgccl — Sat, 03 Oct 2009 00:22:59 +0000

Today I was on Facebook, telling someone I have free this Saturday. Since she was asking me when am I free in this weekend for physics help.

My physics skills are lame, but for some reason I can do a lot of physics problems... If you are taking classical physics, just watch this course Walter Lewin.
That's beside the point.

But it wasn't her on facebook, but her boyfriend. He seems a bit too protective. saying stuff like "Don't try anything funny." and then goes to a generalization say how guys tries to do w/e. Then he added "Not directed to you or anything."

As a lame person I am, I thought "Hey, that's not directed to me."

After a while, I realized. He IS directing it to me. Wow, I really should talk to people more so I know what they really mean. I read textbook way too much...

Later I knew the reason and I come to fully understand it. I might do the same thing if I'm in his situation.

Problem. I still can't forgive him.

Why is that? I'm a shallow person? Doesn't that mean I might not forgive something I would do?

Clearly I can see why I should not be happy about this, but how come after understanding the situation, I'm still not happy about it?

Maybe because I feel like I was using my time to do something helpful to others and not getting appreciated.

I have a MAT 305 middle term on Monday and my knowledge on the topic are minimal. I do like to have a high GPA because I have a few objectives that require a high GPA.

I'm not like... "Ahh, I have nothing to do everyday, I'm so bored I'm going to offer free physics help to people for my own entertainment". Sure I'm not in any clubs, but I have ACM and Putnam to worry about. I don't even get good sleep because I'm keep thinking about the problem before I fall unconscious.

By generously offering some of my time to help other's with physics, and I get insulted before hand? How can I be happy?

Not happy, reasonable... before the understanding of course...
but after the understanding, I'm still not happy.
I can't tell my brain what to feel. "I'm not suppose to be unhappy because it is just a misunderstanding. Even though it cause me some unhappiness, understanding is what's truly important."

What would make me happy? A apology from him? idk.
If that make me happy, then I will be really confused.
I rarely care how other people thinks, this apology is just a verification of what a specific person believes.

I guess I will forgive him in like a few hours when I'm getting pwned by my MAT 305 text.
Oh I'm skipping 305 like... all the time... lol. HW and other stuff are up online anyway. I'm better by just reading the textbook.
I always goes "I will never forgive someone for doing something" and forgive them in like a day. Is that a good evolutionary trait?
For me, forgiveness is a result of time not understanding.
Interesting.

Misattribution of arousal

Mgccl — Mon, 28 Sep 2009 20:41:29 +0000

I was watching a lecture from Communication and Conflict in Couples and Families yesterday , and I heard some discussion about misattribution of arousal.
It is not the first time I heard about it, I already noted it in Introduction to Psychology.
Speaking of that, 2 questions pops up.

Why does it still exist?(I usually take up a evolutionary approach for questions like this.)
Does people stop the misattribution when they know such things exist?

For the 2nd question, idk.
I'm going to write about the first one.
Are there any evolutionary significants of this trait? Is it because all organism have this trait since the beginning of the first sexually reproducing organism and never created one without this trait? Or there are organisms don't have this trait and died out.

There are reasons to believe the first is possible. How does one know the cause of something by just knowing part of the information. If something just cut my hand, do I know what caused it initially? or do I have to do a lot of investigation? To my body, the first response is "ahh, it hurts.", then I go and examine the wound, and come up with some ideas of how it happened. Same thing could happen when one is aroused.
A reasonable hypothesis.

2nd hypothesis is also reasonable. Misattributed arousal are usually toward some one really close(as in physical distance). Such arousal can be generated from many ways. For example, if one is scared.
When does people feel scared? when they feel threatened. It is likely there is danger around the person. If it's dangerous, the smart way is to mate with who ever is close.
Sounds stupid? yeah, clearly no one can mate/produce offspring/nurture offspring in the same condition. But that's the general idea, because it speeds up the process of finding a mate.
What if it's other reasons, like ate something that increase heart beats?
Same reasoning would work. The food is probably dangerous to people, and put someone in a disadvantage for the future. Speed up and find a mate makes sense.

Just some random thoughts.

I'm scared of aging

Mgccl — Sun, 27 Sep 2009 16:05:22 +0000

Yesterday I was talking with some CS graduate student(maybe a Ph.D student.) about Google Code Jam's last problem, I come up with some ideas, and he told me, he isn't young anymore, and can't just think of ideas that fast.

Now I'm scared. He is only 27 years old. Will my brain start to function less optimally in a few years?

Oh god, math and CS(I mainly concentrate in the math part of CS) requires a really awesome functioning brain. Will I be able to do things I can do now in 5 years?

btw, it's not only the aging... experience is also hindering ideas.
Some fields, experience are clearly useful. Some fields, experience are not.

Sometimes experience hinders reason.
"Oh, it's always this way." that will happen if one didn't reason the first time one meets something.
humm, that's beside the point.

What if I'm going to be less capable every single year? True, currently I can gain experience in the field, so the overall usefulness of my brain will increase... but until one day where further experience matters little, I will become less capable. When will that day come? in 10 years? 5 years? tomorrow?

My ACM strategy

Mgccl — Fri, 18 Sep 2009 20:28:59 +0000

Usually, what I do is read every single problem.
YES, ALL OF THEM.
I annotate them in this fashion.
1. What's the main technique required to solve the problem
B = Smart brutal force is enough
DP = Dynamic programming or recursion
G? = Possible greedy(because I still fail at proving if something can be done with simple greedy)
S = Specialized algorithms.

2. How hard is the problem
Trivial, Time consuming(as in the amount of time used for coding), possible TLE/MLE.

3. Any thoughts. Sometimes the solution come to mind really quickly. For example, thoughts like these are written down
-recursively remove the outside and check if the inside works.
-It can be greatly simplified with math(yeah, there are such problems where MO people can solve it easily, the code become like... 10 lines..)
-The minimal solution can be obtained though w/e way, thus testing all of them is not required.
-is O(n^3) fast enough? are there anything to improve it to O(n^2)?

IDK if there is any thing like "topics needed to know for ACM-ICPC" in English, I found a few in Chinese here and here. Some have English around it.
Btw, when I look at it...
Wow I heard of all these stuff! I know how to apply them! except I can't write programs in them. LAME.
That's why I do analysis of every single problem in ACM before I do any, so I know what to expect from each problem. Also that means I can just give the problem to someone better than me at it.
so I look around the team...
seems like it is pretty hard for us to do computational geometry problems, and I suck at graph problems. Anyone knows anything about network flow? I doubt that. Oh crap, only 1 month from the regionals. I have to do a lot of study for it.

SBU's ACM qualifying contest

Mgccl — Fri, 11 Sep 2009 04:58:32 +0000

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.