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

-

## closed as not constructive by gnat, Giorgio, thorsten müller, GlenH7, Martijn PietersApr 20 '13 at 22:36

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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

-

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.

-

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.

-

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.

-

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

The Halting Problem

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

-

Automata Theory and FSM. :-)

-

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.

-

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

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

-
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

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

there are only three numbers that matter:

• zero
• one
• many
-

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.

-

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.

-

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.

-
Thats quite a bit more than one bit. –  user1249 Dec 8 '10 at 22:43

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.

-

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
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. –  Anna Lear Dec 7 '10 at 13:56