1. Basics

Question 1

State 3 rules for Flowcharts

Answer 1

1. Use Rectangles for states, steps and instructions
2. Use Rhombus for decisions
3. Mark the start and the end of the chart

Question 2

What is PseudoCode?

Answer 2

Human friendly code that cannot be understood by machines

Question 3

What is a Model?

Answer 3

A set of concepts to represent a problem and its characteristics

Question 4

A –> B / A

Answer 4

If the water is cold –> I wont swim / !A –> !B

Question 5

Explain the logic XOR (Exclusive OR)

Answer 5

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

Question 6

AND / OR Associativity rule

Answer 6

Parentheses are irrelevant for the sequence of AND/OR operations:

A && (B && C) = (A && B) && C
A || (B || C) = (A || B) ||C

Question 7

AND / OR Distributivity rule

Answer 7

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

Question 8

AND / OR DeMorgan’s Law

Answer 8

!(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

Question 9

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?

Answer 9

M x N

Question 10

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?

Answer 10

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.

Question 11

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?

Answer 11

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:

Question 12

How many ways are there to order N items?

Answer 12

N!

Question 13

Are Permutations ordered? what does it mean?

Answer 13

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.

Question 14

How to calculate a combination which is ordered, have n options, happens r times and allows for repetition?

Answer 14

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

Question 15

How to calculate an ordered Combination, which does not allow for repetition, where r items need to be chosen out of n?

Answer 15

An ordered combination is Permutation.

N! / (N-R)!

Question 16

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?

Answer 16

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.

Question 17

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?

Answer 17

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.

Question 18

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?

Answer 18

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.

Question 19

How are combinations without repetitions calculated? (choosing M items out of N)

Answer 19

N! / M! ( N-M)!

Question 20

How are combinations WITH repetitions calculated?
n - number of items
m - number of items to be choses from n

Answer 20

r = n - 1 (number of switches between resources)

(m + n -1)! / m! (n-1)!

Question 21

What are independent events? and how are they calculated?

Answer 21

If the outcome of one event does not affect the outcome of the other event, those events are considered independent.
P1 x P2

Question 22

What are Mutually Exclusive events? and how are they calculated?

Answer 22

When the events cannot happen simultaneously, one OR the other event happens.
P1 + P2

Question 23

What are complementary events?

Answer 23

When two events cover all possibilities, namely P1 + P2 = 100% || P1 = !P2