Core Concept #2 – Artificial Intelligence
2.1 – Greedy Algorithm
Imagine you are going for hiking and your goal is to reach the highest peak possible. You already have the map before you start, but 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.
2.2 – 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.
AI Weekly
The must-read newsletter for AI and Big Data industry written by Khari Johnson, Kyle Wiggers, and Seth Colaner.
Included with VentureBeat Insider and VentureBeat VIP memberships.
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.
2.3 – 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.
2.4 – Dynamic Programming
Advertisement
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!
(Jonathan Paulson / Quora)
The example above describes memoization (yes memoization not memorization), a top-down approach in dynamic programming, which store the results of previous computations for future use.
More: Dynamic Programming – From Novice to Advanced (TopCoder), Tutorial for Dynamic Programming (CodeChef)
2.5 – Machine Learning
Pararth Shah wrote a brilliant analogy here, but it’s too long to be included.
2.6 – 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. They see us like how we see ants. Our level of intelligence is too insignificant to them. 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
3.1 – How do computers work?
Above: Computers work by adding successive layers of abstraction on top of earlier layers.
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
3.2 – Halting Problem
Watch this video:
More: The Freeze App Analogy, Simple Wikipedia
Computer architecture and engineering is a huge topic which includes subfields like operating system,compiler, and more.
On the next page: Concurrency and computer security