Algorithms

Question 1

What is an algorithm?

Answer 1

An algorithm is a sequence of steps for performing a task in a finite amount of time.

Question 2

What is a data structure?

Answer 2

For computational algorithms, we use data structures to store, access, and manipulate data.

Question 3

Questions to decide which search to use

Answer 3

• How is the list stored?
• Is it sorted or not?
• It is it not sorted, should we sort it first?
• Are we updating the list?

Question 4

Types of algorithm analysis

Answer 4

• Running time
• Space usage
• Optimality of the output solution

Question 5

Experimental Analysis

Answer 5

Interested in dependency of the running time on size of the input.
Size could mean amount of numbers of bits or amount of vertices and edges in a graph.
Therefore we perform experiments to empirically observe running time.

Question 6

Drawbacks of experimental analysis

Answer 6

• Limited test of inputs
• Requires all tests to be performed hardware and software
• Requires implementation and execution of algorithm

Question 7

Theoretical Analysis

Answer 7

More theory based approach of finding running time of algorithms.

Question 8

Theoretical Analysis Benefits

Answer 8

• Can take all possible inputs into account.
• Involves studying high-level descriptions of algorithms
• Can compare efficiency of two algorithms

Question 9

Theoretical Analysis Functions

Answer 9

When doing theoretical analysis, we typically assign a function f(n) to the algorithm, where f(n) characterises the running time for an input size n.

Question 10

Theoretical Analysis Requirements

Answer 10

• a language to describe algorithms
• computational model in which algorithms are executed
• metric for running time
• a way of characterising running time

Question 11

Pseudo-code

Answer 11

A high level description language for algorithms.
Mixture of a natural language and a high-level programming language, describing a generic implementation of data structures or algorithms.

Question 12

Correctness

Answer 12

An algorithm is correct with respect to a specification if it behaves as specified.

Question 13

Loop Invariant

Answer 13

A way to show correctness of an algorithm.
For example, if we had a for loop, we could state what the expected value is at the end of the for loop, aka specifying what the for loop is meant to do.

Question 14

Loop Invariant Properties

Answer 14

• intialisation
• maintenance
• terminantion

Question 15

Initalisation (Loop Invariant)

Answer 15

Remains true prior to the first iteration of the loop.

Question 16

Maintenance

Answer 16

If it remains true before an iteration of the loop, then it remains true before the next iteration.

Question 17

Termination

Answer 17

When the loop is terminated, the invariant gives if a property which helps determine the correctness of the algorithm.

Question 18

Computational Model

Answer 18

CPU connected to a bank of memory cells, with each cell being able to store a number, address or character.
We use a set of high-level primitive operations, like assignment, method invocation, arithmetic operation, etc.

Question 19

Assumption of primitive operations

Answer 19

Primitive operations require constant time to perform.
So when analysing the running time of an algorithm, we count the number of operations executed during the course of the algorithm.

Question 20

Average-case Complexity

Answer 20

Running time as an average taken over all inputs of the same size.

Question 21

Worst-case Complexity

Answer 21

Running time as the maximum over all inputs of the same size.

Question 22

Worst Case Explanation

Answer 22

f(n) - runtime
g(n) - any arbitrary number

f(n) in O(g(n)) if, for constants c and place n_0:
f(n) <= c x g(n) for all n >= n_0

Essentially, for any point after n_0, the runtime of f(n) is always smaller than g(n).

Question 23

Common Functions in Big O Notation

Answer 23

O(log n)
O(n)
O(n^2)
O(n^k)
O(a^n)

Question 24

O(log n)

Answer 24

Logarithmic

Question 25

O(n)

Answer 25

Linear

Question 26

O(n^2)

Answer 26

Quadratic

Question 27

O(n^k)

Answer 27

Polynomial

Question 28

O(a^n)

Answer 28

Exponential

Question 29

Ω(g(n

Answer 29

f(n) - maps to runtime
g(n) - maps to any arbitrary number
f(n) in Ω(g(n)) if, for all constants c and place n_0:
f(n) >= c x g(n) for all n >= n_0

Question 30

Θ(g(n))

Answer 30

If f(n) in O(g(n)) and Ω(g(n)) then f(n) is also in Θ(g(n)).

Question 31

Asymptotic Notation

Answer 31

Allows characterisation of the main factor affecting running time.

Question 32

NP Completeness problem

Answer 32

Class P - problems that are efficiently solvable.
Class NP - problems that are efficiently verifiable.

Question 33

Proof by Mathematical Induction

Answer 33

1) Show hypothesis true for smallest value n
2) Assume hypothesis to be true for n = k and show it is true for n = k + 1

Question 34

Proof by Contradiction

Answer 34

Essentially, prove two different things which fall under the same law and how they contradict each other.

Question 35

Proof by Contrapositive

Answer 35

“If not-B then not-A” is the contrapositive of “if A then B”.
Essentially, proving the complete opposite statement.

Question 36

(Dis)Proof by Counterexample

Answer 36

Proving the statement is false by giving an opposite statement which is true.
“All dogs are hairy” can be disproved by finding one non-hairy dog.