69
votes

I'd like to consider myself a fairly experienced programmer. I've been programming for over 5 years now. My weak point though is terminology. I'm self-taught, so while I know how to program, I don't know some of the more formal aspects of computer science. So, what are practical algorithms/data structures that I could recognize and know by name?

Note, I'm not asking for a book recommendation about implementing algorithms. I don't care about implementing them, I just want to be able to recognize when an algorithm/data structure would be a good solution to a problem. I'm asking more for a list of algorithms/data structures that I should "recognize". For instance, I know the solution to a problem like this:

You manage a set of lockers labeled 0-999. People come to you to rent the locker and then come back to return the locker key. How would you build a piece of software to manage knowing which lockers are free and which are in used?

The solution, would be a queue or stack.

What I'm looking for are things like "in what situation should a B-Tree be used -- What search algorithm should be used here" etc. And maybe a quick introduction of how the more complex(but commonly used) data structures/algorithms work.

I tried looking at Wikipedia's list of data structures and algorithms but I think that's a bit overkill. So I'm looking more for what are the essential things I should recognize?

21
  • 10
    Voting to close as "not constructive". Any answer will be entirely subjective - there is no consensus on what one "should" know.
    – Oded
    Jul 4, 2012 at 20:16
  • 2
    What part of that locker problem requires input/output ordering? [hint!]
    – Telastyn
    Jul 4, 2012 at 20:17
  • 5
    @Oded there is absolutely a list that I think most people will agree upon for which data structures and algorithms a well versed programmer should know. Jul 4, 2012 at 20:30
  • 6
    @Oded No consensus? What about the syllabus of an introductory course on algorithms and data structures in computer science? Quite well standardized and peer reviewed. A good starting point.
    – MarkJ
    Jul 4, 2012 at 21:33
  • 3
    Alternative solution; assume you charge by the day and have a maximum charge. Attach a paper tag to the key when you let the locker and write the Julian day number on it. When the key is returned, look at the tag to calculate the rent due. Missing or defaced tags attract the maximum charge. The unused keys are stored in a bag (since there is no need to select any particular key from the free keys when letting a locker). Total data structure size: zero bits. All parts of the algorithm are O(1). Jul 4, 2012 at 22:08

4 Answers 4

78
votes

An objective response:

While my initial response to this question was based on my empirical experience as a soon-to-graduate CS student and my projected opinion of the type of people I wanted to work with in the CS field. There is actually an objective (with respect to the subjective opinions of the ACM SIGCSE and IEEE computing societies) answer. Every 10 years the ACM and the IEEE bodies cooperate on a joint publication that details suggestions for undergraduate computer science curriculum based on professional knowledge of the state of the computing industry. More information can be found at cs2013.org. The committee publishes a final report listing their curriculum recommendation.

That said, I still think my list is pretty good.

Original answer below.


What Should I Know?

Minimum

I think an adept programmer should have at least undergraduate level knowledge in Computer Science. Sure, you can be effective at many jobs with only a small subset of Computer Science because of the rock solid community CS sits upon, and the narrowed focus of most professional positions. Also, many people will further specialize after undergraduate study. However, I do not think either are an excuse to not be privy of foundational CS knowledge.

To answer the title question, here is what an undergraduate CS student (the foundation for an adept programmer) should know upon graduation:

Data Structures

  • Machine Data Representation
    • Ones, Two's Complement, and Related Arithmetic
    • Words, Pointers, Floating Point
    • Bit Access, Shifting, and Manipulation
  • Linked Lists
  • Hash Tables (maps or dictionaries)
  • Arrays
  • Trees
  • Stacks
  • Queues
  • Graphs
  • Databases

