What Computer Science concepts should I know?

What concepts in Computer Science do you think have made you a better programmer?

My degree was in Mechanical Engineering so having ended up as a programmer, I'm a bit lacking in the basics. There are a few standard CS concepts which I've learnt recently that have given me a much deeper understanding of what I'm doing, specifically:

Language Features

• Pointers & Recursion (Thanks Joel!)

Data Structures

• Linked Lists
• Hashtables

Algorithms

• Bubble Sorts

Obviously, the list is a little short at the moment so I was hoping for suggestions as to:

1. What concepts I should understand,
2. Any good resources for properly understanding them (as Wikipedia can be a bit dense and academic sometimes).

Take a look at this blog post by Steve Yegge (formerly of Amazon, now at Google):

• The Five Essential Phone Screen Questions

It goes into some detail about the the five most important concepts that developers should be required to know:

1. Basic programming (including recursion, file I/O, formatted output, loops etc)
2. Object oriented design (including design patterns etc). You should be able to produce sensible OO designs as well as understanding the concepts.
3. Scripting and regexes.
4. Data structures -- lists, sets, hashtables, trees, graphs, and so on -- as well as Big O notation and algorithmic complexity.
5. Bits, bytes and binary numbers -- how numbers are represented within the computer, and how to manipulate them.

You definitely should understand the Big-O notation and Big-O estimations of algorithms - what it is, how it is used, why it is important, how you compare two algorithms given their Big-O estimations, how you build Big-O estimations for the simple algorithms.

I find it a little funny that you're looking for computer science subjects, but find wikipedia too academic :D

Anyway, here goes, in no particular order:

• The relational model: Introduction to Database systems
• Object orientation : Object Thinking
• Complexity and computation theory (think Turing machines and automata): Introduction to theory of computation
• A little compiler design: The Dragon Book, although this might be a little over too in-depth for your needs.
• Operating system concepts: Modern operating systems
• People skills: How to win friends and influence people
• Teamwork: Peopleware
• User interface design: The inmates are running the asylum

Some concepts that helped my development (intellect and code):

• Lexing, Parsing, String matching, Regex
• Memoization
  • encapsulation/scoping/closures
  • caching
• Recursion
• Iterators/Generators
• Functional programming - John Hughes' amazing article had me at "why"

These are whole domains of discrete math, but a serious introduction is required for CS:

• Matrix/Linear Algebra
• Graph Theory

Although lectures and articles by Mark Jason-Dominus are often directed to Perl hackers, I think any programmer would benefit from his clear presentation and real code, especially in Higher Order Perl.

I would say nowadays an understanding of Object Orientated Programming is a must, even if you don’t need to use it day to day.

From this I would also say understanding the most common patterns can also help.

I see several good CS concepts identified but little talk about Math.

I suggest that you look into discrete mathematics. It has a wide range of useful problems starting with logical proofs which help you write conditions in code. Graph theory and combinatorics also help with complex problem resolution and algorithm optimization.

While we are on the subject of math, linear algebra is typically a prerequisite for advance computer graphics classes.

Programmer Competency Matrix covered this in detail, but I'll highlight a couple:

• Data Structures
• Advanced data structures like B-trees, binomial and fibonacci heaps, AVL/Red Black trees, Splay Trees, Skip Lists, tries etc.
• Algorithms
• Tree, Graph, simple greedy and divide and conquer algorithms, is able to understand the relevance of the levels of this matrix.
• Systems programming
• Understands the entire programming stack, hardware (CPU + Memory + Cache + Interrupts + microcode), binary code, assembly, static and dynamic linking, compilation, interpretation, JIT compilation, garbage collection, heap, stack, memory addressing…
• Source Code Version Control
• Knowledge of distributed VCS systems. Has tried out Bzr/Mercurial/Darcs/Git
• Build Automation
• Can setup a script to build the system and also documentation, installers, generate release notes and tag the code in source control
• Automated testing
• Understands and is able to setup automated functional, load/performance and UI tests
• Problem Decomposition
• Use of appropriate data structures and algorithms and comes up with generic/object-oriented code that encapsulate aspects of the problem that are subject to change.
• Systems Decomposition
• Able to visualize and design complex systems with multiple product lines and integrations with external systems. Also should be able to design operations support systems like monitoring, reporting, fail overs etc.

