Algorithmic Complexity and Probability

Question 1

One way to measure how long a program takes to run is by timing it. But that would not be particularly informative, because the result would depend upon:
…

Answer 1

• the speed of the computer
• the efficiency of the Python implementation on that machine
• the value of the input

Question 2

How can one evaluate the efficiency of programs? (3 ways)

Answer 2

• measure with a timer
• count the operations
• abstract notion of order of growth

Question 3

States some downsides of timing programs.

Answer 3

Time does vary between algorithms, but it does not vary between implementations and computers

Question 4

Downsides of counting operations?

Answer 4

Counting depends on the algorithm, but it does not depend on implementations, and there is no clarity in which operations to count.

Question 5

Let’s say that we want to evaluate a function and we want to express efficiency in terms of size of input:

for i in L:
if i == e;
return True
return False

Analyze the first, worst and the average case scenarios in this case.

Answer 5

BEST CASE: first element is e
- minimum running time over all possible inputs of a given size, len(L)

AVERAGE CASE: look through about half of the elements of the list
- average running time over all possible inputs

WORST CASE: element e is not in the list
- maximum running time over all possible inputs of a given size, len(L)

Question 6

What does “Big Oh” measure?

Answer 6

Big Oh measures the asymptotic growth, often called the order of growth.

Describes how the amount of time needed grows as size of the (input to) problem grows.

Question 7

Big Oh is used to describe the ______ case.

a. best
b. worst
c. average

Answer 7

b. worst

Question 8

Big Oh expresses the rate of growth of the program relative to the input size. True or false?

Answer 8

True

Question 9

Big Oh evaluates the algorithm, the machine and the implementation. True or False?

Answer 9

False

Question 10

What running times do the following denote?

a. O(1)
b. O(logn)
c. O(n)
d. O(nlogn)
e. O(nˆc)
f. O(cˆn)

Answer 10

a. the constant running time
b. the logarithmic running time
c. the linear running time
d. the log-linear running time
e. the polynomial running time (c is a constant)
f. the exponential running time (c is a constant being raise to a power based on the size of the input)

Question 11

Rank the algorithm orders based on their time to execute:

O(1)
O(logn)
O(n)
O(nlogn)
O(nˆc)
O(cˆn)

Answer 11

They are in perfect order.

Question 12

The constant complexity is dependent on input. True or false?

Answer 12

False.

Question 13

Simple iterative loop algorithms are typically linear in complexity. True or false?

Answer 13

True

Question 14

Nested loops describe quadratic complexity. True or false?

Answer 14

True

Question 15

Bisection search is an example of quadratic complexity. True or false?

Answer 15

False, bisection search is an example of logarithmic complexity.

Question 16

By the way, this is what the bisection method it. Click

Answer 16

the bisection method is a root-finding method that applies to any continuous functions for which one knows two values with opposite signs. The method consists of repeatedly bisecting the interval defined by these values and then selecting the subinterval in which the function changes sign, and therefore must contain a root. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods

Question 17

When talking about probability, what is a sample space?

Answer 17

A sample space is the set of all possible outcomes of a random process or experiment.

Question 18

When talking about probability, what is an event?

Answer 18

An event is a subset of a sample space.

Question 19

State the Equally Likely Probability formula.

Answer 19

P = (the number of outcomes in the event)/(the number of outcomes in the sample space)

Question 20

What are permutations?

Answer 20

Permutation is the process of ordering a set of objects.

An r-permutation of a set of n elements is an ordered selection of r elements taken from the set of n elements.

Question 21

What is the formula of permutations?

Answer 21

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

Question 22

What are combinations?

Answer 22

Combination is the process of combining a set of objects in different ways.

An r-combination of a set of n elements is a subset of r of the n elements.

Question 23

What is the formula of combinations?

Answer 23

C(n, r) = n! / r! * (n - r)!

Question 24

Can you express the combination formula based on the permutation formula?

Answer 24

Yes.

C(n , r) = P (n , r) / r!

Question 25

What is P(Ø) equal to?

Answer 25

0

Question 26

What is the probability of a sample space?

Answer 26

1

Question 27

A probability is always between 0 and 1. True or false?

Answer 27

True

Question 28

Briefly explain conditional probability.

Answer 28

If A and B are events in a sample space, then the conditional probability of B given A is
P(B|A) = P(A intersect B) / P(A)

when P(A) != 0

Question 29

Can you say anything about Bayes’ Theorem?

Answer 29

Bayes’ theorem (alternatively Bayes’ law or Bayes’ rule), named after Reverend Thomas Bayes, describes the probability of an event, based on prior knowledge of conditions that might be related to the event.[1] For example, if the risk of developing health problems is known to increase with age, Bayes’ theorem allows the risk to an individual of a known age to be assessed more accurately (by conditioning it on their age) than simply assuming that the individual is typical of the population as a whole