Algorithms Cheat Sheet PDF

Preview

Summary

Download Algorithms Cheat Sheet PDF

Description

Note! Key-Comparison based sorting is proven to be: 𝛺(𝑛𝑙𝑜𝑔𝑛)

Algorithm

Approach

Complexity Class

Properties/Useful in

Selection Sort

Brute Force

𝜃(𝑛2 ) for all inputs. 𝜃(𝑛) key swaps

Good for sorting small collections of large records. Stable: No In-Place: Yes Input insensitive: Yes

Bubble Sort

Brute Force

𝜃(𝑛2 ) Worst: 𝜃(𝑛2 ) key swaps

Sequential Search

Brute Force

Worst: 𝑂(𝑛) Average: 𝑂(𝑛)

String Match

Brute Force

Worst: 𝑂(𝑛𝑚) Average (NL): 𝜃(𝑛)

Closest Pair

Brute Force

All: 𝜃(𝑛2 )

Assignment Problem

Exhaustive Search

All permutations: 𝑂(𝑛!)

DFS

Exhaustive Search

Adj. matrix: 𝜃(|𝑉|2 ) Adj. list: 𝜃(|𝑉| + |𝐸|)

All Exhaustive Search Can’t be avoided. Check the Hungarian method algorithm. •

Checking connectivity, checking acyclicity of a graph.

Algorithm

Approach

Complexity Class

Properties/Useful in •

Used in Topsort

BFS

Exhaustive Search

Adj. matrix: 𝜃(|𝑉|2 ) Adj. list: 𝜃(|𝑉| + |𝐸|)

Checking connectivity, checking acyclicity • Finding path with least number of edges between 2 nodes.of a graph.

Insertion Sort

Decrease and Conquer (by a constant)

Worst (decreasing order): 𝜽(𝒏𝟐 ) Best (already/almost sorted): 𝜽(𝒏) 1 Average (randomly ordered): 𝑡ℎ𝑒 𝑤𝑜𝑟𝑠𝑡 but still 𝜽(𝒏𝟐 ) 2

Iterative: bottom-up; 0 → n-1 Works well with almost sorted inputs. Best Use case: for small arrays (100s of elements). Stable: Yes In-Place: Yes Input insensitive: No

Shell Sort

Decrease and Conquer (by a constant)

Worst: 𝑶(𝒏√𝒏)

Break down the input into k interleaving lists, sort each using insertion sort. The output becomes

•

Algorithm

Approach

Complexity Class

Properties/Useful in almost sorted array, then run insertion sort. Best Use case: for medium-size arrays (~10,000). Stable: No In-Place: Yes Input insensitive: No

Topological Sorting (Topsort)

Decrease and Conquer (by a constant)

Binary Search

Decrease and Conquer (by a constant factor)

-

Worst: 𝜽(𝐥𝐨𝐠 𝒏) Average: 𝜽(𝐥𝐨𝐠 𝒏)

Finding Median • • •

Lomuto Partitioning

Topsort here is the one done by removing source.

n-1 comparison per run

All about finding the smallest element. Start by sorting (). Sorting is too much, we do partitioning.

Algorithm

Approach

Complexity Class

Properties/Useful in

Quick Select

Decrease and Conquer (by a Variable)

Worst: 𝑶(𝒏𝟐 ) Average: 𝑶(𝒏)

Worst Case: k is n (last element in the array), and it is a strictly increasing array. Requires (n-1) for each (n-1) comparison, end up being quadratic.

Interpolation Search

Decrease and Conquer (by a Variable)

Worst: (linear) Average: 𝜽(𝐥𝐨𝐠 𝐥𝐨𝐠 𝒏)

Best Use case: for large arrays if the elements are uniformly distributed. 𝑘 − 𝐴[𝑙𝑜] 𝑚𝑖𝑑 = 𝐴[𝑙𝑜] + | . (ℎ𝑖 𝐴[ℎ𝑖] − 𝐴[𝑙𝑜] − 𝑙𝑜)|

Merge Sort

Divide and Conquer

Worst: 𝜽(𝒏 𝐥𝐨𝐠 𝒏) Average: 75% of worst.

