Abstract:
The minimal reading list to become a good programmer.

Created by Peter Kankowski
Last changed
Contributors: Ace and Michael Weller
Filed under General

Share on social sitesReddit Digg Delicious Buzz Facebook Twitter

Recommended books and sites

Please add links to your favorite programming books with a short description.

The goal is to make a minimal reading list to become a good programmer. Feel free to discuss the listed books and propose better alternatives.

Algorithms

  • Introduction to computer programming using LOGO language (free e-book). Very good for an absolute beginner (includes such topics as loops, conditions, procedures, recursion, etc.) You can use an online LOGO interpreter for executing your programs.
  • Algorithms in C (also in C++ and Java) by Robert Sedgewick (printed book). A practical book on algorithms with examples, pictures, and source code. Covers most classical algorithms: sorting, search trees, hash tables, B-trees, graph algorithms, etc.
  • Introduction to Algorithms (lecture notes from MIT). The code is in Python.
  • Wikibook on algorithms (free e-book). It's unfinished, but still useful for learning design of algorithms including divide-and-conquer, backtracking, and other methods.
  • Algorithms and Data Structures by Niklaus Wirth, the author of Pascal language (e-book).
  • Algorithmic Graph Theory by David Joyner, Minh Van Nguyen, and Nathann Cohen (e-book). Under construction (as of March 2010), but already useful as an introduction to graph theory.
  • Dynamic Programming Practice Problems (a web-site with flash animation). Dynamic programming problems and their solutions.
  • Free lectures online. Free university lectures (video lectures, podcasts, and lecture notes).

Math algorithms and optimization

Compression and encryption

Text processing

Compilers and Languages

C/C++

Functional programming

  • Can Your Programming Language Do This by Joel Spolsky (article). Easy-to-read introduction into functional programming.
  • Advanced programming languages by Matt Might (article). What language to learn next: Haskell, Scala, OCaml, and Scheme.
  • Practical Common Lisp by Peter Seibel (printed book, free e-book). A book on Lisp with practical examples (writing a spam filter, an ID3 tag parser, etc.)
  • Structure and Interpretation of Computer Programs (printed book, free e-book). Learning algorithms and data structures in Scheme.
  • Higher-Order Perl by Mark Jason Dominus (printed book, free e-book). About functional programming techniques in Perl. How to write functions that can modify and manufacture other functions. The book could have been smaller, still it demonstrates that "functional" ideas are not useful only in "classic" functional languages.
  • Learn You a Haskell for Great Good by Miran Lipovača (free e-book). A guide to Haskell programming language.
  • The Little Schemer and The Seasoned Schemer by Friedman and Felleisen (printed books). These books will teach you to 'think' in a functional way using Scheme. It has a very unique format with a series of statements and questions, and the reader must implement various functions and algorithms to solve these problems. The problems build upon one another nicely, increasing in complexity at a good pace.

Operating Systems

Computer architecture

Software engineering

  • Programming Pearls by Jon Bentley (also More Programming Pearls by the same author; both are printed books). Covers such topics as choosing the algorithm, making estimates, and optimizing your code. Easy writing style makes this book pleasant to read.
  • The practice of programming by Brian W. Kernighan and Rob Pike (printed book). Contains a lot of clever ideas for improving your code (e.g. using small languages or designing better interfaces between modules).
  • Code Complete by Steve McConnell (printed book). Covers a lot of topics including coding style, coding techniques, testing, debugging, refactoring, and code optimization. Every programmer will find something new for him or her in this book.
  • The Pragmatic Programmer by Andrew Hunt and David Thomas (printed book). Covers the core processes involved in developing software in a professional manner.
  • Code Kata by Dave Thomas (web site). Short exercises to sharpen your programming skills (from the author of The Pragmatic Programmer).

Usability

Code optimization

  • Optimization manuals for x86 platform by Agner Fog. Detailed, frequently updated e-books on optimizing C/C++ and assembly language programs with a lot of useful tips and examples.
  • Hacker's Delight by Henry Warren, Jr. A printed book on bit-hacking algorithms: rounding, bit counting, transposing bits, replacing division by constant with multiplication, etc. The web site contains some interesting info, too, for example, Computist Quiz.
  • x86 Instruction Latency, Memory Latency and CPUID dumps (web site). Instruction latency and throughput tables for different processors (Intel, AMD, VIA, etc.) measured with Lavalys Everest.

Computer graphics

Win32 programming

  • Catch-22 (web site). Win32 tips and tricks, design and implementation of a Win32 text editor in C. It's useful for anybody writing custom controls or doing Unicode text processing in Win32.
  • The Old New Thing. The blog by Raymond Chen.
  • Windows API Tutorial by Reliable Software. Win32 programming with C++ wrapper classes (no MFC).

Similar lists

Peter Kankowski
Peter Kankowski

About the author

Peter lives in Siberia, the land of sleeping sun, beautiful mountains, and infinitely deep snow. He likes to program in C with a bit of C++, also in x86 assembly language, Python, and PHP (on Windows platform). He can be reached at kankowski@narod.ru.

12 comments

ace,

