Algorithmic Complexity and Probability

Question 1

What is the trade off when deciding which option for a program is the most efficient?

Answer 1

Time and space efficiency:

Question 2

How to evaluate efficiency of programs?

Answer 2

• measure with a timer
• count the operations
• abstract notion of order of growth (most appropriate way)

Question 3

How can you time a program?

Answer 3

Use a time module:
import time t0 = time.clock (start)
call function
t1 = time.clock() - t0

Question 4

What are the drawbacks of timimng programs?

Answer 4

Timing is inconsistent:

timer varies for different inputs but cannot really express a relationship between inputs and timer

Question 5

What are the positive aspects and drawbacks of counting operations?

Answer 5

good:
count depends on algorithm
count is independent of the computer

bad:
count depends on the implementation
no clear definition of which operation to use

Overall: count varies for different inputs and can come up with a relationship between inputs and counts

Question 6

What are the problems about timing and counting as evaluation implementations?

Answer 6

What oyu really want to do is evaluate the algorithm, scalability and the input isze

Question 7

Does the input influence how the function runs?

Answer 7

Yes, i.e. a function that searches for an element in a list:
1. when e is the first element in the lest –> best case
when e is not in the list –> worst case
want to measure this in a general way
(look through half for the average case)

Question 8

What measure do we use to measure the order of growthß

Answer 8

Big OH notation

Question 9

What does the big o notation measure?

Answer 9

The upper bound of the asymptotic growth, often called order of growth
–> big o is used to descrive worst case as it is the bottleneck when a program runs
this evaluates the algorithm and not the machine or implementation

Question 10

What does O(N) measure?

Answer 10

–> how the time needed grows with the input growth

Question 11

What types of orders of growth do we know?

Answer 11

Constant
linear
quadratic
logarithmic
n log n
exponential

Question 12

What is the law of addition for o()?

Answer 12

O(f(n)) + O(g(n)) = O(f(n) + g(n))

Question 13

What is the law of multiplication for O()?

Answer 13

O8f(n)) * O(g(n)) = O(f(n) * g(n))

Question 14

What complexity classes do we know and what do they mean?

Answer 14

O(1) –> constant running time
O(log n) –> logarithmic running time
O(n) –> denotes linear running time
O(n log n) –> denotes log-linear running time
O(nC) –> polynominial runnung rime (c constant)
O(cN) –> exponential running time (c is a constant being raised to power based on soze if input)

Question 15

What are examples of constant complexity?

Answer 15

• -> Complexity independent of input

examples: finding length of a list in python

Question 16

What are examples of linear complexity?

Answer 16

Simple iterative loop algorithms are typically linear in complexity?
- i.e. linear seach on unsorted list

Question 17

What are examples of quadratic complexity?

Answer 17

determine if one list is a subset of another list

Question 18

What are examples of logarithmic complexity?

Answer 18

complexity grows as log of size of its inputs

i.e. bisection search

Question 19

What are examples of exponential complexity?

Answer 19

recursive functions where more than one recursive call for each size of problem

Question 20

What do we use big oh for?

Answer 20

To compare efficiency of algorithms

• > notation that describes growth
• > lower order of growth is better
• > independent of machine specific implementation

Use big oh:

• to descrive order of growt
• upper bound
• worst case analysis

Question 21

What is a sample space?

Answer 21

The set of all possible outcomes of a random process or experiment an event is a subset of a sample space

Question 22

What is the equally likely probability formula?

Answer 22

S = finites sample space and E is an event in S
P(E) = # of otcomes in E/ # of outcomes in S

Question 23

What is the multiplication rule (probability trees)

Answer 23

if an operation consists of k steps and the first step can be performed in n1 ways and the second step in n2 ways …. the entire operation can be performed in n1n2…nk ways

Question 24

What is a permutation?

Answer 24

A permutation of a set of objects is an ordering of the objects in a row. for example the set fo elements a, b, c has six permutations:
abc acb cba bca cab

Question 25

How to calculate the number of permutations?

Answer 25

n and r are integers and 1 <= r <= n the the number of r permutations of a set of n elements r permutations
P(n, r) = n!/(n-r)!

Question 26

what does
n
r n choose r denote?

Answer 26

The number of subsets of size r that can be chosen from a set of n elements

Question 27

How do you calculate the number of subsets of size r that can be chosen from a set of n elements
n
r

Answer 27

n
r
= n!/ r!(n-r)!

Question 28

What are the probability axioms?

Answer 28

For all events A and B in S: 
1. 0 <= P(A) <= 1
2. P(leere menge= 0 P (S) =1 
3. If A and B are disjoint then the probability of the union of A and B is 
P(A) + P(B)

Question 29

What is the likelihood of the compliment of an event?

Answer 29

P(Ac) = 1- P(A)

Question 30

How do you calculate the expected value of an experiment?

Answer 30

a1, …, an are the outcomes of the experiment and p1, …, pn are their respective probabilities:
= a1p1 + … + anpn

Question 31

How do you calculate Conditional probability of B given A?

Answer 31

P(B|A) = P(a n B)/ P(A)