For large n: number of comparisons is around 75% of the worst case. Guaranteed performance. Heapsort < MergeSort < QuickSort Best Use case: • Linked lists • Very large collection of data Stable: Yes In-Place: No Input insensitive: No

Quick Sort

Divide and Conquer

Worst (already sorted input): 𝜽(𝒏𝟐 ) Best (when the pivot is median): 𝜽(𝒏 𝐥𝐨𝐠 𝒏) Average: 𝟏. 𝟑𝟖 𝐥𝐨𝐠 𝒏

Best case: if the pivot value is the median. Worst case: if the array is already sorted. Improved by: median-of-three selection of pivot.

Algorithm

Approach

Complexity Class

Properties/Useful in Best Use case: with arrays of random data. Quick sort is faster on average than MergeSort. Stable: No In-Place: Yes Input insensitive: No

Tree Height Calc

Divide and Conquer

2n+1 comparisons i.e. 𝜽(𝒏)

Closest Pair

Divide and Conquer

General: 𝜽(𝒏 𝐥𝐨𝐠 𝒏)

Transform and Conquer Heap

Height: log 𝑛 Injection/Ejection: 𝑶(𝐥𝐨𝐠 𝒏) Bottom-Up creation: 𝑶(𝒏)

Heap Sort

θ(𝑛 log 𝑛) θ(𝑛)𝑓𝑜𝑟ℎ𝑒𝑎𝑝𝑐𝑟𝑒𝑎𝑡𝑖𝑜𝑛, θ(𝑙𝑜𝑔𝑛)𝑓𝑜𝑟𝑒𝑗𝑒𝑐𝑡𝑖𝑜𝑛(𝑑𝑒𝑝𝑙𝑒𝑡𝑖𝑛𝑔)

Priority Queue Operations: find: finds an item with maximal priority insert: insert item with associated priority. eject: ejects the largest element. On average is slower than Quick Sort, but stronger performance guarantee. Stable: No In-Place: Yes Input insensitive: No

Algorithm

Approach

Complexity Class

Properties/Useful in

Search: Worst case for Balanced trees: 𝛉(𝒍𝒐𝒈𝒏) Worst case for Unbalanced trees: 𝑶(𝒏)

Binary Search Trees

Insertion: Doing the search: 𝜃(𝑙𝑜𝑔𝑛) for balanced trees. AVL trees

Transform n Conquer: Instance simplification

Depth: θ(𝑙𝑜𝑔𝑛) Best case (random data): θ(𝑙𝑜𝑔2 𝑛) Worst case: 45% more of best case. Insertion: θ(𝑙𝑜𝑔𝑛) Deletion: θ(𝑙𝑜𝑔𝑛)

Re-balancing occurs at the lowest unbalanced sub-tree.

2-3 Trees

Transform n Conquer: Representational change

Insertion: binary search operation: 𝑂(𝑙𝑜𝑔𝑛) Worst case (all nodes are 2-nodes): 𝑙𝑜𝑔2 (𝑛 + 1) Best case (all nodes are 3-nodes): 𝑙𝑜𝑔3 (𝑛 + 1)

Operations: Insert, split, promote

Sorting by Counting

Time vs. Space Tradeoff.

Gives: 𝑂(𝑛)

Requires extra space. Only works with a small range of keys known in advance. • Original Array • Count Array • Cumulative Count Array • Sorted Array. Stable: Yes

Complexity Class

Properties/Useful in

Horspool’s Algorithm

Worst case (all pattern match except last character): 𝑶(𝒎𝒏) In practice: 𝑂(𝑛) Best case (when input text contains no characters from the pattern): 𝑂(𝑚/𝑛)

m: size of the pattern to be matched. n: size of the string. In practice: use in English text.

Hashing

Search, Insert, Delete operations: Worst: 𝜃(𝑛) Average: 𝜃(1) Separate chaining: No or probes - Successful: (1 + 𝛼)/2 No or probes - Unsuccessful: α Linear probing: Successful: 0.5 + (1/(2(1 − α))) Unsuccessful: 0.5 + 1/(2(1 − α)2 )

Doesn’t preserve the order of items. Hash Table operations: • Find • Insert • Initialise • Delete • Rehash Separate Chaining: Use case: when number of keys can’t be predicted. Linear probing: Keep α...