Algorithms/ solving Problems Flashcards
existence problem
determining if there is a solution
construction problem
finding a solution to the problem
enumeration
finding how many solutions there are to a problem
optimisation
finding the best solution to a problem
pigeon hole principal
if there are m pigeonholes and n pigeons, where m
proper subset
a part of a set that is smaller than the original set
number of ways of arranging n objects where non are repeated
n!
if there are n numbers and r positions to arrange them and a number cannot be repeated then the number of ways of arranging the numbers is
n!/(n-r)!
choosing n items from a set of r where the order doesn’t matter
r!/n!
The number of combinations of r objects from n is
n!/(n-r)!r!
inclusion exclusion principal
|AUBUC| = |A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|
order of an algorithm
The value with the largest exponent with the coefficient
Bin packing algorithms
next-fit
first-fit
first-fit decreasing
Comparisons in bubble sort
decrements with each pass
Comparisons in shuttle sort
random
If there are no swaps in bubble sort
the list is sort
what is the maximum number of passes for a bubble sort algorithm
n - 1
n is the number of passes
finding the lower bound for a bin packing algorithm
adding all the contents and dividing it by the bin size. This gives minimum number of bins to be used.
Quadratic complexity
Doubling the size of the problem results in four times the effort
Linear complexity
Doubling the size of the problem doubles the effort
worst case time complexity of a quick sort
O(n^2)
if the list in in reverse order
first fit decreasing in 3D
sort by length, height, perimeter or area
Knapsack problems
- workout value per kg
- the highest value per kg should go in the knapsack
- the remaining knapsack can be filled optimally by trial and error
Derangement formula
Dn = (n-1)(Dn-2)(Dn-1)
For passwords…
use selections n!/(n-r)!
