Here’s a list of important computer science theories and concecpts that most computer science undergraduate courses will cover. All explanations are intuitive, simple, and non-technical. It’s like an ultra-fast-track computer science degree program for everyone, just to get you to understand the general concepts.
Important notes:
- 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 to boil things down to the most fundamental truths and then reason up from there.
- Huge thanks to Redditors for pointing out my mistakes and suggesting better analogies.
Also, check out this infographic if you’re just getting started with programming.
Core Concept #1 – Algorithms and Data Structures
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.
Sorting Algorithms
More: Sorting Algorithm Animations, Beautiful and configurable visualizations of sorting algorithm
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.
Here are more Droste effect examples to get you drowsier.
If you still don’t get what recursion is, check out… Otherwise, continue reading.
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.
More: Big Data by TED-Ed (video), What is Big Data and Hadoop (video)
Core Concept #2 – Artificial Intelligence
Greedy Algorithm
Imagine you are going for hiking. You already have the map before you start. However, there are thousands of possible paths shown on the map. You are too lazy and simply don’t have the time to evaluate each of them. Screw the map! You started hiking with a simple strategy – be greedy and short-sighted. Just take paths that slope upwards the most.
After the trip ended and your whole body is sore and tired, you look at the hiking map for the first time. Oh my god! There’s a muddy river that I should’ve crossed, instead of keep walking upwards.
A greedy algorithm picks the best immediate choice and never reconsiders its choices.
Hill Climbing
This time you’re climbing another hill. You’re determined to find the path that will lead you to the highest peak. However, there’s no map provided and it’s very foggy. To make your trips easier, you have downloaded a hiking app that track paths you’ve taken and measures your current altitude.
You climb the hill over and over again. Each time, you take the exact same path that leads you to the highest peak ever recorded, but somewhere in the middle of your journey, you choose a slightly different route.
You can also randomly choose a different starting point, which is known as random-restart hill climbing. So that you don’t just linger around the same area and reduce your probability of getting stuck.
The hill climbing algorithm attempts to find a better solution by generating a neighboring solution. Each neighboring solution is generated based on the best solution so far, with a single element modified.
Simulated Annealing
It’s Mount Everest, the biggest challenge you’ve ever faced. Your goal is to reach the summit, but it’s impractical to climb Mount Everest over and over again. You have one chance. You are more cautious now. Instead of always climbing upwards, you occasionally move to a lower point and explore other paths, to reducing your chance of taking the wrong path. The higher you climb, the lower the probability you move to a lower point and explore.
Dynamic Programming
Dad: *Writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper*
Dad: What’s that equal to?
Kid: *counting and 3 seconds later* Eight!
Dad: *Writes down another “+1″ on the left*
Dad: What about now?
Kid: *instantly* Nine!
Dad: Wow, how did you calculate so fast?
Kid: You just added one more!
Dad: So you didn’t need to recount because you remembered it was eight before. Brilliant!
Dynamic programming breaks down a complex problem and attempt to solve each simpler sub problem only once, by remembering the computed solution (memoization).
Machine Learning
Pararth Shah wrote a brilliant analogy here, but it’s too long to be included.
P vs NP Problem
P vs NP one of the most popular and important unsolved problem in the computer science field.
Say I give you a multiplication question like:
Q1: 7 x 17 = p
The answer is 119. Easy to solve right? What if I reverse the question:
Q2: p x q = 119 (p & q cannot be 1 & 119)
To solve Q2, assuming that you haven’t seen Q1, you probably have to go through all possible numbers from 2 to 118. We are yet to discover an efficient algorithm that can find the factors of a number easily.
What if I ask you: Could p possibly be 7? You can easily verify the answer right? Just divide 119 by 7!
Multiplication is easy. Finding the original factors of a number is hard.
So Q1 is a P (polynomial) problem because it is easy to solve. Computer can easily multiply 2 super large numbers without spending significantly more computer time than small numbers.
Q2 is a NP (nondeterministic polynomial) problem because it is easy to verify, but hard to solve. Finding the factors of 119 is still fairly easy for computer to solve, but how about a 500-digit number? It’s impossible for any computers right now.
Here’s the important part: Are NP problems (e.g., factorization) also P problems (e.g., multiplication), just that we haven’t discover the efficient way to solve NP problems? Are NP problems really hard to solve, or we just need an “aha moment” from a brilliant scientist (or you?) to come out with an efficient algorithm? Or maybe humans are too dumb? Imagine there exist machine or life that possesses much higher intelligence than human. Solving P vs NP problem is like solving 1 + 1 to them!
So why is P vs NP problem important? If we are able to prove P=NP, that means all NP problems can be solved easily within reasonable computer time. We will be able to cure cancer (protein folding), break passwords (RSA), etc. It’s world-changing.
P vs NP is listed as 1 of the 7 Millennium Prize Problems by Clay Mathematics Institute. $1 million will be awarded to the first correct solution.
More: P vs. NP and the Computational Complexity Zoo (video), Simple Wikipedia
Read Also: The Lord of the Rings Analogy To Programming Languages [Infographic]
Core Concept #3 – Computer Architecture and Engineering
How do computers work?
Computers work by adding complexity on top of complexity. When you drive a car, you don’t necessarily have to understand how the car’s engine works. The complex details are hidden.
So how do computers turn binary code, the 0’s and 1’s into programs? Here’s an excellent video that uses dominoes to visualize how computers perform binary calculations at the most basic, fundamental level:
More: Interactive explanation on how computer works
Computer architecture and engineering is a huge topic which includes subfields like operating system, compiler, and more.
Core Concept #4 – Concurrency
Let’s say you work as a secretary in company A. You have to answer phone calls, arrange meetings, typing documents, etc. You always have to switch back and forth between your tasks based on priority. Every time the phone rings, you have to stop whatever task you are working on.
Concurrency is a property of programs and systems that allow tasks to run in overlapping time periods.
Parallelism
Eventually, you can’t cope with your job because there’s too much data entry tasks. You complain to your boss and he happily hires a data entry clerk to handle your data entry tasks.
Parallelism allows 2 or more tasks to run at the same time, provided that the machine has multiprocessing capability.
However, the implementation of concurrency concepts also introduces more potential problems such as race condition.
Race Condition
This is what will happen if you allow concurrent transactions in a banking system and race condition isn’t handled:
- You have $1000 in your bank account.
- Someone transfers $500 to you and you withdraw $300 from ATM.
- Imagine both transactions are performed at the same time, both transactions will see $1000 as your current balance.
- Now, transaction A adds $500 to your account and you have $1500. However, transaction B also sees $1000 as your current balance and it completes a millisecond later, it deducts $300 from $1000 and updates your account balance as $700.
- You now have $700 instead of $1200 because transaction B overwrites transaction A.
- This happens because the banking system isn’t aware of other ongoing transactions.
So, what can you do to handle the above situation? One really simple way is mutual exclusion.
Mutual Exclusion (Mutex)
Now, whenever there’s an ongoing transaction, the system will lock the account(s) involved in the transaction.
This time, the moment when transaction A occurs, your account is locked. You can’t withdraw money from ATM. It unlocks only when transaction A completes.
So mutual exclusion solves the problem right? Yes, but nobody wants to get rejected by the ATM every time there’s an ongoing transaction.
Let’s modify the solution a little bit.
Semaphore
Binary Semaphore
Now, let’s set different priority levels for different types of transactions. Say cash withdrawal request has a higher priority than bank transfer. When you withdraw money from ATM, transaction A (the bank transfer) will stop and allow transaction B to carry on first because it has higher priority. It will resume after transaction B is completed.
Counting Semaphore
Binary semaphore is simple. 1 = ongoing transaction. 0 = waiting. On the other hand, counting semaphore allows more than 1 process running at the same time.
Let’s say you’re a locker room manager for a spa. There are 30 lockers. You have to keep track of the number of keys you have each time you receive or hand out a key, but you don’t exactly know who they are. If all lockers are full, others have to queue up. Whenever someone is done, he/she will hand over the key to the first person in the queue.
Deadlock
Deadlock is another common issue in concurrency system.
Let’s use the same banking system analogy with a different scenario. Just keep in mind that access to a bank account is locked whenever there’s an ongoing transaction.
- Peter transfer $1000 to you (transaction A) and you transfer $500 to him at the same time (transaction B).
- Transaction A locks Peter’s account and deducts $1000 from Peter’s account.
- Transaction B locks your account and deducts $500 from your account.
- Then, transaction A tries access your account to add the $1000 from Peter.
- At the same time, transaction B also tries to add your $500 to Peter’s account.
However, since both transactions aren’t completed, both can’t access the locked accounts. Both wait for each other to complete. Deadlock.
Core Concept #5 – Computer Security
Computer Hacking
Hacking is similar to breaking into a house. Here are some of the popular hacking techniques:
Brute-force Attack
Try hundreds and thousands of different keys. An experienced burglar will try the most commonly used keys first.
A brute-force attack tries every possible passwords, and usually starts by guessing commonly used passwords like “123456”, “abcdef”, etc.
Social Engineering
A couple just moved in next door. They are really nice and helpful. They often invite you over for dinner. One day, you mentioned that you are going for a two-week vacation soon. They happily offered to take care of your dog. You left a spare key for them. Since then, you have not heard any news about them.
Social engineering is tricking users into revealing their private information.
Security Exploit
A burglar checks every possible entries to find the easiest way (weakness) to get in. Maybe your second-floor windows is left open, who knows?
Trojan Horse
A burglar pretends to be a plumber and you unlock the door for him. He fixes your leaking pipe and everything looks perfectly normal. After he left, you discovered that your jewelry is missing.
A trojan horse is malware program that pretends to be useful or helpful and runs malicious code in the background.
Rootkit
Your door lock is jammed and you call a locksmith. He fixes your door lock and secretly duplicates another key.
A rootkit gains administrator or root access of a computer through various ways like social engineering, then disguise as necessary files that is hard to detect by antivirus software.
Distributed Denial-of-service Attack (DDoS)
Here’s a bookshop analogy.
Imagine 100 people visit your little bookshop at the same time. Your bookshop is occupied and others can’t come in. You can’t ask any of them to leave because they don’t seem to be coming in groups. They probably don’t know each other at all. Most of them seem to be genuinely interested to buy books. Some even ask you where are the book shelved. Someone at the counter just pay you in pennies.
People keep coming in and out for hours. All of them look perfectly normal. At the end of the day, you’ve only made one book sale. Remember the guy who pay you in pennies?
DDoS attempts to bring a site or service down by flooding it with visitors.
Cryptography
Cryptography is the study and application of secure communication. Here are 2 of the most widely used cryptographic protocols:
Symmetric cryptography
Say Alice and Bob want to send each other stuff. To make sure nobody can see their stuff, they lock it with a box. They make 2 identical (symmetric) keys for the lock and meet up to share the keys beforehand.
Asymmetric cryptography
Sharing identical keys works fine among 2 people. What if Alice want to exchange stuff with another guy named Carl, and Alice doesn’t want anybody to see their stuff too? Alice can’t use the same lock and key that she shared with Bob, else Bob can unlock the box easily!
Of course Alice can share a completely new and different lock and key with Carl, but what if Alice wants to exchange stuff with 10 different people? She will need to keep and manage 10 different keys!
So Alice come out with a brilliant solution. Now, she only maintains one key (private key). She distribute the same padlocks (public key) to her friends. Anyone can close the padlocks (encrypt), but only she has the key to open (decrypt) them. Now, anyone can send stuff to Alice using the padlock she distributed, and Alice no longer have to manage different keys for different people.
If Alice wants to send something to Carl, she will ask for Carl’s padlock (public key) so that she can use it to lock (encrypt) her stuff and send it to Carl.
The basic principle is: everyone has their own private key to decrypt message, and they will provide senders their own public key for message encryption.
More: Public Key Cryptography: Diffie-Hellman Key Exchange (video)
Read Also: Before They Were Famous – Early Posts From Larry Page, Linus Torvalds, and More
Core Concept #6 – Computer Network
The Internet is like all the roads in the world. It is not one thing, nor it is owned by one person. It is just a series of interconnected systems to get you from one place to the other.
When you go to a website like google.ca, it is like looking up where google.ca lives in the phone book. This is called a DNS Lookup. The problem is, the Internet is so huge, you would have to get massive phone books delivered every hour on the hour to your house.
Instead of downloading the entire phone book, we do a lookup with a phone book your Internet Server Provider (ISP) has. Your ISP talks to other phone books, gets updates and information, and keeps track of them. When your ISP doesn’t know about an address you asked, it calls up someone else and asks them. This is called a DNS Server.
Your computer, your router (the Internet box in your living room) and your ISP remember things they have looked up before for quick recall and to avoid stressing the system, this is called DNS caching.
Once you have the proper address from the phonebook, your computer tells your ISP that you are requesting a web page from the IP address (street address) of google.ca, your computer scribbles a little note like “give me the search page please!” and hands it to your ISP, telling them to take it to the street address you got from the phone book earlier.
Your ISP then sends the letter along the road, going through a series of other providers, all passing the note through different roads until it gets to Google.
Because you are passing this letter along, any one of these providers can just read the note and find out what you are telling or asking Google. When the note is encrypted, the providers are unable to read it as they do not have the key and only able to pass it along.
Google opens up the letter and reads the page you requested. It sends back to you in a series of more letters in the mail, passing through a similar system. Once you get the letter you might send out more letters, asking for the google logo, things like that.
Your computer reads the letter and puts it on your screen in the form of graphics. The letter itself has text describing what the image on the page should look like, or the images you should download, the browser assembles these and turns them into the picture you see on the screen.
If your computer already has the Google logo it might not have to send a letter asking for it again, this is also caching.
A web server like Google needs to handle reading so many letters (in real life they are called packets) at once that it needs thousands of servers.
Core Concept #6 – Software Development Methodologies
Waterfall Development
You figure out everything you need to do and document them (requirements). Like a waterfall, there’s no way to go back up unless you start over again. You move on to next phase only when current phase is completed.
Agile Development
You figure out some of the things you need to do at the beginning. Then, continuously improve, evolve, collaborate and adapt as the development goes on.
Here are some of the popular implementations of agile development methodology:
Software Development In The Real World
So you graduated. You write good and beautiful code (hopefully), everything is perfect so far. Let me introduce you cowboy coding, a software development methodology that isn’t taught in college.
Next, you wonder why you suck at estimating development time:
And methodologies are often implemented wrongly:
So here you go. Computer science in the nutshell.
Feel free to suggest any new computer science theories or concepts to add, those that you think is important and often confusing.
Leave a Reply