Editor’s note: This post first appeared on Carl Cheo’s website. We’ve republished it here with his permission.
To make learning more fun and interesting, here’s a list of important computer science theories and concepts explained with analogies and minimally technical terms. It’s like an ultra-fast-track computer science degree program for everyone, just to get you to understand the general concepts.
- Explanations without specified source are self-written. Correct me if you spot any inaccuracies. Suggest a better one if possible!
- Headings are linked to their respective Wikipedia articles. Please refer Wikipedia for more serious and detailed explanations.
- Analogies are awesome, but not perfect. If you want fully understand the concepts, you need toboil things down to the most fundamental truths and then reason up from there.
Also, check out this infographic if you’re just getting started with programming.
Core Concept #1 – Algorithms and Data Structures
1.1 – Big O Notation
Say you order Harry Potter: Complete 8-Film Collection [Blu-ray] from Amazon and download the same film collection online at the same time. You want to test which method is faster. The delivery takes almost a day to arrive and the download completed about 30 minutes earlier. Great! So it’s a tight race.
What if I order several Blu-ray movies like The Lord of the Rings, Twilight, The Dark Knight Trilogy, etc. and download all the movies online at the same time? This time, the delivery still take a day to complete, but the online download takes 3 days to finish.
For online shopping, the number of purchased item (input) doesn’t affect the delivery time. The output is constant. We call this O(1).
For online downloading, the download time is directly proportional to the movie file sizes (input). We call this O(n).
From the experiments, we know that online shopping scales better than online downloading. It is very important to understand big O notation because it helps you to analyze the scalability and efficiency of algorithms.
Note: Big O notation represents the worst-case scenario of an algorithm. Let’s assume that O(1) and O(n) are the worst-case scenarios of the example above.
1.2 – Sorting Algorithms
Here’s a video that explains sorting:
1.3 – Recursion
Someone in a movie theater asks you what row you’re sitting in. You are too lazy to count, so you ask the person in front of you. You simply have to add 1 from the person’s answer to get your current row number. Brilliant right? However, the person in front of you did exactly the same thing, and so on. Finally the question reaches row 1 and he answers: “I’m in row 1!”. From there, the correct message (incremented by one each row) will pass all the way up to the person who asked.
Here’s another example known as the Droste effect. A nurse is carrying a tray with a box of cocoa and a cup containing a smaller image of her holding the same thing, which in turn contains an even smaller version of the image, and so on.
If you still don’t get what recursion is, check out… Otherwise, continue reading.
1.4 – Big Data
Let’s assume you have a leak in a water pipe in your garden. You take a bucket and some sealing materials to fix the problem. After a while, you see that the leak is much bigger that you need a plumber to bring bigger tools. In the meanwhile, you are still using the bucket to drain the water. After a while, you notice that a massive underground stream has opened. You need to handle gallons of water every second.
Buckets aren’t useful anymore. You need a completely new approach to solve the problem because the volume and velocity of water has grown. To prevent the town from flooding, you may need the government to build a massive dam that requires an enormous civil engineering expertise and an elaborate control system.
Big data describes data sets so large and complex that is impossible to manage with conventional data processing tools.
1.5 – Data Structures
Every computer scientist and programmer should at least know:
Go to the next page to learn about artificial intelligence and computer architecture.