Computer Science Distilled

Logic in Computing

Logic gates perform logic operations on electric current. Logic gates include NOT, AND, OR, NAND, NOR, XOR, etc.

Logic gates calculating 2 + 3 = 5 (10 + 11 = 101):

1.3 Counting

Both counting and logic belong in the field of discrete mathematics.

Multiplying:

If one event happens n ways and another m ways, the way to calculate the number of ways both can happen is to multiply them.

Creating a PIN:

Problem: A PIN is comprised of two numbers and a letter. It takes one second to try a PIN. Worst case, how much time is needed to crack a PIN?

Solution: Two digits can be chosen 100 ways (00-99) and a possible letter in 26 ways (A-Z), making 100 * 26 = 2600 possible PINs. Worst case would mean having to try every single combination and arriving at the right PIN on the last attempt. Since each attempt is a second and worst case is 2600 attempts, the worst case would be 2600 seconds or around 43 minutes.

Hiring a Team:

Problem: There are 23 candidates wanting to join your team. For every candidate, you flip a coin and hire if the coin lands on heads. How many team configurations are possible?

Solution: When you start, the only configuration is you alone working at the company. Every coin toss then doubles the number of possible configurations. Since there are 23 candidates, that would mean 2²³ or 8388608 configurations.

Permutations:

If you have n items, you can order them n factorial (n!) different ways. n! = n x (n-1) x (n-2) x...2 x 1.

Traveling Salesman:

Problem: Truck company delivers to 15 different cities and you want to know the best order to serve the cities such that you use the least amount of gas. If it takes one microsecond to calculate the length of one route, how long does it take to compute the length of all possible routes?

Solution: Each permutation of the 15 cities is a different route - 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = ~1.3 trillion routes. In microseconds, roughly 15 days.

Precious Tune:

Problem: A musician is studying a scale of 13 notes. She wants to render all possible melodies that use six notes only. Each note should play once per melody and each six-node melody should play for a second. What would be the audio run-time for this song?

Solution: To count permutations of 6 out of the 13 notes, we need to ignore permutations of unused notes and stop developing the factorial after the sixth factor. n!/(n-m)! is the number of possible permutations of m out of n possible items. melodies, which would take 343 hours or so.

Permutations with Identical Items:

In a sequence of n items of which n are identical, there are r! ways to reorder the items. So to count distinct permutations, need to divide n! by the overcount factor.

Example: "CODE ENERGY" would be 10!/3!

Playing with DNA:

Problem: A biologist is studying a DNA segment relating to a specific disease. The segment is made of 23 base pairs where 9 must be A-T and 14 must be G-C. She wants to run a simulation on every possible DNA segment having this number of base pairs. How many simulations would that take?

Solution: First, calculate all possible permutations of the 23 base pairs then divide the result to account for the 9 repeated A-T and 14 repeated G-C base pairs:

23!/(9! * 14!) = 817190 base pair mutations. But the question isn't looking for base pairs, it's looking for segments. Because there are 23 base pairs, we multiply the number of base pair mutations by 2²³ to get ~ 7 trillion sequences.

Combinations:

Picture a deck of 13 cards of the same suit. How many ways can you deal six cards? The binomial is the number of ways to select m items of a set of n items regardless of order:
The binomial is read "n choose m".

Chess Queens:

Problem: You have an empty chessboard and 8 queens which can be placed anywhere on the board - how many different ways can the queens be placed? Board has 64 squares (8x8)
Solution: which equals 4426165368.

Sums:

Sequential sums are expressed using the capital-sigma Σ notation which indicates how an expression will be summed for each value of i:

Summing the first five odd numbers is written:
because the i is replaced by the numbers 0 - 4 in the equation.
(2(0) + 1) = 1
(2(1) + 1) = 3
(2(2) + 1) = 5
(2(3) + 1) = 7
(2(4) + 1) = 9

Summing the first n natural numbers is thus:

Gauss's Trick:

