1. Basics Flashcards
State 3 rules for Flowcharts
- Use Rectangles for states, steps and instructions
- Use Rhombus for decisions
- Mark the start and the end of the chart
What is PseudoCode?
Human friendly code that cannot be understood by machines
What is a Model?
A set of concepts to represent a problem and its characteristics
A –> B / A
If the water is cold –> I wont swim / !A –> !B
Explain the logic XOR (Exclusive OR)
XOR expresses ideas are of opposing truths
one of the two must be true for XOR to be true. If both true, or both false, then XOR returns false
AND / OR Associativity rule
Parentheses are irrelevant for the sequence of AND/OR operations:
A && (B && C) = (A && B) && C
A || (B || C) = (A || B) ||C
AND / OR Distributivity rule
Factoring multiplicative terms from sums:
a x (b+c) = axb + axc;
A && (B || C) = A&&B || A&&C
A||(B&&C) = A||B && A||C
AND / OR DeMorgan’s Law
!(A&&B) = !A || !B !(A||B) = !A && !B
Sumer and Winter cannot be at the same time, so it is either not Summer, or not Winter.
It is not Summer and not Winter when it is not either Summer or Winter
If an event happens in M different ways, and another event happens in N different ways. What is the number of ways both events can happen?
M x N
A PIN code is composed of two digits and a letter. It takes one second to try a PIN. In the worst case, how much time do we need to crack a PIN?
Two digits can be chosen in 100 ways (00-99) and a letter in 26 ways (A-Z). Therefore, there are 100 × 26 = 2, 600 possible PINs. In the worst case, we have to try every single PIN until we find the right one. After 2,600 seconds (43 minutes), we’ll have cracked it.
There are 23 candidates who want to join your team. For each candidate, you toss a coin and only hire if it shows heads. How many team configurations are possible?
Before hiring, the only possible team configuration is you alone. Each coin toss then doubles the number of possible configurations. This has to be done 23 times, so we compute 2 to the power 23:
How many ways are there to order N items?
N!
Are Permutations ordered? what does it mean?
Yes. It means if we are choosing Richard, Polly, and Nico out of 30 people, the order in we choose will determine their classes. So RPN will have different outcome than PNR.
How to calculate a combination which is ordered, have n options, happens r times and allows for repetition?
An ordered combination is Permutation. If it allows for repetition it makes each arrangement of r independent of the other, so N x R ==> N^R
How to calculate an ordered Combination, which does not allow for repetition, where r items need to be chosen out of n?
An ordered combination is Permutation.
N! / (N-R)!
Your truck company delivers to 15 cities. You want to know in what order to serve these cities to minimize gas consumption. If it takes a microsecond to calculate the length of one route, how long does it take to compute the length of all possible routes?
Each permutation of the 15 cities is a different route. The factorial is the number of distinct permutations, so there are 15! = 15 × 14 × · · · × 1 ≈ 1.3 trillion routes. That in microseconds is roughly equivalent to 15 days. If instead you had 20 cities, it would take 77 thousand years.
A musician is studying a scale with 13 different notes. She wants you to render all possi- ble melodies that use six notes only. Each note should play once per melody, and each six-note melody should play for one second. How much audio runtime is she asking for?
We want to count permutations of six out of the 13 notes. To ignore permutations of unused notes, we must stop developing the factorial after the sixth factor. Formally, n!/(n − m)! is the number of possible permutations of m out of n possible items. In our case:
13! (13 − 6)!
= 13×12×11×10×9×8×7! 7!
= 13 × 12 × 11 × 10 × 9 × 8
6 factors
= 1, 235, 520 melodies.
That’s over 1.2 million one-second melodies—it would take 343 hours to listen to everything. Better convince the musician to find the perfect melody some other way.
You have an empty chessboard and 8 queens, which can be placed anywhere on the board. In how many different ways can the queens be placed?
The chessboard has 64 squares in an 8×8 grid. The number of ways
to choose 8 squares out of the available 64 is (64) ≈ 4.4 billion.
How are combinations without repetitions calculated? (choosing M items out of N)
N! / M! ( N-M)!
How are combinations WITH repetitions calculated?
n - number of items
m - number of items to be choses from n
r = n - 1 (number of switches between resources)
(m + n -1)! / m! (n-1)!
What are independent events? and how are they calculated?
If the outcome of one event does not affect the outcome of the other event, those events are considered independent.
P1 x P2
What are Mutually Exclusive events? and how are they calculated?
When the events cannot happen simultaneously, one OR the other event happens.
P1 + P2
What are complementary events?
When two events cover all possibilities, namely P1 + P2 = 100% || P1 = !P2
