Term
01 Knapsack recurrence. Does ordering determine which object the thief may take? 

Definition
i < items. j < capacity.
F(i,j)= max{F (i1,j), v_{i }+ F(i1, jw_{i})} if jw_{i} ≥ 0
F(i1, j) if jw_{i} < 0
Yes, ordering matters. 


Term
Initial conditions of Knapsack 10 for making the table 

Definition
F(0,j)=0 for all j
F(i,0) = 0 for all i



Term
What is the bigOh of building the KnapSack 01? 

Definition


Term
What is the bigoh for tracing back 01 knapsack? 

Definition


Term

Definition
//Input: A nonnegative integer i indicating the number of the first
// items being considered and a nonnegative integer j indicating
// the knapsack capacity
//Output: The value of an optimal feasible subset of the first i items
//Note: Uses as global variables input arrays Weights[1..n], Values[1..n],
//and table F [0..n, 0..W ] whose entries are initialized with −1’s except for
//row 0 and column 0 initialized with 0’s
if F(i,j) < 0
if j < weights[i]
value < MFKnapsack(i1, j)
else
value < max(MFKnapsack(i1, j),
values[i] + MFKnapsack(i1, jweights[i]))
F(i,j) < value
return F[i,j]



Term
Number of subsets of a sequence 

Definition
2^{L} Where L = sequence length 


Term
Order of growth to construct a table for Longest Common Substring 

Definition
O(mn)
Where m=length of first, n=length of second 


Term
Bottom up traversal explanation for LCS 

Definition
If upper or left is equal, move there, otherwise mark character and move upleft. Character is marked by both row and column since they are the same. 


Term
How to trace back in a table of knapsack and bigOh 

Definition
Bigoh of n, number of items. 


Term
Robot coin collecting psuedocode 

Definition
//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and
//for cells with and without a coin, respectively
//Output: Largest number of coins the robot can bring to cell (n, m)
F[1,1]←C[1,1];
for j←2 to m do
F[1,j]←F[1,j−1]+C[1,j]
for i ← 2 to n do
F [i, 1] ← F [i − 1, 1] + C[i, 1]
for j ← 2 to m do
F[i,j]←max(F[i−1,j],F[i,j −1])+C[i,j]
return F [n, m]



Term
Time and space efficiency of tracing back robot coin collection? 

Definition


Term
Recurrence relation for 01 knapsack with repeats 

Definition
max{v_{i} + F(jw_{i})}
all items wi ≤ j 


Term
Difference between divide and conquer and dynamic programming 

Definition
Smaller subproblems in dynamic programming overlap 


Term
What is characterizing a problem into subsets of smaller problems? 

Definition


Term
M(n, k) represents what in the dynamic partition problem. n is size of problem, k is number of partitions. 

Definition
The minimum (for all possible kpartitions) of the max sum of numbers in one of the subsets determined by the partition. 


Term
Recurrence relation for dynamic programming partition 

Definition
M(n, k) = Min {max (M(i, k1)), ∑ S_{j}}
^{i=1, 2...n1}
Look at the minimum of the smaller partitions (k1) and the remaining numbers. The remaining numbers will count as a partition as well, since we want the smallest of the max partitions. 


Term
What is the "choice" of 01 knapsack with repeats? 

Definition
Which item to choose, if any 


Term
Worst case order of growth for filling 01 knapsack with repeats table? 

Definition
θ(n*w)
n  different items
w  capacity 


Term
Array entries for dynammic programming solution to partition problem. 

Definition
The entries represent largest sum determined by the best partition for a prefix sequence of the numbers and a number of partitions 


Term
Recurrence relation for Minimum Sum Desent 

Definition
M[ i , j ] = min { M[ i+1 , j], M[ i+1 , j+1 ]} + A[ i , j ] 


Term

Definition


Term

Definition


Term
Spanning Tree of a connected graph is a 

Definition
Connected, acyclic subgraph of G that includes all of G's vertices 


Term