Legend has it that a teacher once punished Gauss by making him sum all numbers 1 to 100 and that's what lead him to come up with this solution:

Dividing by 2 then gives the answer of 5,050.

We can formally write this as:

As there is no i in the last line, (n+1) is summed over and over again n times. Therefore:

Flying Cheap:

Problem: You need to fly to New York City any time in the next 30 days. Ticket prices change unpredictably according to departure and return dates. How many pairs of days must be checked to find the cheapest tickets to fly to NYC within the next 30 days?

Solution: Any pair between Day 1 (today) and Day 30 is valid as long as the return flight is after the departure. So 30 pairs begin with Day 1, 29 begin with Day 2, 28 with Day 3, etc. We can use Gauss's Trick!

We could also solve this using combinations:

1.4 Probability:

Counting Outcomes:

A die roll has six possible outcomes: ⚀ ⚁ ⚂ ⚃ ⚄ ⚅ , so the chance of getting one particular number (say 4), is 1/6. The chance of rolling an odd is 3/6 or 1/2 because there are three odd dice - ⚀ ⚂ ⚄.

Probability can be calculated using this formula:

Team Odds

Problem: Given 23 candidates, throw coin and hire if heads. What are the chances of hiring nobody?

Solution: There is only one way to hire nobody - to throw tails 23 consecutive times. We've already established that there are 8,388,608 combinations of hiring, so the chances of hiring nobody is 1/8388608

Independent Events:

If the outcome of an event doesn't influence the outcome of another event, they are independent. The probability of two independent events occurring is the product of the individual probabilities. A coin toss ending in heds is 1/2 and a die being rolled a 2 is 1/6, so the probability of both is 1/2 * 1/6 = 1/12.

Backing Up:

Problem: You need to store data for a year. One disk has a probability of failing of one in a billion. The other disk costs 20% less and has a probability of failing of one in 2000. What should you buy?

Solution: If you use three cheap disks, you only lose the data if all three disks fail. The probability of that happening is (1/2000)³ -> 1/8,000,000,000. That redundancy achieves a lower risk of data loss than the expensive disk while costing 60% the price.

Mutually Exclusive Events:

When two events cannot happen simultaneously, they are mutually exclusive. Probability is calculated by summing the indidivual probabilities. Rolling a 4 and rolling an odd are mutually exclusive, so can be calculated by 1/6 + 1/2 = 2/3

Subscription Choice:

Problem: Your site offers a free, basic, and pro plan. Random new users have a 70% probability of choosing the free tier, 10% pro, and 20% basic. What are the chances a new user will sign up for a paying plan?

Solution: Customer cannot have multiple plans at the same time, so you sum the probability of both paid plans - 0.2 + 0.1 = 0.3

Complementary Events:

When two mutually exclusive events cover all possible outcomes, they are complementary. The sum of individual probabilities of complementary events is 100%.

Tower Defense:

Problem: Your castle is defended by 5 towers. Each tower has a 20% chance of disabling an invader before they reach the gate. What are the chances of stopping an attacker?

Solution: DO NOT SUM THE PROBABILITIES OF INDEPENDENT EVENTS. This is an example of complementary events.

• 20% chance of a hit means 80% miss rate.
• Probability of all 5 towers missing is 0.8⁵ which is around 0.33.
• The count of "all towers miss" is complementary to "at least one tower hits". The probability of stopping the enemy, then, is 1 - 0.33 = 0.67.

Gambler's Fallacy:

If you flip a normal coin 10 times and get 10 heads, the 11th flip is more likely to be tails. NEVER assume that past events affect the outcome of an independent event.

Advanced Probabilities:

Problem: 23 candidates and the coin toss. AGAIN. What are the chances of hiring seven people or less?

Solution: Binomial distribution. Type B(23, 1/2) <= 7 into Wolfram Alpha to visualize this.

References:
Discrete Mathematics and Its Applications : code.energy/rosen
Prof Jeanette Wing's slides on computational thinking : code.energy/wing