# Shared Flashcard Set

## Details

CPE 349
This Class Is Awesome
72
Computer Science
05/08/2013

Term
 0-1 Knapsack recurrence. Does ordering determine which object the thief may take?
Definition
 i <-- items. j <-- capacity. F(i,j)= max{F (i-1,j), vi + F(i-1, j-wi)} if j-wi ≥ 0                  F(i-1, j)                                if j-wi < 0   Yes, ordering matters.
Term
 Initial conditions of Knapsack 1-0 for making the table
Definition
 F(0,j)=0 for all j F(i,0) = 0 for all i
Term
 What is the big-Oh of building the KnapSack 0-1?
Definition
 O(nW)
Term
 What is the big-oh for tracing back 0-1 knapsack?
Definition
 O(n)
Term
 MF Knapsack Pseudocode
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(i-1, j)    else       value <-- max(MFKnapsack(i-1, j),                               values[i] + MFKnapsack(i-1, j-weights[i]))    F(i,j) <-- value return F[i,j]
Term
 Number of subsets of a sequence
Definition
 2L 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 up-left. Character is marked by both row and column since they are the same.
Term
 How to trace back in a table of knapsack and big-Oh
Definition
 Big-oh of n, number of items.
Term
 Robot coin collecting psuedo-code
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
 Θ(nm)
Term
 Recurrence relation for 0-1 knapsack with repeats
Definition
 max{vi + F(j-wi)} 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
 Top-down. Merge Sort
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 k-partitions) 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, k-1)), ∑ Sj}            i=1, 2...n-1   Look at the minimum of the smaller partitions (k-1) 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 0-1 knapsack with repeats?
Definition
 Which item to choose, if any
Term
 Worst case order of growth for filling 0-1 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
 logb(xn)
Definition
 n * logb(x)
Term
 eln(3)
Definition
 3
Term
 Spanning Tree of a connected graph is a
Definition
 Connected, acyclic subgraph of G that includes all of G's vertices
Term
 Minimum spanning tree
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 |E|log(|v|)
Term
 Cut property
Definition
 If an edge is the minimum cost edge between S and V-S 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
 Earliest finish time
Term
 Time Efficiency of Dijkstra's Algorithm for graphs represented by weight matrix using an array for PQ
Definition
 O(|V|2)
Term
 Prim's Algorithm proof. Prove that there is a path in T that goes from S to V-S
Definition
 T: MST for G but e' (min cost edge between S and V-S) 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 V-S
Term
 Spanning tree properties
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
 Point A and all others
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 = V-S. -Adding min cost edge at each step
Term
 Extreme Point Theorem
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
 Exponential
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
 Current Left Hand Side
Term
 Max-Flow Min-Cut Theorem
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, V-X) with capacity c, then v ≤ c
Term
 Proof 2 of max-flow min-cut 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 V-X - Σ flows on edges from V-X to X. Second term is not negative, there are no negative flows Since v =  Σ X → V-X - Σ V-X →X and c =  Σ X → V-X 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 V-X has unused capacity of 0, otherwise the end vertex j would have ended up in V-X. Each edge (j,i) has flow 0, there are no back edges. v =  Σ flows on edges from X to V-X - Σ flows on edges from V-X to X. Bold = 0. = capacity of the cut.
Term
 Accuracy ratio of an approximate solution s for minimization / maximization
Definition
 r(sa) = f(sa) / 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
 Big-Theta of MergeSort
Definition
 O(nlogn)
Term
 Recurrence relation of MergeSort
Definition
 M(n) = M(n/2) + Cmerge
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
 Worst Case of quicksort
Definition
 O(N2)
Term
 Worst Case of Heap Sort
Definition
 O(nlogn)
Term
 Is the left branch 0 or 1 for huffman tree
Definition
 0
Term
 Nondeterministic polynomial algorithm is two-stage 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 - Θ(n2) Average case - Θ(n) Sorting points by x-coordinate 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
 Big O, Θ, Ω
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 non-negative 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 C1 and C2 and a k, all greater than 0 such that C1g(x) ≤ f(x) ≤ C2g(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 Non-Recursive 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
 Quick Hull Algorithm
Definition
 Take the left-most x-point and right-most x-point, 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
 Height of a heap is
Definition
 Floor of log2 n
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 x-coordinates. Q is sorted y-coordinates.
Definition
 1) Divide points given into two subsets P1 and P2 by a vertical line x=m where m is a number so that the points are equally split 2) Compute d1 recursively doing closest pair to left side 3) Comput d2 recursively doing closest pair to right side 4) let d= min(d1, d2) 5) S = set of points such that their x-coordinates 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 < Py - 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
 What is a DAG
Definition
 Directed graph Acyclic - No cycles
Term
 If there is a back edge in DFS, what does this mean?
Definition
 There is a cycle
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
 CPE 123
Term
 Number of permutations needed for TSP
Definition
 1/2(n-1)!
Term
 Definition of NP-complete
Definition
 Any problem in NP can be polynomially reduced to it. It is as hard as any NP problem
Supporting users have an ad free experience!