This is a rather crude summary I created before my exam - there are some omissions, most notably dynamic programming. I do recommend reading the other notes if possible.
- A sequence of unambiguous instructions for solving a well-defined problem. Algorithms are guaranteed to terminate if the input is valid.
- Algorithms are a subset of procedures, which aren't guaranteed to terminate.
- Finite
- Terminates after a finite number of steps
- Definite
- Rigorously and unambiguously specified
- Inputs
- Valid inputs are clearly specified
- Output
- Can be proved to produce the correct output given a valid input
- Effective
- Steps are sufficiently simple and basic
- Each step of the algorithm must be unambiguous
- The range of inputs must be specified carefully.
- The same algorithm can be represented in different ways AND Several algorithms for solving the same problem may exist - with different properties
- Understand the problem
- Decide on computational means
- Design an algorithm
- Prove correctness
- Analyze the algorithm
- Code algorithm
Another representation of the above 6 steps:
- Efficiency: time and space
- Simplicity
- Generality: range of inputs, special cases
- Optimality: no other algorithm can do better
- Brute Force
- Try all possibilities
- Decrease & Conquer
- Solve large instance in terms of smaller instance
- Divide & Conquer
- Break problem into distinct subproblems
- Transform & Conquer
- AKA Transformation
- Covert problem to another one
- Trading Space & Time
- Use additional data structures
- Dynamic Programming
- Break problem into overlapping subproblems
- Greedy
- Repeatedly do what is best now
-
Definition: f(n) ∈ O(g(n)) iff there exists positive constant c and non-negative integer n0 such that ** f(n) <= c g(n)* for every n >=n0
-
Definition: f(n) ∈ Ω(g(n)) iff there exist positive constant c and non-negative integer n0 such that
- f(n) >= c g(n) for every n >= n0
-
Definition: f(n) ∈ Θ(g(n)) iff there exist positive constants c1 and c2 and non-negative integer n0 and non-negative integer n0 such that
- c1 g(n) <= f(n) <= c2 g(n) for every n >= n0
-
O(g(n)): functions that grow no faster than g(n)
-
Ω(g(n)): functions that grow at least as fast as g(n)
-
Θ(g(n)): functions that grow at same rate as g(n)
-
O(g(n)): functions no worse than g(n)
-
Ω(g(n)): functions at least as bad as g(n)
-
Θ(g(n)): functions as efficient as g(n)
- O is an upper bound on performance
- Θ is a tight bound
- It is the upper and lower bound
A straightforward approach usually directly based on problem statement and definitions
- Crude but often effective
- Simple
- Widely Applicable
- Sometimes impractically slow
- Try all the possibilities until problem solved
- Loop through each possibility, check if it solves problems
- Strengths
- Wide applicability
- Simplicity
- Yields reasonable algorithm for some important problems and standard algorithms for simple computational tasks
- A good yardstick for better algorithms
- Sometimes doing better is not worth the bother
- Weakness
- Rarely produces efficient algorithms
- Some brute force algorithms are infeasibly slow
- Note as creative as some other design techniques
- Definition
- A brute force solution to the search for an element with a special property
- Usually among combinatorial objects such a permutations or subsets
- Suggests generating each and every element of the problem's domain
- Method
- Construct a way of listing all potential solutions to the problem in a systematic manner
- Evaluate all Solutions one by one (disqualifying infeasible ones) keeping track of the best one found so far
- When search ends, announce the winner
- Exhaustive search algorithms run in a realistic amount of time only on very small instances
- In many cases there are much better alternatives!
- In some cases exhaustive search (or variation) is the only known solution
- and parallel solutions can speed it up
If we have a recurrence of this form:
T(n) = aT(n/b) + f(n) and f(n) ∈ Θ (n2) then:
- T(n) ∈ Θ(nd) if a < bd
- T(n) ∈ Θ(ndlogn) if a = bd
- T(n) ∈ Θ(nlogba) if a > bd
- Divide & Conquer is the best known algorithm design strategy:
- Divide instances of problem into two or more smaller instances
- Solve smaller instances recursively
- Obtain solution to original (larger) instance by combining these solutions
- Decrease by a constant
- Decrease by a constant factor
- Variable size decrease
- Reduce problem instance to smaller instance of the same problem and extend solution
- Solve smaller instance
- Extend solution of smaller instance to obtain solution to original problem
- Also called inductive or incremental
Strengths
- Can be implemented either top down (recursively) or bottom up (without recursion)
- Often very efficient (possibly Θ(logn))
- Leads to a powerful form of graph traversal (breadth and depth first search)
Weakness
- Less widely applicable (especially decrease by a constant factor)
The secret of life is to replace one worry with another
👆 Charles M. Schultz
Different types of transformations:
- Instance simplification = a more convenient instance of the same problem
- Presorting
- Gaussian elimination
- Representation Change = a different representation of the same instance
- Balanced search trees
- Heaps and heapsort
- Polynomial evaluation by Horner's rule
- Binary exponentiation
- Problem reduction = a different problem altogether
- Lowest Common Multiple
- Reductions to graph problem
- Pre-sorting
- Closest pair
- Convex hull
- Text of length n and Pattern P[0 ... m-1]
- Shift table called T:
- T(X) = m-1- rightmost index of x in P[0 ... m-2]
- T(X) = m if x is not in position P[0 ... m-2]
- Horspool
- When there is a mismatch, shift pattern T[c] places where c is the last character currently aligned against the pattern
- Boyer-Moore's Bad Character rule
- When there's a mismatch, calculate from the back, k, number of characters that matched
- Shift pattern max(T(c)-k,1) where c is the mismatched character