This post is includes information about these three parts:

- The hierarchy of computer science problems
- Parts of computer science which I will/might be taking courses in
- Parts of computer science which I might want to work in in the future

Disclaimer: This post is just a formal way of trying to connect all these pieces together using make up stories from my head in a very crude and atrociously inaccurate manner.

### Hierarchy of computer science problems

The hierarchy is as follows

- Computability Theory
- Computational Complexity Theory
- Design and Analysis of Algorithms
- Improving implementation

The first thing to understand before I delve in is what computer science actually does. A definition I found particularly insightful from Philip J Guo, the author of The PhD Grind, who says Computer Science is Efficiently Implementing Automated Abstractions

The thing about computer science that people need to understand is that computer science is revolutionary is that we learned how to control voltages in circuits and built layers and layers of abstraction upon that so that we could have machines/computers that would carry out the instructions perfectly without any chance of error (with some exceptions). Building machines and writing instructions for them to compute has been far more efficient and productive than teaching humans and over organisms to compute because they don’t need food, motivation but only electricity. (Although there has been some headway into cellular computation)

But this automation has a limit. Some problems are undecidable/non-computable. I must emphasis that there is a difference between questions that are undecidable, unsolved and simply have no answer to. This is where **Computability Theory** steps in, which Turing formalized and basically showed the non-decidability (Turing computability) of certain problems when computers barely even existed around WWII. That was the beginning of theoretical computer science I suppose you could say.

I think I will be taking PHIL1680A which is in Topics in Logic: Incompleteness. It’s sort of related to this topic but more on metalogic, or basically how logic is limited by itself as well. This class is more of an experiment for me as I don’t really have any formal training in logic but the topic seems very interesting and relevant to computer science. But I hope to get some formal logic training out of it and some mind blowing insights into logic itself.

Then computers/mainframes started becoming popular, and we started to try to harder and more difficult problems.To each of these problems, there is an algorithm, a step by step procedure for calculations. Algorithms is not a construct unique to Computer Science. (many may disagree but) in fact, most of the math we’ve learnt are algorithms. How to find the sum between two large numbers. You start from the right most digit, find the sum of those two digits, carry 1 over if needed, and proceed to the digits to the left and add the carry. That I think is also an algorithm. So people start developing algorithms, and realize that there are different speeds (runtimes) for each in the best, worst and average cases. So this is **Analysis of Algorithms**. There are more than a dozen ways to sort an unordered list of numbers/strings into an ordered one, each having a different best/average/worst case big-O runtime as it is called in computer science.

I am hopefully going to take cs157 in the spring, which is our algorithms class, learning all the different algorithm classes, mostly likely the deterministic polynomial ones. This class will give me familiarity with all the different classes of algorithms I will ever come across as a commercial software developer if I decide to work as one. It will also be a class heavy in proof writing and help contribute to more mathematical maturity.

But then, during this process of writing and proving the runtime of different algorithms, larger patterns start emerging. Computer scientists started realizing that runtime of some problems took larger than the size of the input list i.e. very famous computer science problem that some of you may have heard of the “The Traveling Salesman problem” , which is given a list of cities and their pairwise distances, find the shortest path that travels to each city once and return to the origin city. Different complexity classes started emerging, with different capital letters and subscripts denoting the differences i.e. P, NP (non-deterministic in polynomial time), EXP (standing for exponential). The sort of big question of this century is whether P = NP? It’s part of the Clay Millennium Mathematics Problems and has huge implications ranging from cryptography, efficiency of our economic markets and protein structure prediction once proved. I am going to paraphrase something my research professor paraphrased heardfrom a talk he attended. “Computer science are in hell, dealing with the complex intricacies and faultiness of computer systems, while mathematicians are in heaven, hidden away by beautiful abstractions. But once in a while, a question from hell, from computer science, P = NP, raises above to heaven that baffles even mathematicians”

I am going to take CS51 this upcoming fall, which is the Theory of Computation class in our department.From what I understand, there will discussion about the aforementioned different complexity classes, and a lot of work in using reduction to go from one formulation of the problem into another one that can be identified as a clear member of one of the complexity classes. There will also be work on automata theory.

Finally, computer science boils down to the implementation part of these algorithms, programming, which is what I think many people mistakenly believe is what computer science is all about. But it must be said that algorithsm are only useful if someone implements them and applies them to some problem. And even the implementation itself varies greatly depending on different languages, understanding of computer systems. The bulk of work in systems, software engineering is on the differences between different implementations and the related performance increases.

I’m TA-ing cs33 in the fall, which is basically this, an intro into computer systems, and low-level programming. I admit my training in this area has been weak and lacking for the most part so this will be a good chance for me to work on.

As to which part of computer science or which part of the hierarchy I want to work in post graduation is a very good question I’m trying to answer as well. Well the first two parts 1)Computability and 2) Computational Complexity pretty much refine me to academia but that doesn’t appeal to me as much. Somehow, I’m not too enarmored with the idea of commercial software development. Software development interviews are very intimidating and being a code monkey is not really what I want to do. This sort of leaves 3) Design and Analysis of Algorithms which can be done in a non-academia setting in certain computational science fields, but again that will and must include some software development. I am also including subfields which require more mathematics i.e. machine learning into this classification. I’m not too sure where I stand on the spectrum yet but hopefully these few courses this year will help me answer those questions. Of course, this completely leaves out things like product manager, business-side roles that involves less computer science.

Jobs is a question that is slowly looming in my head, like a dark overcloud and soon the question and application forms will consume me.

Two pedantic comments: First, I don’t know if I would agree that your hierarchy is actually hierarchical in the sense of the higher items being more fundamental or more important or encompassing the lower items. While I agree that computability theory can tell us about which functions can be computed, and which functions cannot, it is orthogonal to computational complexity theory in the sense that just because a problem is computable doesn’t mean that it isn’t beyond the computational reach of humanity (e.g. the Travelling Salesperson Problem). Actually, I’m not sue about the relationship between the two, but I don’t think I would characterize it as hierarchical.

As for complexity theory and algorithms, I feel like they are two sides of the same coin, in that one categorizes problems into complexity classes based on what algorithms are known for solving them. Again, I think it is more complex of a relationship than you suggest.

Also, for clarity, I would suggest describing NP as the class of problems for which a solution can be verified in polynomial time (non-determinism is a historical artifact that I think only serves to confuse.)

Lastly, I think there are parts of computer science that you somewhat unfairly neglect. Just to name a few, I would add Distributed / Concurrent / Parallel Computing, Programming Languages, Networking, Security. While you could lump these into Systems, each is sufficiently deep on its own so as to be the subject of an entire field of research. While you are probably writing code in each of these fields, it is not at all clear that you are doing software development in the traditional sense, and I think they are a good compromise between the theoretical and applied sides of CS.

I’m getting tired of typing, so this comment is ending now.

Sweet. Thank you. I was actually hoping for a comment from you since I knew you were much more knowledgeable than me in cs. Thanks for pointing out the inconsistencies. I agree with you on my not very rigorous way of defining the hierarchy.

As for the different subfields of cs, I don’t have a lot of experience with any of them so I hopefully will try to take some courses in those fields.

Thanks