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