Shared Flashcard Set

Details

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

Additional Computer Science Flashcards

 


 

Cards

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), v+ 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

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 Pand 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!