# What is the one bit of computer science theory I should know? [closed]

Speaking as someone with an Electronic Engineering rather than Computer Science degree, what is the one bit of computer science I should know to make me a better real world programmer?

(By real world I mean something I'm going to use and benefit from in my day to day job as a programmer - for instance I'd suggest understanding database normalisation is of more practical use than understanding a quick sort for which there are lots of libraries).

• 1 (sorry, I had to) – haylem Dec 7 '10 at 14:11
• oh, or the most significant one! (I'll go now...) – haylem Dec 7 '10 at 14:11
• Theoretical Computer Science stackexchange confirms what everyone else here mentions: complexity, data structures and algorithms. cstheory.stackexchange.com/tags – chrisaycock Dec 7 '10 at 16:06
• I feel the need to object to this question. There isn’t “one bit” that would be sufficient to learn, and what’s more, there isn’t (IMHO) one “most important” bit. There are several aspects that are (again, IMHO) equally essential to CS. So I think that while the answers to this question may may be interesting, the question could have been formulated better. – Konrad Rudolph Dec 7 '10 at 16:09
• If you didn't already have your eeng, I would have said boolean logic and/or discrete number theory. Nearly every if and loop statement ever written uses a subset of those two areas of study. – Steven Evers Dec 8 '10 at 22:46

If I have to choose just one bit, which is a difficult decision, I'd say go for the Big O notation. Understanding the implications of O(n), O(ln n), O(n²), O(2^n), O(n!) helps you to avoid a lot of expensive mistakes, the kind of which work well in the test environment but disastrously fail in production.

• +1 and I'd say that more important that just knowing that O(n^2) is worse than O(lg n) (for example) is knowing how to derive the Big-O for a given piece of code. – Dean Harding Dec 8 '10 at 0:24
• Disagree strongly. This stuff is relatively trivial, and there are more interesting topics in CS. Also, I think most people think about complexity intuitively, although they might not call it complexity and they might not call it quadratic, exponential etc. – Magnus Wolffelt Dec 8 '10 at 22:41
• Magnus: In my experience, most non-programming people do not think at all about complexity, they intuitively assume O(n) for all problems. – user281377 Dec 8 '10 at 22:48
• I've yet to need this formally. – CaffGeek Dec 9 '10 at 17:07
• Chad: There is nothing about the Big O-notation that is overly formalistict, but without names for things, you can hardly think about those things, let alone talk about it with your peers. – user281377 Dec 9 '10 at 17:44

This is a question, everyone will have a different answer on. I would say: complexity theory is the most important piece, that you don't directly learn as a programmer anyway (like algorithms and data-structures), but what may impact your work. It helps if I know, that a problem is has cubic complexity, I know that it will scale badly if the problem size is increased.

• I would add that it helps a lot to know if you are solving a problem that can easily be restated in a simpler language. – philosodad Dec 7 '10 at 18:36
• Complexity is important as a concept, but actually calculating it is often not. Understanding what is less complex is the important bit. – Bill Dec 8 '10 at 15:28
• @Bill: Exactly. But that part is the one thing you don't necessarily get through practise. The theory is very helpful on that part. – Mnementh Dec 8 '10 at 15:34

Learn about data structures, algorithms and complexity.

Not too much just to get an understanding that a machine is not a magic box with unlimited power. You can't throw anything at it and expect it to crunch it in milliseconds. It has limits you know. You need to learn to not test them out with your code.

Also have a look at common approaches to solve particular design problems in programming. Design patterns namely. Don't worship them just take the ideas they communicate.

Knowledge of database modeling is essential as well.

After that it's just different programming languages, frameworks and libraries that implement or let you implement the core concepts. Pick up whatever you like and practice with those.

• Specifics - there are a lot of algorithms and data structures. – Jon Hopkins Dec 7 '10 at 10:10
• Just the basic ones to get an idea of the things. Pick up some not-too-thick book and work it through. – user8685 Dec 7 '10 at 10:16
• Thats quite a bit more than one bit. – user1249 Dec 8 '10 at 22:43

This is a bit of a difficult question.

All aspects of Computer science are important in one way or another.

In terms of what you will benefit on a day to day basis, probably a generalised overview of how your code works "under the hood" from code to CPU.

Understanding Big O Notation is important, and also understanding how your code may be executed is also very important in real world situations.

Yeah, This kicked me into thinking for hours.

NO LIST

1. Big O(n) notation. Hard to put it here but No, we can intuitively work out inefficiencies and compare different set of procedures without having even remotely heard of asymptotic algorithmic analysis.

2. Functional languages No, A single family of language is just one approach to thinking about problems. Why only this bit should matter?

3. Halting Problem Some are just too specific and people have lived life without knowing they existed.

4. Listen If you are not listening then you live in world of your own. Not necessarily detrimental!

5. Software Development Cycle Nah! We can still bumble our way to some incredible software or solo heroic effort.

6. complexity theory I guess this could be it but without all the formalisms

That one bit of idea from Comp Science

I would say - "Abstractions Abstractions Abstractions ...". Learn about it. See examples around it and learn how to build using it. It is every where. The whole of computer science, engineering and applications looks like layers upon layers of abstraction.

Once you know this, you start learning to look around well.

When you see some one using list insertion in python and not append, you smile because you know that python lists are built using array abstraction where insertions are costly and append cheaper.

This is but one example.

• +1 for an answer you've obviously given a lot of thought to. – Jon Hopkins Dec 9 '10 at 9:39
• just a comment on your comment on the Halting Problem: "Living life without knowing existing" is true for ANY computer science topic. – user1249 Dec 9 '10 at 9:50

Automata Theory and FSM. :-)

