Algorithms Flashcards
What is an algorithm?
An algorithm is a sequence of steps for performing a task in a finite amount of time.
What is a data structure?
For computational algorithms, we use data structures to store, access, and manipulate data.
Questions to decide which search to use
- 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?
Types of algorithm analysis
- Running time
- Space usage
- Optimality of the output solution
Experimental Analysis
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.
Drawbacks of experimental analysis
- Limited test of inputs
- Requires all tests to be performed hardware and software
- Requires implementation and execution of algorithm
Theoretical Analysis
More theory based approach of finding running time of algorithms.
Theoretical Analysis Benefits
- Can take all possible inputs into account.
- Involves studying high-level descriptions of algorithms
- Can compare efficiency of two algorithms
Theoretical Analysis Functions
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.
Theoretical Analysis Requirements
- a language to describe algorithms
- computational model in which algorithms are executed
- metric for running time
- a way of characterising running time
Pseudo-code
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.
Correctness
An algorithm is correct with respect to a specification if it behaves as specified.
Loop Invariant
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.
Loop Invariant Properties
- intialisation
- maintenance
- terminantion
Initalisation (Loop Invariant)
Remains true prior to the first iteration of the loop.
Maintenance
If it remains true before an iteration of the loop, then it remains true before the next iteration.
Termination
When the loop is terminated, the invariant gives if a property which helps determine the correctness of the algorithm.
Computational Model
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.
Assumption of primitive operations
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.
Average-case Complexity
Running time as an average taken over all inputs of the same size.
Worst-case Complexity
Running time as the maximum over all inputs of the same size.
Worst Case Explanation
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).
Common Functions in Big O Notation
O(log n)
O(n)
O(n^2)
O(n^k)
O(a^n)
O(log n)
Logarithmic
O(n)
Linear
O(n^2)
Quadratic
O(n^k)
Polynomial
O(a^n)
Exponential
Ω(g(n
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
Θ(g(n))
If f(n) in O(g(n)) and Ω(g(n)) then f(n) is also in Θ(g(n)).
Asymptotic Notation
Allows characterisation of the main factor affecting running time.
NP Completeness problem
Class P - problems that are efficiently solvable.
Class NP - problems that are efficiently verifiable.
Proof by Mathematical Induction
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
Proof by Contradiction
Essentially, prove two different things which fall under the same law and how they contradict each other.
Proof by Contrapositive
“If not-B then not-A” is the contrapositive of “if A then B”.
Essentially, proving the complete opposite statement.
(Dis)Proof by Counterexample
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.
