97

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).
3
  • 5
    Bubble sorts? Stay as far away from them as you can! Rather learn how quicksort / heapsort work.
    – Carra
    Apr 14, 2009 at 14:32
  • 18
    Yes learn bubblesort. Learn why its terrible. Learn quicksort, mergesort, and all the rest, including their individual weaknesses. But don't write them in production code: call the sort functions provided by whatever platform you are on. Apr 14, 2009 at 15:12
  • @Roger Pate - +1 for you, one should know what an algorithm or data structure is good for, and what it sucks at. Both Quicksort and Bubblesort have the same worst case performance [O(n^2)], but for very different kinds of input, and Bubblesort has best case performance of O(n), where QS is still O(n log n). Of course, if you are considering Bubblesort then you may want to go for Insertion sort instead. Jun 18, 2010 at 22:37

33 Answers 33

63

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

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.
13
  • Nice link. A bit focussed on the unix side, (missing .NET completely) but still nice. Apr 14, 2009 at 12:55
  • Great link - there's a lot there for me to work through, I just wish it had some links to good pages explaining those things.
    – Jon Artus
    Apr 14, 2009 at 12:57
  • The link will be very useful for me to check myself and catch up with the fundamentals. Thanks..
    – rpr
    Apr 14, 2009 at 13:22
  • Agreed, great link. While many of the identified possible solutions are Unix based, the overall concepts involved are very language/platform agnostic. For most programmers, things like recursion, writing ADT such as trees, and bitwise ops are pretty rare however they are an important foundation. Apr 14, 2009 at 13:37
  • 5
    I'd agree with everything except regexes. Those are a nice bonus, but most of the stuff is ground level basics, the foundation upon which everything is built...regexes are great, but I know plenty of great programmers who never use them, and never need to.
    – Beska
    Apr 14, 2009 at 21:16
36

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.

15
  • 1
    You can start with a Wikipedia article I linked to - it's both quite simple and mathematically correct.
    – sharptooth
    Apr 14, 2009 at 12:56
  • 3
    You must have a pretty low opinion of advanced math. I understood this in my first year of college, when I was only part way through calculus.
    – GoatRider
    Apr 14, 2009 at 13:50
  • 1
    Don't forget the concept of NP and when a problem is contained within it, a developer that tries to code a TSP (Travelling Salesman) into each database transaction for a search purpose or some other such idiocy is a major problem =]
    – Ed James
    Apr 14, 2009 at 14:09
  • 2
    You should also know that big O doesn't tell you which algorithm takes less time. Something most CS grads don't grasp Apr 14, 2009 at 16:24
  • 3
    It kind of does. It tells you which one has the best worst-case, not neccessarily which one is 'faster' as that depends on the input set.
    – Ed James
    Apr 14, 2009 at 17:06
30

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:

1
  • 2
    +1 because you mentioned databases, often overlooked in these types of lists but a very important concept for any well rounded CS graduate to know. Apr 14, 2009 at 15:16
14

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.

10

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.

10

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.

1
  • 1
    If I had to pick only one it would be discrete mathematics. It's pretty much CS 101. I'm hard pressed to think of an area or paradigm in general programming that isn't touched in some way by DM. Jun 18, 2010 at 23:25
8

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

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.

4

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

4
  • For the record, I'd never actually use a bubble sort! I just found learning how it works to be an interesting experience, and figured that there are a few other such algorithms that people should understand well enough to write in their language of choice.
    – Jon Artus
    Apr 14, 2009 at 12:54
  • There are innumerable algorithms. Most of them bad. Some of them good. Bubble Sort is simply bad. Buy ANY book on algorithms and move on.
    – S.Lott
    Apr 14, 2009 at 13:26
  • Just nit picking, but Quicksort is worst case O(n^2). I only point it out because I think understanding why this is true is a valuable educational exercise when studying fundamental algorithms. Apr 14, 2009 at 15:23
  • For quicksort, yes -- an important exercise. For bubble sort, the only thing is to see how truly bad an algorithm it is. Understanding typical vs. worst-case is important in general.
    – S.Lott
    Apr 14, 2009 at 15:42
4

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

3

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
3

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.

3

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.

2

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.

2

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!

2

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]

2
  • auto meta? - surely "automata" as per the first edit. Apr 14, 2009 at 13:33
  • Oops! bogged down to spell check I guess. I will correct it. Thanks.
    – aJ.
    Apr 14, 2009 at 15:54
2

Strive for low coupling, high cohesion.

low coupling, high cohesion

(I stole this image from the website linked above)

1

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.

1

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

1

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

1

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.

1

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

1

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

0

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.

0

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

0

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

0

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 :)

0

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.

0

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.