As a review of what I learned in school and have already began to forget, I’ve been reading Computer Science Distilled by Wladston Ferreira Filho in an attempt to refresh my core CS knowledge. As I go through chapters and search for more details to better understand concepts, I figure it’s a good opportunity to write small summaries such as this one.
Introduction
Computer Science Distilledstarts off with a chapter called Basics. In this chapter there is a general introduction to logic (operators, boolean algebra, etc), counting and probabilities. This is where I started during college and it makes sense to start here because the foundation of Computer Science is based on math and logic.
1. Logic
Skipping over operators because they are relatively simple, I’ll skip directly to boolean algebra. There are some general rules a programmer should understand when it comes to boolean statements (which you will come across a lot at work).
A. Associativity
If a sequence has all the same operations (all/or), parentheses are irrelevant and the sequence can be evaluated in any order.
(A and B) and C = A and (B and C)
B. Distributivity
You can distribute boolean logic with and/or sequences just like you would in regular algebra.
A and (B or C) = (A and B) or (A and C)
C. DeMorgan’s Law
You can’t run forwards and run backwards simultaneously. You are either doing one or the other, and this can be applied to your boolean logic.
! (forward and backward) = ! forward or ! backward
Computer Science Distilled gives some great examples of using distribution to simplify logic or make it more understandable. I have made up my own example below, but the examples in the book are more in-depth.
You have a car that does not drive if it doesn’t start. A car might not start because it has no fuel. It also might not start because it has no battery.
A : Car does not start B : Car has no fuel C : Car has no battery D : Car does not drive
For the car to not drive, we can model by:
D -> (A and B) or (A and C)
But this can be simplified to:
D -> A and (B or C)
What if we want to see the logic for a car that does drive (! D)?
!D -> !(A and (B or C)) !D -> !A or !(B or C) !D -> !A or (!B and !C)
For a car to drive we need the car to start or we need the car to have fuel and battery, which meets the conditions needed for the car to start, and therefore to drive!
Counting
There are situations where a developer needs to calculate complexity or estimate time needed to complete a task. For this, the developer needs to know a number of possibilities.
For example, if a pin is needed to unlock a phone, and the pin includes 2 digits between 0 and 9 and two letters, how is the number of possibilities determined?
Having 2 numerical digits will range from 00 to 99, giving us 100 possibilities. If there are two letters in this combination, and there are 26 letters, then the final solution is:
100 x 26 x 26 = 67,600 possibilties
This of course is a very simple example.
Permutations
Permutations are basically the calculations of the total possible combinations of a set. To calculate this we use a factorial (n!).
N! = n x (n - 1) x (n - 2) x ... x 2 x 1
If a salesman has to visit 5 locations in a day, and wants to get all possible combinations of routes, he would calculate this by finding the value of 5!
5! = 5 x 4 x 3 x 2 x 1 = 120
This means there are 120 possible combinations of routes he can take. This however is a simple example because the 5 different locations are all unique.
What if you wanted to find the number of possible combinations of the letters in the word Google? There are 6 letters so there are 6! combinations, unless you don’t use duplicate letters.
In the case of number of combinations of unique letters in the word Google, the solution is:
6! / (2! * 2!) = 180
The word Google has 6 letters, but there are 2 o’ and 2 g’s. To get the number of unique permutations we divide the total number of permutations (6!), by 2! x 2!
Probability
The formula for calculating the probability of an outcome is the number of ways the event can happen divided by the number of outcomes. For example, on a perfect coin toss, the chance of getting heads is 1 out of 2 outcomes, so it’s 50%.
When determining the probability of independent events, you calculate the probabilities separately and then multiply them together. For example a coin toss landing on heads and a dice rolling a 4 would be two independent events.
Mutually Exclusive Events
Out of a deck. of 52 cards, the probability of drawing a King is a 1/13 probability. You can’t draw a Queen and a King at the same time, so they are mutually exclusive. In this case the probability of drawing a King or Queen is the sum of both probabilities.
1/13 + 1/13 = 2/13 probability