I find graphs and some applied algorithms like depth first, breath first search, shortest paths etc very useful. Object orientation is also a really common concept.

Rule 1: Software is Knowledge Capture. Software means something. If you're unclear on the meaning, spend more time talking to users to understand what they do.

Algorithms and Data Structures are two sides of the same coin. Algorithm depends on data structure, data structure depends on algorithm.

Unlearn bubble sort as quickly as possible. Seriously. All modern languages (Java, Python, etc.) have collection classes that implement a better sort than bubble sort. There are absolutely no circumstances under which you should ever use bubble sort for anything. You should be looking for a collection class that includes a sort method. Better, you should be looking for a algorithm which avoids sorting entirely.

You must learn several languages.

• Programming language (Java, Python, etc.)

• Shell language.

• Database language (SQL)

• Presentation languages (HTML and CSS)

• Other data representation languages (XML, JSON)

You must learn several data structures.

• Sequences (lists, tuples, files)

• Hierarchical (like XML and HTML documents, as well as the basic file system)

• Relational (like databases, and the file system with hard and soft links thrown in)

• Maps (or Indexes or Associative Arrays) including Hash Maps and Tree Maps

• Sets

Plus some algorithmic complexity analysis. Sometimes called "Big O". Why a bubble sort is bad is that it's O ( n ^ 2 ), where a quicksort is O( n log n ).

Well the can of worms is open now! :)
I started out in Electrical Engineering.

Relational Database Design: Keeping track of data is like Arnold in "Kindergarden Cop".
It can be total chaos. It must be controlled.
How to keep your data, in the fewest locations, with the fewest duplications of information. How to keep your data light, and easily accessible. How to control data growth and integrity.

User Interface (UI) Design: This is how the User must access the data we're keeping track of.
Most UIs are designed by developers. Thus, most UIs, unfortunately, parallel the database design. Users don't care about the data design at all. They simply want, what they want. They want to get it easily. Usually this demands great separation from the data design and the User Interface. Learn to separate the "engineering" you from the "southern-hospitality" you.

Object Oriented Programming: Many languages boil down to this format.

Parallel Processing - Multi-Threading: Many processors make the work fast!
Parallel computers have been around for decades. They've been on our desktops for some time now. With the event of "cloud computing", massive parallel processing is not only manditory but also preferable. It is incredibly powerful! There is a lot of job potential for parallel developers.

Understanding Business Rules: This helps you make a lot of your logic, table-based.
Many IFblock conditions can sit in business rule tables. To change the logic, just change the information in a table. Little/No recoding. Little/No recompiling.

Events Supervise...Methods do the work:
Keep things separate in your code. It makes it easier for others to make updates in the future. It also somewhat parallels the Model/View/Controller (MVC) framework.

PJ

For me I got a lot from the following course at varsity

• Project Management
• Human Computer Interaction (Helps us geeks make more user friendly screens)
• Database Design (Including how databases work, transaction logs, locking etc)
• Data warehousing
• Graphics (OpenGL)
• Advanced Algorithms
• Data structures

Things I wish I had done at varsity

• Compiler Construction
• Design Patterns
• Automata theory

LOGIC - I just overstate the importance of logic in programming. You said you did Mechanical Engineering so you must know how much mathematics can make your life easier.

Propositional Logic, First-Order Logic, Second-Order Logic: these are very powerful tools. Probably the most (and only) important things I've learned at university. Logic is like the heavy artillery of a programmer - lots of very complex problems (as well as the less complex ones) become much simpler once you have put them into an organized, logical form. It's like what Linear Algebra is for Mechanical Engineers.