I don't find that "Optimizing C++ by Steve Heller" should be in "a minimal reading list to become a good programmer". I consider it quite horribly written. The table of contest is argument for itself:

Prologue

A Supermarket Price Lookup System

A Mailing List System

Cn U Rd Ths (Qkly)? A Data Compression Utility

Free at Last: An Efficient Method of Handling Variable-Length Records

Heavenly Hash: A Dynamic Hashing Algorithm

Zensort: A Sorting Algorithm for Limited Memory

Mozart, No. Would You Believe Gershwin?

The book is my personal candidate for my "WTF" section ;>

The only O(N) sorting I know of is http://en.wikipedia.org/wiki/Radix_sort. The whole idea is: When the number of keys is small enough that we can count the number of occurrences of each key we can create the result with sorted keys in O(N) by first counting the keys an then constructing the result by storing count times each corresponding key value. This sentence is probably enough to replace at least one chapter from his book.

It's to icky for me to even try to understand what he presents in his book – confusing presentation of ideas, very ugly code for my taste (a typical guy whom I'd never take to program for me!). As I don't believe that he discovered anything new, I guess that his other ideas can also be explained in a few sentences per idea – no need to reading so ugly book.

I'd remove that book from this list. Of course, YMMV

Peter Kankowski,

Thanks, I've removed it. I agree that it's not good enough for the minimal reading list.

Radix sort can be used for arbitrary string keys; it works by counting individual characters in O(Nk) time, where k is the string length (usually a small constant). Sedgewick praises a hybrid algorithm (quicksort + radix sort), which showed impressive results in his benchmarks:

http://www.cs.princeton.edu/~rs/talks/strings.ps

What you described is http://en.wikipedia.org/wiki/Counting_sort, not Radix sort.

ace,

Yes you're right, radix sort is the generalization of counting sort, and I've described the counting sort. So I still must prove that "the whole idea" can be expressed shortly. So I've just stolen from the wikipedia a few sentences and modified them a little: Take the least significant group of bits (LS radix) of each key, then group the whole keys to leave them sorted by that radix, but otherwise keep the original order of keys (sorting must be "stable"). Repeat the grouping process with each more significant radix.

It can be a good exercise to try to describe some principle as short as possible without losing the important details. This also allows us to find the limits – it appears to me that counting sort would work efficiently for files much bigger than RAM (providing that counting of the keys fits in RAM of course), whereas radix can need potentially a lot of passes – so much that k in k * N is too big to be practical?

I'm still somewhat curious to learn what this guy described in the rest of the book (chapter titles certainly don't help much), but I'd really expect the short descriptions (or links to something else in better form).

(digression) I've taken a look at the "strings.ps". Benchmarks are for the computers of that time, MIPS and x86 machines, the fastest being MIPS R4400 on 150 MHz. My current router (ASUS WL-500g Premium) uses MIPS processor on 266 MHz taking only 12 W of power, total. If anybody stumbles to some sources and results of some complete benchmark which run on MIPS then I'd like to cross compile them and run them on WL-500gP. (/digression)

ace,

re radix sort, here's one implementation of radix sort over linked lists, I haven't checked details though: http://www.codersnotes.com/rsort/

Peter Kankowski,

IMHO, the shortest explanations are pictures:

Radix sort chart

Radix sorting is basically a counting sorting applied to each digit. The order of the digits can be MSD or LSD (most significant or least significant digit first).

I'm curious about the Heller's book, too :). Most of his optimizations are not very useful today, but he has some ideas I never found anywhere else.

Thanks for the linked lists example, it's a nice implementation (though, he should make shift a function parameter, not a template parameter).

Marat Dukhan,
I think this site worth adding to code optimization section: instlatx64.freeweb.hu
Contains measured CPUID dumps and latency/throughput of instructions for a large number of processors
Peter Kankowski,
Thanks, I've added it.
ace,
Efficient C code for ARM devices
Chris Shore, ARM

http://www.eetimes.com/General/DisplayPrintViewContent?contentItemId=4210470
ace,
GoogleTechTalks
JavaScript: The Good Parts
presented by Doug Crockford February 27, 2009

http://www.youtube.com/watch?v=hQVTIJBZook
Carlo Boyd,

Two other books that I'm very fond of, covering less common but still useful algorithms:

Managing Gigabytes (Witten, Moffat and Bell). An engrossing description of text indexing and compression, as well as black & white image compression. What's nice is that in addition to describing the techniques used in the associated software, the authors describe the techniques they rejected, and why.

The Algorithm Design Manual (Steven Skiena). A level beyond the usual big-O notation and priority-queue algorithm textbooks, this describes graph algorithms and NP-hard approximation heuristics.

Peter Kankowski,
Carlo, thank you very much; the books look very useful. I've read (and enjoyed) Skiena's Programming Challenges.
Peter Kankowski,

Stop using strncpy already!

http://randomascii.wordpress.com/2013/04/03/stop-using-strncpy-already/

checkedthreads: bug-free shared memory parallelism

http://www.yosefk.com/blog/checkedthreads-bug-free-shared-memory-parallelism.html

Your name:
Comment:

Please ignore this field: