Tech Notes by Aftab Mahmood
Algorithms
hash tables, heaps, binary trees, linked lists, depth-first search, recursion, merge
● Divide and conquer Algorithm: works by recursively breaking down a problem into two or more sub
problems of the same (or related type) until these become simple enough to be solved directly. The
solution to sub-problems are then combined to give a solution to the original problem.
○ Every algorithm that uses recursion or loops could be regarded as a divide-and-conquer
algorithm.
■ quick sort, merge sort,
■ binary search
■ multiplying large numbers, Karatsuba
■ syntactic analysis, top-down parsers
■ discrete Fourier transform
○ Divide and conquer typically splits the problem in half, solves each half, then stitches the halves
back together to form a full solution.
● Tail recursion or tail-end recursion is a special case of recursion in which last operation performed in a
recursive call.
○ Return a (usually simple) value without recursion.
● Dynamic programming typically removes one element from the problem, solves the smaller problem,
and then uses the solution to this smaller problem to add back the element in the proper way.
○ Dynamic programming is probably the easiest algorithm design technique to apply in practice.
● Greedy algorithms, which make the best local decision at each step
Analysis of Algorithms
Types of Analyses
● Best case - Running time determined by easiest input
● Worst case - Running time guarantee for all inputs
● Average case - Running time for random input
Commonly-used notations
● Tilde - provide approximate model
● Big Theta - classify algorithms
● Big Oh - develop upper bounds
● Big Omega - develop lower bounds
Map Reduce
,Big-O Notation:
1. Big-O notation provides an upper bound on the growth rate of the function.
2. Describes an algorithm’s usage of computational resources.
3. Expressed as a function of the length of its input using
4. O(N) describes an algorithm whose performance will linearly and in direct proportion to the
size of the input data set.
5. O(N^2) represents an algorithm whose performance is directly proportional to the square of
the size of the input data set.
6. If we have any input of size N, solving it will require at most f(N) steps.
● Bubble Sort O(n^2)
● Selection sort O(n^2)
● Quick Sort O(n^2)
● Heap Sort O(N log N)
● Big Theta is more tightly bound than Big O. mean there exists two constants c1 and c2 such
that c1n log n < f(n) < c2 log n
● Big Omega saya that the algorithen has a lower bound of c n log n
● Big O is not concerened with factors that do not chagne as the input increases.
● O(g) - asymptotic upper bound -
● omage Ω (g) - lower limit -
● theta θ(g) = O(g) ∩ Ω (g) - upper and lower bounds of a function are on the same order
of magnitude.
○ A funciton is in big-theta of f if its not much worse but also not much better than f
● There is no asymptotic notation to describe the average case.
● dont congfure best / average /worst case with asymptotic bounds.
Issues:
1. Too hard to analyze
2. Average case unknown
3. Unknown constant: Big-O analysis only tells you how it grows with the size of the problem,
not now efficient it is. e.g. Both walking and travelling at the speed of light have a
time-as-function-of-distance of complexity O(N). Altho they have the same big-o
characteristics, one is faster than other.
4. Small data set
Estimating for recursive and nested loops
● estimate the maximum number of times each loop can be executed.
● add these bounds for cycles following each other.
● multiply theses founds for nested cycles/parts of code.
● Time complexity of a while cycle is O(n).
, References:
● http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
Sorting
Approaches to Sorting
● Selection of Data Structures
● Incremental Insertion Technique
○ a particularly useful technique in geometric algorithms
● Divide and Conquer Technique
○ Mergesort is a classic divide-and-conquer algorithm
● Randomization Technique
○ In quicksort, we separate the n-1 other items into two piles: a low pile containing all the elements
that will appear before p in sorted order and a high pile containing all the elements that will appear
after p in sorted order. After sorting the two piles and arranging the piles correctly, we have
succeeded in sorting the n items.
● Bucketing Techniques
○ Bucketing is a very effective idea whenever we are confident that the distribution of data will be
roughly uniform. It is the idea that underlies hash tables, kd-trees, and a variety of other
practical data structures. The downside of such techniques is that the performance can be
terrible whenever the data distribution is not what we expected.
Sorting methods:
● Insertion, selection, merge, exchange, partitioning
● in other words: Swap based, Merge based, Tree based
● cost of sorting - comparisons and exchanges
Stability:
● Stable sorting algorithms maintains the relative order of records with equal keys.
○ one way of doing this to artificially extend the key comparision, so that comparisons between
two objects with othwerwise equal keys are decided using the order of the entries in the original
data order as a tie-breaker.
○ (4, 2) (3, 7) (3, 1) (5, 6) can be sorted in two way
○ (3, 7)..(3, 1)......
○ (3, 1)..(3, 7).......
Algorithms
hash tables, heaps, binary trees, linked lists, depth-first search, recursion, merge
● Divide and conquer Algorithm: works by recursively breaking down a problem into two or more sub
problems of the same (or related type) until these become simple enough to be solved directly. The
solution to sub-problems are then combined to give a solution to the original problem.
○ Every algorithm that uses recursion or loops could be regarded as a divide-and-conquer
algorithm.
■ quick sort, merge sort,
■ binary search
■ multiplying large numbers, Karatsuba
■ syntactic analysis, top-down parsers
■ discrete Fourier transform
○ Divide and conquer typically splits the problem in half, solves each half, then stitches the halves
back together to form a full solution.
● Tail recursion or tail-end recursion is a special case of recursion in which last operation performed in a
recursive call.
○ Return a (usually simple) value without recursion.
● Dynamic programming typically removes one element from the problem, solves the smaller problem,
and then uses the solution to this smaller problem to add back the element in the proper way.
○ Dynamic programming is probably the easiest algorithm design technique to apply in practice.
● Greedy algorithms, which make the best local decision at each step
Analysis of Algorithms
Types of Analyses
● Best case - Running time determined by easiest input
● Worst case - Running time guarantee for all inputs
● Average case - Running time for random input
Commonly-used notations
● Tilde - provide approximate model
● Big Theta - classify algorithms
● Big Oh - develop upper bounds
● Big Omega - develop lower bounds
Map Reduce
,Big-O Notation:
1. Big-O notation provides an upper bound on the growth rate of the function.
2. Describes an algorithm’s usage of computational resources.
3. Expressed as a function of the length of its input using
4. O(N) describes an algorithm whose performance will linearly and in direct proportion to the
size of the input data set.
5. O(N^2) represents an algorithm whose performance is directly proportional to the square of
the size of the input data set.
6. If we have any input of size N, solving it will require at most f(N) steps.
● Bubble Sort O(n^2)
● Selection sort O(n^2)
● Quick Sort O(n^2)
● Heap Sort O(N log N)
● Big Theta is more tightly bound than Big O. mean there exists two constants c1 and c2 such
that c1n log n < f(n) < c2 log n
● Big Omega saya that the algorithen has a lower bound of c n log n
● Big O is not concerened with factors that do not chagne as the input increases.
● O(g) - asymptotic upper bound -
● omage Ω (g) - lower limit -
● theta θ(g) = O(g) ∩ Ω (g) - upper and lower bounds of a function are on the same order
of magnitude.
○ A funciton is in big-theta of f if its not much worse but also not much better than f
● There is no asymptotic notation to describe the average case.
● dont congfure best / average /worst case with asymptotic bounds.
Issues:
1. Too hard to analyze
2. Average case unknown
3. Unknown constant: Big-O analysis only tells you how it grows with the size of the problem,
not now efficient it is. e.g. Both walking and travelling at the speed of light have a
time-as-function-of-distance of complexity O(N). Altho they have the same big-o
characteristics, one is faster than other.
4. Small data set
Estimating for recursive and nested loops
● estimate the maximum number of times each loop can be executed.
● add these bounds for cycles following each other.
● multiply theses founds for nested cycles/parts of code.
● Time complexity of a while cycle is O(n).
, References:
● http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=complexity1
Sorting
Approaches to Sorting
● Selection of Data Structures
● Incremental Insertion Technique
○ a particularly useful technique in geometric algorithms
● Divide and Conquer Technique
○ Mergesort is a classic divide-and-conquer algorithm
● Randomization Technique
○ In quicksort, we separate the n-1 other items into two piles: a low pile containing all the elements
that will appear before p in sorted order and a high pile containing all the elements that will appear
after p in sorted order. After sorting the two piles and arranging the piles correctly, we have
succeeded in sorting the n items.
● Bucketing Techniques
○ Bucketing is a very effective idea whenever we are confident that the distribution of data will be
roughly uniform. It is the idea that underlies hash tables, kd-trees, and a variety of other
practical data structures. The downside of such techniques is that the performance can be
terrible whenever the data distribution is not what we expected.
Sorting methods:
● Insertion, selection, merge, exchange, partitioning
● in other words: Swap based, Merge based, Tree based
● cost of sorting - comparisons and exchanges
Stability:
● Stable sorting algorithms maintains the relative order of records with equal keys.
○ one way of doing this to artificially extend the key comparision, so that comparisons between
two objects with othwerwise equal keys are decided using the order of the entries in the original
data order as a tie-breaker.
○ (4, 2) (3, 7) (3, 1) (5, 6) can be sorted in two way
○ (3, 7)..(3, 1)......
○ (3, 1)..(3, 7).......