I think a good understanding of how a compiler works is good to know. Aho has the classic book on concepts used in creating a compiler. The title is Compilers: Principles, Techniques, and Tools. Its nickname is the Dragon Book. In order to really understand that book, you should have an understanding of formal languages. Hopcroft has a good book on that - Introduction to Automata Theory, Languages, and Computation.

Some of the OS concepts

 ( memory, IO, Scheduling, process\Threads, multithreading )

[a good book "Modern Operating Systems, 2nd Edition, Andrew S. Tanenbaum"]

Basic knowledge of Computer networks

[a good book by Tanenbaum

OOPS concepts

Finite autometa

A programming language ( I learnt C first then C++)

Algorithms ( Time\space complexity, sort, search, trees, linked list, stack, queue )

[a good book Introduction to Algorithms]

Encapsulation

In computer science, encapsulation is the hiding of the internal mechanisms and data structures of a software component behind a defined interface, in such a way that users of the component (other pieces of software) only need to know what the component does, and cannot make themselves dependent on the details of how it does it

Alot of good responses have been mentioned here already, but I wanted to add a subset of what is important, but hasn't been covered so far.

After 15 years of post-undergrad professional Software development, I find that I regularly use some of the following concepts from in school:

• General OO concepts, and modern programming language features (classes, data hiding, etc).
• Algorithm performance metrics (Big O notation). When designing an algorithm, performing a Big O analysis to determine the cost of the algorith, and looking at more efficient alternatives in bottleneck areas.
• Linked lists and other complex data structures.
• Fast sorting, and different sorting concepts.
• Trees and fast tree manipulation.

If your language/platform doesn't support Garbage Collection, memory allocation and cleanup are critical, and would be added to the list.

I upvote Discrete math. Computer science is abstraction. learning to think like a Mathematician is very helpful.

I also wanted to add to what S.Lott said about languages. Learning a bunch of TYPES of languages is important too. Not just compiled vs scripting. But functional (ML, Lisp, Haskell) logical (Prolog) object oriented (C++, Java, Smalltalk) imperative (C, Pascal, FORTRAN even).

The more programming paradigms you know, the easier it is to pick up new languages when the hot new language comes along!

Strive for low coupling, high cohesion.

(I stole this image from the website linked above)

Try to get an understanding of all levels of programming. From the lowest level (assembly) to the highest level.

Take recursion for example which is an easy feature :) Try to learn assembly and create a program that will use recursion in assembly.

It is clearly a good understanding of Object-oriented programming, good guiding principles like SOLID Principles and following established patterns and practices.

If you look at SOA, or DDD, they all ultimately fall back to some form of OOP concepts.

I would recommend you to get some good OOP books and alos pick a rich language like C# or Java to begin with

OOP by Grady Booch

(PHP, ruby guys please do no down vote me, I am just giving some examples for him to begin with, you can provide your own answers and suggestions here)

Algorithms.

Learning to use a programming language in a descent way is something you can learn as you go, but It's virtually impossible to invent all the widely used Algorithms by yourself.. One really should at least be aware of what can and can't be done with some problems.

For example one simply can't write some programs with bubble-sort and expect it to be considered good, no matter how fine the code is.

To sum it up - take a look at Introduction to Algorithms

No need to master it, just know what's going on...

As a recent graduate from a computer science degree I'd recommend the following:

