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

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.)

Comments URL: https://news.ycombinator.com/item?id=6223168

Points: 1

# Comments: 0

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...

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

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...

Comments URL: https://news.ycombinator.com/item?id=6191901

Points: 2

# Comments: 0

Comments URL: https://news.ycombinator.com/item?id=6112522

Points: 1

# Comments: 0

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

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