Algorithms Flashcards
What is runtime
A function f: N -> N, which maps the input size to the number of elementary operations completed
How to compare asymptotic complexity of functions
What is the racetrack principle
How does Fast Peak Finding work
Imagine the array is sloping downwards, then there must be a peak to the left and vice versa; perform binary search to get the peak
Log laws
n = 2^log(n) (base 2)
Derivative of log(n) (base 2)
Sum of arithmatic sequence formula
Sum of geometric sequence formula
What is big O notation
Runtime complexity hierarchy
How to prove/disprove that a function is in O(n)
Composing two functions effect on O notation
Loop / multiplying functions effect on O notation
Loop / multiplying functions effect on O notation
What are the 5 steps of merge sort
1) If n = 1 return A
2) Recursively sort left sub-array
3) Recursively sort right sub-array
4) Merge together the two arrays
5) Return the sorted array
How does the tree diagram of merge sort look like
What are the steps of a divide and conquer algorithm
1) Divide into smaller subproblems
2) Conquer sub-problems
3) Merge back up the tree to find a general solution
What does it mean for an algorithm to be in-place
It means that no auxillary arrays are used. At most O(1) elements stored outisde array
What does it mean for an algorithm to be stable
The ordering of elements are not un-neededly swapped. Ex: If A[i] = A[i+1] they will not be swapped. Useful for satilite data
Is insertion sort stable and in-place
Insertion sort is both stable and in-place
Is merge sort stable and in-place
Merge sort is stable but not in-place since it uses auxillary arrays in the merge step
How does the merge step work in mergesort (4 steps)
Require both halves of A are sorted
1) Copy left half into auxillary array B
2) Copy right half into auxillary array C
3) Merge B and C in sorted order
4) Return result
How is a loop represented in sigma notation
What type of binary tree is mergesort
Complete binary tree
What is a full binary tree
Each element has either 0 or 2 children
What is the runtime of mergesort
O(nlogn)
What is the depth of the tree for a divide and conquer algorithm which splits in half at each step
log(n) (base 2)
What is the general runtime for most divide and conquer algorithms
O(nlogn)
How to determine the runtime of a divide and conquer algorithm
Look at how long each node takes to complete, the amount of nodes per level and the number of levels
What is the maximum subarray problem
What are the 3 cases for the maximum subarray problem
If it is included in L then can recursively solve, same for R. However if spans across the middle then will need to find the indices.
How to find the indices for i,j for when the maximum subarray crosses the midpoint
Can be broken into two subproblems, maximising A[i,n/2] and A[n/2,j], thus can just loop through all values to find which gives the highest result. Takes O(n) time.
What are the 5 steps for the maximum sub array problem d&c algorithm
1) If n=1 return A
2) Recursively compute the max subarr for L
3) Recursively compute max subarr for R
4) Compute the max subarr that crosses the midpoint
5) Compare all these arrays and return the greatest one
What is the definition of theta notation
What is the symetry of theta notation
How does theta notation relate to big-o
What is the definition of omega notation
How does omega notation relate to big-o
How does the RAM model work ( what can be done in a single time-step)
How does the RAM model work (memory-wise)
What are the two costs of an algorithm according to the RAM model
What does the RAM model mean about the O() for each operation
Every operation of our algorithm can be implemented in O(1) elementary operations in the RAM model
How are loops expressed as sums
Note: k would be the runtime of the inner loop
What is the formula for best case runtime
What is the formula for worst case runtime
What is the formula for average case runtime
What is the algorithm for linear search
What is the best and worst case runtime for linear search
Worst case: O(n)
Best case: O(1)
What is the average case runtime for linear search on a binary array
Average case O(1)
In O(1)
What is the algorithm for binary search
Worst case runtime of binary search
O(logn)
What are the steps of proof by induction
What is strong induction
What is a loop invariant
A loop invariant is a property P that, if true before iteration i, it is also true before iteration i + 1
What are the steps to prove a loop invariant
Note: true before itteration i+1 is the same as being true after itteration i; assume true for before itteration i.
What is the difference between a formal and informal loop invariant proof with 2 nested for loops
Informal: can just say what the nested loop is doing
Formal: need a separate invariant for the nested for loop
What is the algorithm for insertion sort
Note: works by inserting each element into correct position in growing ‘safe area’
What is the main loop invariant for insertion sort
The sub-array safe area A[0,j-1] is sorted before itteration j
What is the best and worst case runtime for insertion sort and why
Best case: O(n) -> goes through array once
Worst case: O(n^2)
What is the definition of a tree
What is the definition of a rooted tree
What is the definition of a leaf and an internal node?
What is a parent node of v (a node in a tree)
- The parent of a node v is the closest node on a path from v to the root.
- The root does not have a parent
What is a child node of v (a node in a tree)
The children of a node v are v’s neighbours except its parent.
What is the height of a tree
The height of a tree is the length of a longest root-to-leaf
path (number of edges).
What is the degree of a node? And what is the total degree of every node in the tree?
What is the level of a vertex (node) v in a tree?
The level of a vertex v is the length of the unique path from the root to v plus 1.
Is it possible for a tree to have less than two leafs
No
What is a full, complete and perfect k-ary tree?
What is the number of nodes in a k-ary tree based on its height?
Height = # levels -1
What is the height of a perfect k-ary tree based its number of nodes
Reminder: height = # levels -1.
In addition: A complete k-ary tree also has height of O(log_k(n))
Is it possible to sort faster than O(nlogn)
Yes with knowleedge of the data (ie only integers), however not possible to sort faster than O(nlogn) using comparison based sorting (sorting anything).
How can you sort a binary array in O(n)
What is the premise of comparison based sorting? And what are some example algorithms?
What is the lower bound for comparison based sorting
OMEGA(nlogn)
How many possible orderings are there for an array of size n
n!
What is a comparison sorting decision tree? How many leafs and what is the height?
n! leaves (for each permuation)
To accomodate n! leaves 2^h >= n!, the height is log(n!) = OMEGA(nlogn).
The height is the amount of decisions needed.
What is Stirling’s approximation?
Is heap sort in place and/or stable?
Heap sort is in-place but is not stable (due to way elements are rearranged in the heap - and root swapped with last element)
What are the two functions of a priority queue structure?
How is an array interpreted as a tree (and what is the location of a parent, l-r child of any node)
What is the heap property
How is a heap constructed from an array (build(.))
What does the function Heapify() do
Traverses from current node to bottom of array (in a single path), swapping elements if they don’t fufill the heap property.
What are the steps of Heapify()
What is the runtime of Heapify() and why
What is the runtime for constructing a heap?
You would think O(nlogn) since for n nodes * runtime of heapify O(logn), however given the fact that trees are bottom heavy, computing the sum actually gives O(n)
What are the steps of heapsort
What is the runtime of heapsort
What is the worst case + average case runtime of QuickSort and why is it used?
Worst case: O(n) - bad pivot
Average case: O(nlogn)
It is used because in practice is much faster than most other sorting algorithms (the hidden constants are small)
Is QuickSort stable and in-place?
QuickSort is in-place but is not stable, due to the way it swaps elements (a larger elem initially to the left could be swapped with a smaller elem to the right)
What are the divide, conquer and combine steps of QuickSort
nHow does the partition function of QuickSort work and what is its runtime
Runtime O(n)
How does quicksort work (visualised)
What is the main loop invariant for quicksort?
Assuming x is the pivot
What is the psuedocode for QuickSort?
How is the quicksort runtime calculated
Partitioning takes O(n) meaning total of O(n) per level (as nodes sum to n)
Runtime = n * L (number of levels) -> = O(nlogn) if a ‘good’ split is selected
What is the general runtime recurrence for QuickSort
What is the best and worst case splits for QuickSort
Worst case: Largest or Smallest
Best case: median
What does the worst case QuickSort recursion tree look like
What does the best-case QuickSort recursion tree look like
What does the best-case QuickSort recursion tree look like
What distinguishes a good and bad QuickSort split
What is the recursion tree for QuickSort with only good splits
Recurses until n = 1, so log(n)+1
What does the recursion tree for QuickSort look like with alternating good/bad splits
How is pivot selection typically done in QuickSort
While it is possible to use an O(n) algorithm to find median, in practice it is better to use a random pivot since algorithm will make enough progress leading to O(nlogn)
What type of algorithms are recurrences especially useful for
Divide and conquer algorithms
What is the general format for a recurrence
Base case: T(1) =1
General case: T(n) = 2T(n/2) + O(n) – or can just write n
The number of recurrences along with their magnitude (in terms of n elements passed) plus the time taken for this recursive step O(n).
What 3 methods can be used for solving recurrences
What are the 3 steps of the substitution method for solving recurrences
1) Guess a good upper bound
2) Substitute into the general equation and solve to show the guess is larger than substituted value
3) Verify base case (can increase base case if needed)
How do you solve the following problem
Add a minus one at the end
What is the premise of drawing a recursion tree for the recursion tree method
- Each node represents the local-cost of a sub-problem (the non recursive element in the recurence with the current value of n)
- Recursive invocations become children of a node
- Compute sum per level (and # level until n=1) then add up
- This gives a good gues for the substitution method
How to deal with upper and lower bounds in recursion tree method
Discard them - only need a vague guess
Sum of infinite geometric series formula
How to find the number of levels of a recursion tree
Determine at what rate the size of n is getting smaller and set it equal to one
Is it possible to sort integers faster than O(nlog(n))
Yes using counting sort or radix-sort
What is the psuedocode for counting sort
What are the steps of counting sort
1) Using aux-array count how often each element appears
2) Count how many smaller elements appear
3) Go through initial array (right-to-left) and insert element at counted position (-1) and decrement count
What is the runtime of counting sort
O(n+k) where k is the highest integer in the array
Is counting sort stable and in-place?
Yes is stable but not in-place since it uses aux arrays
What is the psuedo-code for Radixsort
Sort from lowest to highest usually
What is the runtime of radixsort
O(d(n+b)) – b is base and d is number of digits
How do you compute the fibonacci series using a dynamic programming algorithm
Either store all values, or just last two
What is a method for working out solution to pole-cutting
For each element, starting with the lowest one, work out the optimal revenue. Scan through the array with the price of the legnth of a single cut and the cuts from previous entries to find the optimal cut for each entry.
Assumption: R(i) = P(i_1) + R(i_2) for i_1 + i_2 = i
What is the optimal substructure property
Optimal substructure is a key property for dynamic programming that asserts that the optimal solution of a problem can be constructed efficiently from the optimal solutions of its subproblems. In other words, if a problem can be broken down into smaller subproblems, which can be independently solved optimally, then these optimal solutions can be used to solve the original problem optimally as well.
What is the optimal substructure of pole cutting
In the rod cutting problem, the optimal solution for a rod of length ‘n’ is achieved by maximizing profit from all possible cut lengths ‘i’. If ‘P[i]’ represents the maximum profit from a rod of length ‘i’, the optimal substructure can be summarized as:
P[n] = max(p_i + P[n-i]) for 1 <= i <= n
This equation means that the best profit comes from the best choice of initial cut plus the best profit from the remainder.
The first piece is considered a single cut with no recursive sub cuts, this is accounted for in the 2nd part
What is bottom up psuedo-code for the dynamic programming approach to polecutting
What is the difference between top-down and bottom up dynamic programming
**Top-down (Memoization): **Begins with the original problem, breaks it into subproblems, and stores the results of each subproblem to avoid duplicate work. It uses recursion and starts solving the problem from the ‘top’, using the results of smaller subproblems as needed.
Bottom-up (Tabulation): Starts from the simplest subproblem and iteratively solves larger subproblems using the results. It typically involves filling up an n-dimensional table in a manner that avoids redundant calculations. It’s more efficient in terms of function calls and stack space as it’s iterative, not recursive.