Competitive use cases of data structures.

There are situations where a map with red-black trees is required to guarantee performance and others where you cannot use an array, again to guarantee performance. Knowing when to choose what data structure is an invaluable skill.

there are only three numbers that matter:

• zero
• one
• many
• but doesn't that imply that '3' also matters? – Javier Dec 7 '10 at 14:26
• It's supposed to be zero, one, and infinity: en.wikipedia.org/wiki/Zero_One_Infinity – Thomas Owens Dec 7 '10 at 14:32
• @Javier: 3 is a subset of many – Steven A. Lowe Dec 7 '10 at 14:54
• @Thomas: says who? – Steven A. Lowe Dec 7 '10 at 14:54
• @Steven My understanding might not be 100%, here, but I think the idea is that you have none of something, a single thing, or the number of things that you have should be unbounded. If you aren't limiting to no or one instance, then you should not limit the instances. However, I'm not entirely sure WHY this is the case (I'm only vaguely familiar with the Zero/One/Infinity concept). – Thomas Owens Dec 7 '10 at 15:30

The most important thing I learned in CS (and as a developer for many years and as an architect) is the ability to break a problem down based on volatility and not on function. All good designs isolate and encapsulate volatility. All good developers/architects do this intuitively even if they have not formalized it in their thinking. A huge reason for project failure is the failure to break a problem down on the basis of volatility and encapsulate it. A failure to encapsulate volatility inevitably leads to run away complexity and project failure.

• What do you mean by volatility exactly? – amara Aug 26 '11 at 22:01

The Halting Problem

The fact that computer related problems exist that simply cannot be solved by a computer.

You should know enough automata theory to be able to know where the problem you're dealing with falls in the hierarchy of formal languages. From that, you can figure out a few important practical uses, like why you shouldn't use a REGEX to parse HTML (HTML needs a context free grammar to describe it), and why it takes so much longer to compile C++ as opposed to Java or C# (C++ requires a Turing machine, while Java and C# can be described with context free grammars).

The most important tiers of formal languages are, from weakest to strongest:

1. Languages that can be parsed by a finite automata, or a REGEX (REGEX implementations with backreferences are more powerful than this category, but they still can't parse everything in category 2)

2. Languages that can be parsed by an automata with stack memory, or a context-free grammar.

3. Languages that can be parsed by a Turing machine, or an automata with random access memory.

• Um, no. A regular expression parses a regular grammar. That is exactly the category of grammar that can be accepted by a finite state automata. And a 'Chomsky Grammar' doesn't refer exclusively to the context free grammars, which is what stack machines process. – philosodad Dec 9 '10 at 4:36
• @philosodad - Context free grammar is more precise, and I've updated the post to use the term. I don't understand your issue with what I said about regular expressions. – Dan Monego Dec 9 '10 at 14:40
• @Dan - My issue is that a regular expression is precisely as powerful as a finite state automata, and if you can parse ANY deterministic context-free grammar with a machine than you can parse ALL deterministic context-free grammars. – philosodad Dec 10 '10 at 4:50
• Or, to be more precise: either you need a stack or you don't. If you do need a stack to parse a language, then you must have a stack to parse the language, and therefore, if a language requires a stack to parse it, you can parse that language. – philosodad Dec 10 '10 at 5:23
• @philosodad - There are two types of regular expression - regular expressions in theory, and regular expressions as implemented in software. You're correct about theoretical regular expressions, but most implementations have several features beyond their theoretical basis, and can match some non-regular languages, like a^n for non prime n. Because this is a thread about theory in practice, I went out of my way to mention that there is a difference between the formal definition and the one used in the wild. – Dan Monego Dec 10 '10 at 14:46

Well, I could give you a dull answer: automata theory, and information theory.

Or I could tell you what I learned from a hardware consultant a long time ago:

• "Good Enough" isn't good enough.

Software Development Life Cycle is something I'd suggest knowing if you don't already. Granted this was introduced in a second year Computer Science course and is something used repeatedly within software projects. This can be useful to get a general idea of how does a project go from start to finish, though if you want to more in-depth there are methodologies like Waterfall or Agile that you could study to get more specific knowledge.

• Murphy's law: Anything that can go wrong, will go wrong – Richard Dec 7 '10 at 15:29
• It's not CS theory, but this is an excellent answer. – justkt Dec 7 '10 at 16:13

## Programming

From the Department of Mathematics and Computer Science Hobart and William Smith Colleges comes Computer Science 124 Introduction to Programming:

Topics include control structures, objects, classes, inheritance, simple data structures, and basic concepts of software development.

If you can't program, you're not going very far in real world computing.

And, yes, I've noted that you are programmer. This is to improve your overall knowledge of programming theory and what other approaches there are available to you.

Is programming Computer Science as we know it?

In response to the comment from @Thomas Owens, who pointed out (quite rightly) that programming is not strictly Computer Science, I'd like to quote from Wikipedia's Computer Science article:

... the focus of computer science is more on understanding the properties of the programs used to implement software such as games and web-browsers, and using that understanding to create new programs or improve existing ones ...

Thus, as I read it, by programming you are demonstrating your understanding of programming theory. This should in turn help you to create simple, elegant code that is a joy for others to work with.

• Programming isn't CS theory. In fact, I could easily argue that programming isn't computer science at all. – Thomas Owens Dec 7 '10 at 14:33
• @Thomas Owens I've updated my answer to back up my claim that it is valid. Could you review it and let me know your thoughts? – Gary Rowe Dec 7 '10 at 14:43
• Still don't think that programming is CS. Programming MIGHT be useful to a computer scientist who wants to implement an algorithm or data structure, but topics in CS theory (from my Intro to CS Theory book, so there are probably more advanced topics as well) include logic, automata theory, graph theory, computability, computational complexity, and analysis of algorithms. I would also say that programming languages (the theory behind the design and implementation of a language) is also part of computer science. However, you don't need to be able to program to be a good computer scientist. – Thomas Owens Dec 7 '10 at 14:49
• @Thomas Owens I see your point, and (puts on purist hat) I agree. However, the OP is asking for one bit of CS that would help him in the real world. I hold fast to my opinion that programming theory (as implemented in good code) is that one bit. I've edited slightly accordingly. – Gary Rowe Dec 7 '10 at 15:00
• Yeah. From CS, I would say understanding programming languages and paradigms might help (especially if you are implementing DSLs, but knowing many paradigms like procedural, functional, OO, logic just helps in software development). Understanding algorithms and data structures also helps you choose the right one(s) to solve your problem in the most efficient way. Automata theory might help (I worked with a system that was a giant FSM once, but I don't know how common that is). So I would say data structures, algorithms, and PL theory would be the most useful things to know from CS. – Thomas Owens Dec 7 '10 at 15:27

I have to disagree with Konrad Rudolph. There is "One bit" of computer science you should know to make you a better "real world programmer." If you take nothing else away from the answers you're getting here, at least consider this- Satisfying the requirements is NOT the same as satisfying the client! The end users will ALWAYS try to use your program in a way you never thought of or coded for. ALWAYS, ALWAYS, ALWAYS.

Therefore, in order to be a better programmer, you must first LISTEN. Listen to the client. Listen to their needs. Listen to their wants. And especially, listen to their level of "techs-pertise." I can't tell you how many times I've seen a project built that was exactly what was requested, but not at all what the client actually neeeded. All because the programmer gathering the req's wasn't really listening.

Something else you can take away is, unless you've got a background in UI design, get someone eles to design the UI. I can ALWAYS spot an app where the UI was designed by the programmer and not an expert. What is logical and makes sense to you will not make sense to the client. And, if your clients aren't tech saavy, (and who's are?) then your "functionaly correct, but esthetically ugly" solution will be met with the warmth of skunk at a dinner party.

• This answer doesn't deal with CS theory, which is what Hopkins asked about. – James Dec 7 '10 at 17:57

Functional languages!

Learning functional languages makes you think in terms of expressions, rather than steps and named mutable states (variables). This has a significant impact on your ability to effectively deal with every-day programming problems - especially now that almost every popular language has functional features.

Algorithms and complexity theory is also important, but it is somewhat less interesting in that it mostly lets you put names on stuff that you usually already knew and could deduce.

That computers are essentially pattern matchers, nothing more. Everything boils down to the Turing Machine - the classic Computer Scienceconcept of explaining pattern maching.

Problem Solving and the desire to continue learning!

They serve me far better than knowing quick sort and database normalization.

• That's not computer science theory, they apply equally to electronic (or pretty much any other form of) engineering. – Jon Hopkins Dec 7 '10 at 10:08
• The way I see it, to take your example into account knowing quick sort just isn't helpful. Knowing it exists and what makes is special is helpful, but is also one google search away if I didn't know anything about it. Knowing any one algorithm isn't helpful either. However, knowing how to create one and interpret one is! Perhaps if I could change my answer, Complexity is probably the most important. – Bryan Harrington Dec 7 '10 at 10:19
• You can't search for something if you don't know you need it or that it exists. Your answer lists important qualities for a developer to have, but doesn't answer the posed question. – Adam Lear Dec 7 '10 at 13:56