In the spirit of 501 Must-Visit… book series I decided to write this post. My ambitions are much smaller so don’t expect a comprehensive “guide” to computer programming. Nevertheless, I just think it would be useful to show you short programs that demonstrate important computer ideas and techniques.
Fortunately, as software developers, we don’t need to know 501 things in order to accomplish our daily tasks. So my intention is write a list of programs with brief explanation for each one. I will extend the list whenever I find programs good enough to represent important computer techniques. At first sight, the programs in the list may seem random or unusual but they all demonstrate important aspects of commonly used concepts in computer programming. Here goes the first ten in no particular order:
- Nth Fibonacci number – I know, I know… it is too simple. However, I think we often can learn from simple things. Let’s see what there is for us to learn. Fibonacci numbers are one of the canonical examples for recursion. They can be used to explain time complexity in a very easy manner as well. It’s also good to mention Binet’s formula and memoization technique.
- Conway’s Game of Life – I include this program in the list just because it is beautiful. It is an excellent example of how simple rules can lead to complex interaction. Cellular automation is used in computability theory, mathematics, physics, complexity science and theoretical biology just to mention a few. To the curious readers, I recommend to read about Wolfram code as well.
- Quine (self-replicating program) – It is really fun to write a quine in your favorite (Turing complete) programming language. While writing a quine program is fun and good for your creativity, it is worthy to note its deep connection with mathematical logic and fixed point in mathematics.
- Currency converter – While this program may not seem fun or a programming challenge, it’s a handy tool and it will make you familiar with units of measure concept which is important in numeric calculation.
- String searching – I guess this is one of most common tasks in our work. Every now and then we have to search for a given substring. While the naive implementation is easy to write, you will quickly find out that it is impractical for large strings due its time and space complexity. Then you will enter the wonderful world of Knuth–Morris–Pratt and Rabin–Karp string search algorithms. There are tons of scientific literature on the topic and most of it comes from bioinformatics and computational mathematics.
- Huffman coding – It is, by far, the easiest introduction into the information theory and lossless data compression. While nowadays there are much better data compression algorithms, the idea of Shannon entropy is still used.
- Line counting – Well, you may find this is too lame. Counting the lines of a text file is not a big deal until the file is small and can fit into the main memory. Then you quickly come with the idea of data buffer. While buffering is not a rocket science it is one of most practical and useful things in most code bases.
- Calculate definite integral – Yes, you read it right. At first you may wonder how calculus is related to computer programming. I chose this relatively simple program because it demonstrates important ideas used in numerical analysis such as approximation and sampling. Both ideas are very important in computer programming because everything in computer science is discrete in a broader sense. If your programming languages allows passing functions as parameters then you can write this program in functional programming style.
- Graph traversal – Graphs are one of the most commonly used data structures. While both depth-first search and breadth-first search algorithms are easy to understand, together they represent a duality which is common to find in the computer science.
- Tic-tac-toe game – Writing this game is one of the easiest introduction to game theory. The simplicity of the game allows you to comprehend hard ideas like NP-complete and NP-hard problems, backtracking algorithms, alpha-beta pruning and minmax rule.