• As mentioned in various posts Big O notation

  OO Design

  Data structures & Algorithms (can't remember the exact title of the book I used will update if i remember)

  Operating Systems http://www.amazon.com/Modern-Operating-Systems-2nd-GOAL/dp/0130313580

  NP Problems

Structure and Interpretation of Computer Programs. If you understand this book, everything else can be built easily on that foundation. If you have trouble with the concepts in the book, you may be a software developer but not a computer scientist.

I'm not going to tell you any specific concepts to study, but would instead recommend that you do a lot of light reading across a wide range of topics. Don't worry about getting an in-depth understanding of each subject you read about - at this point, it's more important that you're able to recognize what kind of problem you're looking at, so that you can do some just-in-time studying when you're actually faced with it. In other words, it's ok if you don't know how to solve a combinatorics problem, as long as you know enough to look up "combinatorics" when you need to see how many ways you can arrange a set of objects or pick a subset.

Wikipedia is a pretty good resource for this sort of wide-ranging browsing, especially if you're just skimming to begin with. An even better one, especially if you find Wikipedia too academic or inaccessible, is the C2 wiki. (This is, interestingly enough, the original wiki invented by Ward Cunningham).

I think it's essential to understand the basic theory behind multi-threading, without this it can be difficult to even see that there can be a problem, until you're debugging on a live server at 4 o'clock on a sunday morning.

Semaphores, critical sections & events.

No, not bubble sort, quicksort. It's the big-O thing- bubble sort averages O(n^2), quicksort is O(n*log(n)).

I would say below are the most important stuff

• Object Oriented Programming
• Operating System concepts
  • Process and Thread
  • Scheduling Algorithms
• Data Structure
  • Type of data storage and collection, types (linkedlist, hash, array etc.)
  • Sorting Algorithms
  • Complexity of algorithms

Then Go to specific language related stuff. I hope this is helpful!!

I would start with the quote:

> "if the only tool you have is a > hammer, you treat everything like a > nail". (Abraham Maslow)

The most important principle, IMO, is to know many different programing paradigms, languages and inform yourself well about the tools on your disposal. Any problem can be solved in almost any language you choose, be it full blown mainstream language with its huge default library or small specialized language like AutoHotKey. The first job of programmer is to determine what to use according to the specification of the problem. Some concepts provide better approach to topic, whatever your main goal may be - sophistication, obfuscation, performance, portability, maintance, small code size ...

Otherwise you will finish like some of programmers who desperately try to do something in a 1 language they specialized, while the problem could be trivial to solve in different programming context.

This advice goes along with todays tendency for multi-language projects (take web applications for example, which may involve several languages in single application, like C#, JS, CSS, XPath, SQL, XML, HMTL, RegExp.... and even different programming paradigms (for instance, C# introduced recently some concepts from functional programming paradigms, lambdas).

So, the basic thing is constant learning, forever :)

I think 3D-Graphics is something everyone should learn. Or at least how to properly use homogeneous vectors and matrix-transforms.

It can be helpful not only for creating 3d-applications but also in mechanic fields like inverse kinematics on robots, calculating moments and a lot of other stuff.

I didn't fully understand linear algebra until i had read 3d-graphics, one of the best courses I've ever taken even though our teacher was bad.

Since machines with multiple cores (both CPU and GPU) are becoming the standard, I would say to include Distributed Algorithms (from multiple threads to multiple machines). It is critical to understand multi-threading and distributed processing. Sorry that the link doesn't really provide a lot of help.

Software Development Life Cycle - The requirements gathering, design and analysis, implementation, testing, and support and maintenance sequence. This along with methodologies such as Waterfall and Agile where these steps are put into practice is also an important thing to learn.

Anything but Bubble sort:

• Heap sort
• Quick sort

And most importantly: Big O notation so you know why you should use one of these instead of a Bubble sort.

If you are going to teach big-O at least explain that it describes how the time for an algorithm scales with larger inputs - it doesn't mean that an algorithm will take less time.
As an example, building pyramids is O(n), while sorting photographs of them is O(n ln n) at best. So it's quicker to build another pyramid than tidy your holiday snaps.

Students need to have an idea of how long an operation on a register, in cache, in main memory, on disk, on the net takes. Many taught only on very high level languages have no concept.

(this was a comment that someone wanted to discuss)