Mgccl

Yes. K_{3,3} can be embedded on a torus.

Theory cs could care less about coding abilities. It's never a bad thing to know how to code, but I can go though the entire PhD program without coding a single line of code. (Well not really, one of the professors in my PhD program committee recommended me to do one systems course. other than that, I just prove theorems. )

It's hard for someone in anything remote to math/science without coding anything in their entire undergraduate life.

It's like you say no one can be admitted to a PhD program in US without first learning some English.

1. There is no proof that pi is a normal number. 2. The index of the position takes up space.

mathematician make errors. I want something that can be checked formally.

This is why I think it be important to have a language designed to express algorithms and can be verified of correctness to a certain point.

I haven't done any statistical surveys, in my undergrad years, I find math students are much smarter than the cs majors.

Why do you care about the high demand? We can put that aside for now--if you are a competent coder, you are in high demand...

If you want to have more math, then some subfield in CS theory is the way to go. CS theory have lot of elegant math. complexity, data structure, algorithms, combinatorial optimization, computational geometry. All of them have nice set of mathematical tools you can use. There are also unexpected ones that uses more traditional mathematics, like universal algebra for CSP, functional analysis in graph embedding with little distortion, and topology for computational topology(well that seems obvious, there are certain uses for computational topology, read up on persistent topology, which I guess is part of machine learning now).

Of course, the demands are low for pure theory students. However you can do some practical work. For example http://www.tokutek.com/ , founded by professors who specialize in cache oblivious data structures. Some more practical ones include cache oblivious data structures, sublinear time algorithms, string related algorithms. In Google, there are researchers working on how to optimize ads.

Also, I just don't see how you are going to write non-boilerplate code anywhere. everything eventually become repetitive(unless you use Haskell, anything new become a paper.)

It could mean "2/3 of the men who took the survey admit to watching porn" for w/e survey they had in mind...

How about "Math beyond arithmetic is not important at all for the vast majority of adults today."

See the updated content in the link and the code in here http://www.chaoxuprime.com/posts/2013-08-16-more-algorithms-... Both in Haskell. you can see how to implement it from scratch...

This is a common technique of switching between two algorithms. iirc, I never saw this as an material in undergrad algorithms course.

I wrote on another problem that uses this technique. Mix ternary search and linear search to find the minima of an first decreasing then increasing array.

http://www.chaoxuprime.com/posts/2013-07-27-find-the-minimum...

Google Analytics has a filter system that allow one to use regular expressions of length at most 255.

Sometimes, people have long list of strings that have total length more than 255 characters. frak would be a nice tool for compression.

Since I'm a CS theory person, I can offer some theoretical improvements on the running time and make the problem even more general...

Instead of minimize the linear difference of partition, we might want to minimize the standard deviation, or basically any convex function, and still do it in the same time bound.

One can reduce this problem to find a k-edge path of minimum weight on a complete DAG. The naive algorithm will run in O(kn^2), but we can improve the running time to O(kn) by realize the weight on this DAG has the Monge property. This is very practical to implement.

I posed it as a problem on daily haskell exercise http://dailyhaskellexercise.tumblr.com/post/58060450750/the-....

In this application, k is very large. n is just a constant multiple of k. We can use a theoretically better algorithm that takes n2^O(sqrt(log n loglog n)) time. (this is almost O(n^(3/2))). I doubt it will ever be implemented with speed comparible to the O(kn) solution. See http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/sdarticle_...

I shall post a solution tomorrow since I'm currently touring NYC with my gf...

I thought you would want the most negative cycle, which would be NP-hard to find.

Let's put some algebra/order into this... Bellman-Ford works for any totally ordered group (G,+), such that a+b<=a+c if b<=c.

What logarithm does is just a order preserving homomorphism from (R,*) to (R,+).

true.

irrc there is only a constant factor of time difference between the two.

I see his point, I'm not attacking that. I'm not happy about him didn't do enough research on the topic to find more recent results? Or talk with a real algorithms professor about this before writing up this entire article about this? One line could change those 90% of the comments, just one line about how "This kind of problem is tackled by the field of cache-oblivious data structures."

I really wish the theory and applied side split off into separate departments or divisions just like how math and applied math go their separate ways.

Good article, but it only demonstrate his ignorance on existing cache-oblivious data structures...

I second this.

In programming languages, different paradigms differs as much as how different field in math. So a more concrete analogy would be one jumping from different paradigms of programming languages. Like someone using a imperative language like Java for their entire life and must learn to read a Haskell program.

You are restricted by the set of tools you already have right?

I can't believe how many times a great advancement in theory in different field comes from pure math advancement (or applying pure mathematical results). Say in economics, if Nash didn't apply topology, how would one ever know Nash equilibrium exists. Stable matching, compressed sensing and others also comes to mind.

I have a hypothesis that any field would benefit if we introduce some pure mathematicians to them.

This is not available in New York due to state laws require them to have certain license.

I know who would be perfect for this, except she is still in college so she would need to drop a semester to do this instead.

Do you have any pitch concerning this?

I assume the summer one doesn't conflict with college, but at those times people usually go for internships.

I guess it depend on how one sees something to have value. There are mathematicians only consider research level mathematics have value. There are some subfield of mathematics like algebraic geometry that take years for a math grad student to even understand the language, and takes even longer to produce research paper with value.

I'm on the other end. Once I found that I did all the theoretical CS things easily and doing amazingly bad in all "applied" cs courses. I know it's time to switch out of CS and enter math.

Thanks. hlint-like suggestions are always welcome.

I have no idea what was in my mind when I wrote

  foldr ((:).(y!!)) []　x

This challenge is the first real life program I wrote with Haskell.

https://github.com/Mgccl/mgccl-haskell/blob/master/random/un... (so it seems I don't like to specify the type of my functions...)

Explanation is here: http://chaoxuprime.com/2011/11/a-solution-to-Instagram-engin...

Updated. thx to gwern. Now I know the existence of hlint.

Now, without the type declaration, white space, comments, it's only 6 lines, and looks even better. :)

Just did a Haskell version of spark. It supports in 9 lines of code (exclude comment + empty line) Double instead of just Int. Negative numbers.

https://github.com/Mgccl/mgccl-haskell/blob/master/random/sp...

He does teach the undergraduate algorithms course.