Thinking Like a { Computer Scientist, Mathematician }

As a Computer Science and Mathematics double major, a lot of the things I learn in my math classes I can apply in my computer science classes (and vice versa). But there's also a lot of material that I learn in math that's way different than anything I'd ever do in computer science (and vice versa). I've also met a lot of different people in each subject. In this post, I will talk about a recent experience I had when I posed the same question to math students and computer science students. Mathematicians and Computer Scientists think differently, and in some cases they approach problems differently. I will also talk about why some Mathematicians should broaden their horizons and explore the world of computing.

Each week I send out weekly challenge problems on behalf of ACM (and Math Club for that matter). I usually think up and solve these problems myself so the answers don't necessarily exist out on the internet. For last weeks ACM weekly challenge, the problem was this:

 An ascending number is a natural number in which every digit is strictly less than the next digit. What is the sum of all base 16 ascending numbers (in hexadecimal)?

 At first glance, it is pretty obvious that a naive brute force solution that iterates through all the natural numbers n < 123456789ABCDEF and asking each one if it's ascending would take too long no matter how good your processor is. The problem size is just too large.

Both computer science majors and math majors submitted solutions to this problem, but the mathematicians had much more scalable solutions than the computer scientists. The computer scientists that submitted solutions had an algorithm which generated all the ascending numbers (so it never had to check non-ascending numbers). Coding this algorithm is non-trivial, and it works sufficiently fast to solve with this input size for all modern architectures, but it becomes unusable if the problem scales up too far. The mathematicians that solved this problem recognized that ascending numbers a very predictable, and by putting in a little extra up front work on pencil and paper, they were able to come up with a solution that runs in logarithmic time compared to the computer scientists' solution.

This demonstrates an important point that often times it's worth it to put in a little extra time up front and really analyze the problem before attempting a solution. The computer scientists rely on the computer to do the work for them, where as the mathematicians do the work, then use a computer to help with the calculations. In this case and many others like it, I think it pays off to think like a mathematician.

However, in some cases mathemticians can benefit from thinking like a computer scientist, too. Computers are at the basis of almost all scientific computing, among lots other related things. Computers can also be a useful tool to rapidly get an idea of how a particular system or problem behaves, even if it cannot be used to solve the problem itself. Mathematicians should be open minded and accept computers as a valid tool to solve and analyze problems.

I think it's important for computer scientists to not settle for sub-optimal solutions when a better solution clearly exists. Also, I think it's important for mathematicians to accept and utilize computers to help them solve problems. Math and Computer Science are related in so many ways that being proficient in both is a huge advantage when thinking about these types of problems.