Definition
Spanning tree of G (weighted, connected) of minimum total weight 


Term
Analysis of Prim's algorithm (2 steps) 

Definition
 Make V  1 extractMin (getting smallest element from queue)
 E * changePriority (worst case V) operations of a priority queue. But since we use a heap it is Elog(v)



Term

Definition
If an edge is the minimum cost edge between S and VS then E is in the MST. S is a set of vertices within the total set of vertices. 


Term
Greedy algorithm for interval scheduling 

Definition


Term
Time Efficiency of Dijkstra's Algorithm for graphs represented by weight matrix using an array for PQ 

Definition


Term
Prim's Algorithm proof. Prove that there is a path in T that goes from S to VS 

Definition
T: MST for G but e' (min cost edge between S and VS) is not in T.
Since T is a min spanning tree, there must be a unique path between two vertices.
Take T U {e}
There is a cycle, so there's an edge e that goes from S to VS 


Term

Definition
No cycles.
Minimal set of edges containing all vertices V = E + 1



Term
Prove T' is better for Prim's algorithm proof 

Definition
T' = (T  {e}) U {e'}
T' is a spanning tree because V = E + 1
Weight(e') < weight(e)
Total weight(T') < total weight (T)
So T is not the minimal spanning tree
e' must be in MST 


Term
Dijkstra's Algorithm works on shortest path between... 

Definition


Term
How does Prim's algorithm relate to cut property 

Definition
1)Prim builds a tree by adding min cost edge to existing tree.
2) Vertices of existing tree = S. Vertices not in existing tree = VS.
Adding min cost edge at each step 


Term

Definition
Any linear programming problem with a nonempty, bounded, feasible region has an optimal solution. Also, optimal solution is always at the extreme point of the region. 


Term
Worst Case Efficiency of Simplex Method 

Definition


Term
Asymptotic notations and properties 

Definition
O(g(n)): functions f(n) that grow no faster than g(n)
Θ(g(n)): functions f(n) that grow at same rate as g(n)
Ω(g(n)): functions f(n) that grow at least as fast as g(n) 


Term
When updating vertices, update them according to point A or current left hand side for prim's 

Definition


Term

Definition
Value of a max flow is equal to it's min cut capacity 


Term
Proof 1 of Max Flow Min Cut 

Definition
For any flow network, any feasible flow with the value v, and any cut C(X, VX) with capacity c, then v ≤ c 


Term
Proof 2 of maxflow mincut theorem 

Definition
The shortest augmenting path algorithm determines a cut with capacity c such that v=c 


Term
Prove Step 1 of Max Flow Min Cut 

Definition
Net flow across cut = v. v = Σ flows on edges from X to VX  Σ flows on edges from VX to X.
Second term is not negative, there are no negative flows
Since v = Σ X → VX  Σ VX →X
and c = Σ X → VX
Thus v ≤ c 


Term
Prove Step 2 of max flow min cut 

Definition
Form a cut with X being set of vertices reachable from the source in the final iteration of shortest augmenting path. X contains source, not sink. Therefore, X and the complement form a cut.
Each edge (i,j) from X to VX has unused capacity of 0, otherwise the end vertex j would have ended up in VX. Each edge (j,i) has flow 0, there are no back edges.
v = Σ flows on edges from X to VX  Σ flows on edges from VX to X.
Bold = 0.
= capacity of the cut.



Term
Accuracy ratio of an approximate solution s for minimization / maximization 

Definition
r(s_{a}) = f(s_{a}) / f(s*) > minimization
max is flip 


Term
What is a prefix code, and what types of codes take this form? 

Definition
A prefix code is such that there is no valid code word in the system that is a prefix of any other valid code word in the set. Huffman codes are prefix codes. 


Term
What is a hamiltonian circuit? 

Definition
A circuit where every edge is visited exactly once 


Term

Definition


Term
Recurrence relation of MergeSort 

Definition
M(n) = M(n/2) + C_{merge} 


Term
What is topological sorting? 