Algorithms

  • Sorting:
    • Bubble Sort (to know why it's bad)
    • Insertion Sort
    • Merge Sort
    • Quick Sort
    • Radix style sorts, Counting Sort and Bucket Sort
    • Heap Sort
    • Bogo and Quantum Sort (=
  • Searching:
    • Linear Search
    • Binary Search
    • Depth First Search
    • Breadth First Search
  • String Manipulation
  • Iteration
  • Tree Traversal
  • List Traversal
  • Hashing Functions
  • Concrete implementation of a Hash Table, Tree, List, Stack, Queue, Array, and Set or Collection
  • Scheduling Algorithms
  • File System Traversal and Manipulation (on the inode or equivalent level).

Design Patterns

  • Modularization
  • Factory
  • Builder
  • Singleton
  • Adapter
  • Decorator
  • Flyweight
  • Observer
  • Iterator
  • State [Machine]
  • Model View Controller
  • Threading and Parallel Programming Patterns

Paradigms

  • Imperative
  • Object Oriented
  • Functional
  • Declarative
  • Static and Dynamic Programming
  • Data Markup

Complexity Theory

  • Complexity Spaces
  • Computability
  • Regular, Context Free, and Universal Turing Machine complete Languages
  • Regular Expressions
  • Counting and Basic Combinatorics

Beyond

To get into what you're asking about later in your question, if you are familiar with the above, you should be easily able to identify the appropriate pattern, algorithm, and data structure for a given scenario. However, you should recognize that there is often no best solution. Sometimes you may be required to pick the lesser of two evils or even simply choose between two equally viable solutions. Because of this, you need the general knowledge to be able to defend your choice against your peers.

Here are some tips for algorithms and data structures:

  • Binary Search can only (and should) be used on sorted data.
  • Radix style sorts are awesome, but only when you have finite classes of things being sorted.
  • Trees are good for almost anything as are Hash Tables. The functionality of a Hash Table can be extrapolated and used to solve many problems at the cost of efficiency.
  • Arrays can be used to back most higher level data structures. Sometimes a "data structure" is no more than some clever math for accessing locations in an array.
  • The choice of language can be the difference between pulling your hair out over, or sailing through, a problem.
  • The ASCII table and a 128 element array form an implicit hash table (=
  • Regular expressions can solve a lot of problems, but they can't be used to parse HTML.
  • Sometimes the data structure is just as important as the algorithm.

Some of the above might seem like no brainers, and some may seem vague. If you want me to go into more detail, I can. But, my hope is when encountered with a more concrete question such as, "Design a function that counts the number of occurrences of every character in a String", you look to the tip about the ASCII table and 128 element arrays forming neat implicit hash tables for the answer.

Based off these ideas, I will propose an answer the locker problem outlined in your question.


Answer to the problem posed in your question.

This may not be the best answer to your question, but I think it's an interesting one that doesn't require anything too complex. And it will certainly beat the time complexity of using a queue, or stack which require linear time to determine whether a locker is free or not.

You have 0-999 lockers. Now, because you have a fixed number of lockers, you can easily conceive a hashing function with no collisions on the range 0-999. This function is simply h(x) = x mod 1000. Now, [conceptually] construct a hash table with integer keys and the contents of a 1000 element char array as your values. If a customer wants to reserve locker 78 for use, simply put 78 into the hash function (returning 78), and then add that number to the base pointer of the array -- storing a true value at the location pointed to by the offset value. Similarly, if you need to check whether 78 is in use, simply read the value stored at that location and check against true.

This solution operates in constant time for lookups and storage as opposed to a log(n) time storage and lookup in the case of a priority queue backed by a binary tree. The description is intentionally verbose so you can see the higher concepts being boiled down into an efficient algorithm.

Now, you might ask, what if I need to know all of the available lockers, wouldn't a priority queue be better? If there are k available lockers in the priority queue, iterating over all of them will take k steps. Further, depending on your priority queue implementation, you might have to rebuild your priority queue as you look at it all.. which would take k*log(k) : (k < 1000) steps. In the array solution, you only have to iterate of a 1000 element array and check which ones are open. You can also add an available or used list to the implementation to check in k time only.

15
  • 1
    Great answer! I'd also like to add, that you really should be confident in using the predefined functions/datastructures of the language you are using, for example algorithm and stl data structures in C++, or the Java API for Java.
    – marktani
    Jul 4, 2012 at 22:19
  • 1
    Excellent! Especially "Regular expressions can solve a lot of problems, but they can't be used to parse HTML." Jul 4, 2012 at 23:40
  • 2
    The answer was good, until the "problem" appeared. There is no reason, at all, to use a priority queue or hash-table. A simple stack is sufficient. Add iteration to get the full list of free lockers if you wish. Jul 5, 2012 at 6:19
  • 1
    should we add relational database + SQL , knowledege of B+ tree , compiler theory, knowledge hardware organization , knowledge of operation system theory, knowledge of TCP/IP networking ?
    – dan_l
    Jul 5, 2012 at 8:12
  • 1
    I'm skeptical about Design Patterns. Many are useful in some types of languages while useless and/or unnecessary in others. You might also want to add Heuristics under algorithms, and the trie and skip-list data structures. Traditional algorithms/data structures reach a limit on synchronous access but can be beaten by other non-traditional approaches using multiple threads and concurrency. Heuristics can dramatically decrease the number of lookups needed while structures like a skip-list will allow the data structure to be written to without a global lock. Jul 5, 2012 at 22:26
6
votes

The Algorithm Design Manual by Steven S. Skiena seems like the source you are searching. The second part is a classified list of problems with a review of the related algorithms. There is a web version.

2
  • 3
    great book, but don't feel you have to master all of it to really be a programmer. I just bought it recently, and I've been paid to program since 1979. (And yes, I bought it believing I could learn something from it.) Jul 4, 2012 at 23:35
  • @KateGregory I bought the book and couldn't really get the hang of it because I only know high level languages like Ruby and Javascript (no binary trees, linked lists, etc)... I eventually gave up reading it.
    – bigpotato
    Jan 3, 2015 at 1:00
4
votes

There is no "should". A. Get acquainted with the basic complexity classes (linear, logarithmic, etc.) B. Realize that you can do just about anything with a simple array as you can with a fancy data structure like a B-tree. The trick in choosing the appropriate structure/algorithm is lies in balancing performance, expected input size and implementation complexity.

Then there's abstract but immensely useful stuff (though usefulness is not immediately obvious): state machines, graph theory, convexity theory (linear programming, etc).

1
  • 1
    Don't underestimate the importance about knowing when to use what. Because those problems you solved using a simple array will be coming back and bite you just when you are about to reel in that big client and find out your application that worked fine for years slows down to a crawl just because you used a bubblesort instead of a quicksort.
    – Pieter B
    Jul 5, 2012 at 7:52
3
votes

MIT publish free lecture notes, videos, assignments and exam material for Introduction to Algorithms. The lecture titles list the algorithms / data structures covered.

This is a peer-reviewed consensus on what you should know. It's probably a great learning resource, too.

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