Algorithms Flashcards
1
Q
What is runtime
A
A function f: N -> N, which maps the input size to the number of elementary operations completed
2
Q
How to compare asymptotic complexity of functions
A
3
Q
What is the racetrack principle
A
4
Q
How does Fast Peak Finding work
A
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
5
Q
Log laws
A
n = 2^log(n) (base 2)
6
Q
Derivative of log(n) (base 2)
A
7
Q
Sum of arithmatic sequence formula
A
8
Q
Sum of geometric sequence formula
A
9
Q
What is big O notation
A
10
Q
Runtime complexity hierarchy
A
11
Q
How to prove/disprove that a function is in O(n)
A
12
Q
Composing two functions effect on O notation
A
13
Q
Loop / multiplying functions effect on O notation
A
13
Q
Loop / multiplying functions effect on O notation
A
14
Q
What are the 5 steps of merge sort
A
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
15
Q
How does the tree diagram of merge sort look like
A
16
Q
What are the steps of a divide and conquer algorithm
A
1) Divide into smaller subproblems
2) Conquer sub-problems
3) Merge back up the tree to find a general solution
17
Q
What does it mean for an algorithm to be in-place
A
It means that no auxillary arrays are used. At most O(1) elements stored outisde array
18
Q
What does it mean for an algorithm to be stable
A
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
19
Q
Is insertion sort stable and in-place
A
Insertion sort is both stable and in-place
20
Q
Is merge sort stable and in-place
A
Merge sort is stable but not in-place since it uses auxillary arrays in the merge step
21
Q
How does the merge step work in mergesort (4 steps)
A
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
22
Q
How is a loop represented in sigma notation
A
23
Q
What type of binary tree is mergesort
A
Complete binary tree
24
What is a full binary tree
Each element has either 0 or 2 children
25
What is the runtime of mergesort
O(nlogn)
26
What is the depth of the tree for a divide and conquer algorithm which splits in half at each step
log(n) (base 2)
27
What is the general runtime for most divide and conquer algorithms
O(nlogn)
28
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
29
What is the maximum subarray problem
30
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.
31
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.
32
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
33
What is the definition of theta notation
34
What is the symetry of theta notation
35
How does theta notation relate to big-o
36
What is the definition of omega notation
37
How does omega notation relate to big-o
38
39
How does the RAM model work ( what can be done in a single time-step)
40
How does the RAM model work (memory-wise)
41
What are the two costs of an algorithm according to the RAM model
42
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
43
How are loops expressed as sums
## Footnote
Note: k would be the runtime of the inner loop
44
45
What is the formula for best case runtime
46
What is the formula for worst case runtime
47
What is the formula for average case runtime
48
What is the algorithm for linear search
49
What is the best and worst case runtime for linear search
Worst case: O(n)
Best case: O(1)
50
What is the average case runtime for linear search on a **binary array**
Average case O(1)
51
In O(1)
52
What is the algorithm for binary search
53
Worst case runtime of binary search
O(logn)
54
What are the steps of proof by induction
55
What is strong induction
56
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
57
What are the steps to prove a loop invariant
## Footnote
Note: true before itteration i+1 is the same as being true after itteration i; assume true for before itteration i.
58
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
59
What is the algorithm for insertion sort
## Footnote
Note: works by inserting each element into correct position in growing 'safe area'
60
What is the main loop invariant for insertion sort
The sub-array safe area A[0,j-1] is sorted before itteration j
61
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)
62
What is the definition of a tree
63
What is the definition of a rooted tree
64
What is the definition of a leaf and an internal node?
65
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
66
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.
67
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)**.
68
What is the degree of a node? And what is the total degree of every node in the tree?
69
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.
70
Is it possible for a tree to have less than two leafs
No
71
What is a full, complete and perfect k-ary tree?
72
What is the number of nodes in a k-ary tree based on its height?
Height = # levels -1
73
What is the height of a **perfect** k-ary tree based its number of nodes
| Reminder: height = # levels -1.
## Footnote
In addition: A complete k-ary tree also has height of O(log_k(n))
74
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).
75
How can you sort a binary array in O(n)
76
What is the premise of comparison based sorting? And what are some example algorithms?
77
What is the lower bound for comparison based sorting
OMEGA(nlogn)
78
How many possible orderings are there for an array of size n
n!
79
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.
80
What is Stirling's approximation?
81
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)
82
What are the two functions of a priority queue structure?
83
How is an array interpreted as a tree (and what is the location of a parent, l-r child of any node)
84
What is the heap property
85
How is a heap constructed from an array (build(.))
86
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.
87
What are the steps of Heapify()
88
What is the runtime of Heapify() and why
89
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)**
90
What are the steps of heapsort
91
What is the runtime of heapsort
92
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)
93
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)
94
What are the divide, conquer and combine steps of QuickSort
95
nHow does the partition function of QuickSort work and what is its runtime
Runtime O(n)
96
How does quicksort work (visualised)
97
What is the main loop invariant for quicksort?
Assuming x is the pivot
98
What is the psuedocode for QuickSort?
99
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
100
What is the general runtime recurrence for QuickSort
101
What is the best and worst case splits for QuickSort
Worst case: Largest or Smallest
Best case: median
102
What does the worst case QuickSort recursion tree look like
103
What does the best-case QuickSort recursion tree look like
104
What does the best-case QuickSort recursion tree look like
105
What distinguishes a good and bad QuickSort split
106
What is the recursion tree for QuickSort with only good splits
Recurses until n = 1, so log(n)+1
107
What does the recursion tree for QuickSort look like with alternating good/bad splits
108
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)
109
What type of algorithms are recurrences especially useful for
Divide and conquer algorithms
110
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).
111
What 3 methods can be used for solving recurrences
112
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)
113
How do you solve the following problem
Add a minus one at the end
114
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**
115
How to deal with upper and lower bounds in recursion tree method
Discard them - only need a vague guess
116
Sum of infinite geometric series formula
117
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
118
Is it possible to sort integers faster than O(nlog(n))
Yes using **counting sort** or **radix-sort**
119
What is the psuedocode for counting sort
120
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
121
What is the runtime of counting sort
O(n+k) where k is the highest integer in the array
122
Is counting sort stable and in-place?
Yes **is stable** but not in-place since it uses aux arrays
123
What is the psuedo-code for Radixsort
## Footnote
Sort from lowest to highest usually
124
What is the runtime of radixsort
O(d(n+b)) -- b is base and d is number of digits
125
How do you compute the fibonacci series using a dynamic programming algorithm
Either store all values, or just last two
126
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`
127
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.
128
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**
129
What is bottom up psuedo-code for the dynamic programming approach to polecutting
130
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.**