Definition
A list of vertices in such an order that for every edge in the graph, the vertex where the edge starts is listed before the vertex where the edge ends. (Course Prerequisites Example) 


Term

Definition


Term

Definition


Term
Is the left branch 0 or 1 for huffman tree 

Definition


Term
Nondeterministic polynomial algorithm is twostage procedure that... 

Definition
Guesses the random string to solve problem
Checks string correctness in polynomial time 


Term
Worst and average case complexity of convex hull 

Definition
Worst case  Θ(n^{2})
Average case  Θ(n)
Sorting points by xcoordinate can be done in O(nlogn)



Term
Euclid's Algorithm to greatest common divisor 

Definition
gcd(m,n) = gcd(n,m mod n) until second number = 0 


Term

Definition
Big O the algorithm will not grow faster, Θ it will grow as fast, Ω it will grow at least as fast 


Term
If f(x) and g(x) are functions from Z+ > Z+. Then f(x) is O(g(x) if there exists _________________________ such that______________________________
FOR ALL_____________________________. 

Definition
A positive constant c and nonnegative integer k
such that
f(n) ≤ c g(n)
for every
n ≥ k 


Term
If f(x) and g(x) are functions from Z+ > Z+. Then f(x) is θ(g(x) if there exists _________________________ such that______________________________
FOR ALL_____________________________. 

Definition
two integers C_{1} and C_{2} and a k, all greater than 0
such that
C_{1}g(x) ≤ f(x) ≤ C_{2}g(x)
for all
n > k 


Term
1 ↔
2 [image]
3 [image]
4 Z
5 C
6 [image]
7 →
8 [image]
9 [image]


Definition
1 Implies and implied by
2 Is an element of
3 Is a subset of
4 The set of integers
5 The set of complex numbers
6 The set of real numbers
7 Implies
8 For all
9 There exists 


Term
Time Efficiency For NonRecursive Functions 

Definition
1) Decide Input Size n
2) Identify Basic Operation
3) Worst/Avg/Best Case of Input size n
4) Sum number of times basic op executed
5) Simplify using standard formulas 


Term

Definition
Take the leftmost xpoint and rightmost xpoint, divide plane with this.
Divide points on each side of line segment according to the line determined by the point in that subset that is farthest from the existing line. 


Term
Left child/ right child/ parent array location. Where are all parrents? 

Definition
2j, 2j + 1, floor of j./2.
Parents are in first floor of n/2 


Term

Definition


Term
Bottom Up Heap Construction Algorithm 

Definition
Loop until done with root
Observe right to left parents
If it doesn't satisfy heap condition  exchange with largest child until heap condition holds (Drift Down)
(Until heap condition holds means if you exchange, the loop hits the child that resulted)



Term
Closest pair(P, Q) steps. P is sorted xcoordinates. Q is sorted ycoordinates. 

Definition
1) Divide points given into two subsets P_{1 }and P_{2} by a vertical line x=m where m is a number so that the points are equally split
2) Compute d_{1}_{ }recursively doing closest pair to left side
3) Comput d_{2} recursively doing closest pair to right side
4) let d= min(d_{1}, d_{2})
5) S = set of points such that their xcoordinates are within d distance of m
6) Loop over points in S using Q
7) for each point Γ in S we compute its distance if Γ_{y} < P_{y}  d
8) if its distance to P is less than d, d= that distance
return 


Term
What does it mean for a sorting algorithm to be stable 

Definition
The algorithm does not make unnecessary switches (5 of hearts switching with 5 of clubs) 


Term

Definition
Directed graph
Acyclic  No cycles 


Term
If there is a back edge in DFS, what does this mean? 

Definition


Term
How to get topological order from DFS 

Definition
Reverse order from which it is popped off 


Term
What is first in topological order, if we are using CPE course example? 

Definition


Term
Number of permutations needed for TSP 

Definition


Term
Definition of NPcomplete 

Definition
Any problem in NP can be polynomially reduced to it. It is as hard as any NP problem 

