Learning efficient algorithms

Question

Up until now I've mostly concentrated on how to properly design code, make it as readable as possible and as maintainable as possible. So I alway chose to learn about the higher level details of programming, such as class interactions, API design, etc.

Algorithms I never really found particularly interesting. As a result, even though I can come up with a good design for my programs, and even if I can come up with a solution to a given problem it rarely is the most efficient.

Is there a particular way of thinking about problems that helps you come up with an as efficient solution as possible, or is it simple a matter of practice and/or memorizing?

Also, what online resources can you recommend that teach you various efficient algorithms for different problems?

Answer 1

Data dominates. If you design your program around the right abstract data structures (ADTs), you often get a clean design, the algorithms follow quite naturally and when performance is lacking, you should be able to "plug in" more efficient ones.

A strong background in maths and logic helps here, as it allows you to visualize your program at a high level as the interaction between functions, sets, graphs, sequences, etc. You then decide whether the sets need to be ordered (balanced BST, O(lg n) operations) or not (hash tables, O(1) operations), what operations need to supported on sequences (vector-like or list-like), etc.

If you want to learn some algorithms, get a good book such as Cormen et al. and try to implement the main data structures:

• binary search trees
• generic binary search trees (that work on more than just int or strings)
• hash tables
• priority queues/heaps
• dynamic arrays

Answer 2

Introduction To Algorithms is a great book to get you thinking about efficiency of different algorithms/data structures.

The authors of the book also teach an algorithms course on MIT . You can find most lectures here