Mgccl's Ivory Towerso tired

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.

I have produced an algorithm that pwns lp_solve at rg data. But fails to lp_solve at k data. It also beat last semester's TA's solution. The s-rg-733-100 can be solved in less than 2 seconds on my machine (exclude IO and preprocessing(O(n^2)) time, java IO is soooo slow.)

In general, my solver is worse than lp_solve, as rg data contains a very special structure which makes my algorithm VERY effective on them.

What made this great leap possible?
Think outside the normal backtracking framework, where one tries to find a sequence such that each index of the sequence can only correspond to something of a global sequence. For example, a sequence of 0 and 1s, where 0 at nth place = not picking the nth set(so the global sequence is a sequence of sets, maybe sorted in some way). What if it is still a sequence of 0 and 1s, but 0 at nth place = not pick some set, and it doesn't have to be the nth set? Yeah, it be a problem, because the sequence itself will not give any information about which set was chosen. Does that information have to be contained in the sequence? Can the information be passed in some other way?

I'm done with this problem, I'm not going to work on it anymore. I literally wake up at 3 am sometimes because I dreamed of some optimization.= = I need a break from all these backtracking and do something else, like CSE 392 HW...

Must take
CSE 220; CSE 260; MAT 310; MAT 319 or MAT 487 independent study on mathematical analysis(Zorich's book).

Maybe:
MAT 534[Algebra 1](for a MAT 313 waiver). It will be the killer class I next semester if I chose it. It means I will be done with the math major requirement except MAT 324 and some math papers.
CSE 528[CG](for a CSE 328 waiver). Someone I know took it and said it's hard, it seems most students in that class last semester are ones who are going for a PhD in CG.

Free to chose:
None.

Ideally the course layout would be
CSE 220 3
CSE 260 4
CSE 528 3
MAT 310 4
MAT 487 3
MAT 534 3

Which gives me 3 credits to spare, idk what to take. Clearly not a DEC(Meh to GPA killars), clearly not a science requirement(it need 4 credits) and clearly not a CSE major requirement(everything else have time conflicts), and clearly not a math class(I can't stuff that many hard math in one semester). So I need something to rise my GPA and FUN to do, maybe something in AMS. nvm, AMS is not fun.

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.

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.