Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

GA > exam 3 > Flashcards

exam 3 Flashcards

1
Q

what does NP stand for?

A

nondeterministic polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a search problem?

A

a problem where we can efficiently verify solutions (in polynomial time)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is NP?

A

class of all search problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is P?

A

class of all search problems that can be solved in polynomial time (subset of NP)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Knapsack search

A
  • Just like Knapsack, but you have a minimum (goal) as well as a max (B)
  • Solutions just needs to have weights <= B and values >= goal
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Examples of P problems

A

MST, LP

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

NP-Complete

A

NP problems that cannot be solved in polynomial time

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

IS Problem

A

NP-Complete. A set of vertices S of a graph is an independent set if there are no edges connecting any two vertices in the set. Have goal for minimum

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is NP-Hard

A

Problems at least as hard as NP-Complete, but not necessarily in the class NP. Must reduce NP-Complete to NP-Hard

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Clique

A

A set of vertices such that for any pair of vertices in the set, there is an edge between them. Have goal.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How to reduce IS->Clique

A

Reverse the graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Vertex Cover

A

A set of vertices is a vertex cover if for every edge at least one vertex is in the cover. Have budget b and want |S| <= b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Property of a vertex cover

A

S is a vertex cover if and only if !S (all vertices not in S) is an independent set

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What problems do we have for NP-Complete proof?

A

SAT, 3SAT, Clique, Vertex Cover, IS, Subset Sum, Knapsack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Is LP in P or NP?

A

It’s in P

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Is ILP in P or NP?

A

NP-Complete

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what is a Vertex Corner?

A

one of the vertices in the LP graph is an optimum solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

How do we know if we’ve found the optimal solution in an LP?

A

If a vertex is better than its neighbors, then it’s a global optimal point (assuming bounded and feasible)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How to check if there is a feasible area in an LP?

A

Start at x = 0 and check all remaining constraints, if none are satisfied, there is no solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Are strict inequalities (< or >) allowed in LP?

A

No

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Max-Flow as an LP

A 
f(e) for every edge
objective function: 
max(sum of all flows out of s)
subject to:
for every edge 0<= f <= c
for every vertex v except for s,t: incoming flow == outgoing flow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

LP Standard Form

A

Max C^T(x) such that Ax <= b and x >= 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How to convert a min LP to a max?

A

multiply by -1

24
Q

How many variables in an LP?

A

n for n-dimensional space

25
How many constraints in an LP?
m+n (m constraints + n non-negativity constraints)
26
What shape is an LP's feasible region?
convex polyhedron
27
what is the Upper bound on number of vertices in an LP?
N+m choose N vertices
28
what is the Upper bound on number of neighbors?
n*m
29
Simplex Algorithm
- Start at x=0 and check if there is a feasible area - Look for neighbor vertex with higher objective value and move to that vertex - Repeat
30
What makes a region infeasible?
the constriants
31
How to check if an LP is feasible?
Check at x = 0 and check all the constraints to see if a region is feasible or not
32
what is an Unbounded area?
The optimal values for the objective function are arbitrarily large
33
What is the dual LP?
Finding the smallest upper bound for the primal LP
34
Dual LP general form
Min b transpose y A transpose y >= c Y >= 0
35
Weak Duality
Any feasible y for dual LP is an upper bound for the objective function of the primal LP. AKA: ○ C transpose x <= b transpose y ○ If x and y are both feasible points in the primal and dual
36
Weak Duality Corollary
If we find a feasible x and feasible y where c^T x == b^T y, then x and y are both optimal - X is a max - Y is a min - c^T x == b^T y (this means objective function match)
37
rules on primal/dual feasibility and bounds
1. If primal LP is unbounded, then dual LP must be infeasible (Dual LP can't be bigger than infinity => must not be possible) 2. If dual is unbounded, then the primal is infeasible (Since dual is minimizing, b^Ty will be negative infinity)
38
If dual is infeasible, then...?
primal is either infeasible or unbounded
39
How to check if LP is unbounded (using dual)?
If dual is infeasible and primal is feasible => primal is unbounded
40
Strong duality
If primal LP is feasible and bounded, then the dual LP is both feasible and bounded (and vice verse)
41
Strong Duality Corollary:
Primal has optimal x* if and only if dual has optimal y*. c^T x* == b^T y*
42
What other theorem can be proved using strong duality?
Max-Flow Min-Cut
43
Max-SAT
Similar to SAT, except the output is the assignment that maximizes the number of satisfiable clauses
44
What class is Max-SAT?
NP-Hard
45
Max-SAT simple solution and expected value
Randomly assign variables to T/F | Expected number of satisfiable clauses (E[W]) >= 1/2
46
Probability that clause is satisfied in Max-SAT simple solution
1-2^k
47
what class is ILP?
NP-Complete
48
In ILP, where is the optimal point?
Not guaranteed to be on a vertex
49
How to do LP Relaxation
remove requirement that variables are ints
50
How to convert an LP solution back to an ILP and what is the expected value?
Round each value of y using randomized rounding If y=0.75, then round y to 1 with probability 0.75, and to 0 with probability 0.25 Expected value >= (1-1/e) m* where m* is the optimal value for the ILP
51
How can we use ILP/LP to get heuristics for NP-Hard problems?
Reduce NP-Hard to ILP Relax to LP and solve Do Randomized Rounding => Results in a feasible point and reasonable heuristic
52
How can we use ILP/LP to get heuristics for NP-Hard problems?
Reduce NP-Hard to ILP Relax to LP and solve Do Randomized Rounding => Results in a feasible point and reasonable heuristic
53
3/4 approximation
Can use a combo of LP-Relaxation and Simplex method. Just perform both and pick the best value. Expected performance >= 3/4 m* where m* is the optimal solution
54
LP-Relaxation probability of Max-SAT clause evaluating to true
1-(1-1/k)^k
55
Subset sum
- Input = set of integers and t - Output = subset of integers that add up to exactly t NP-Complete
56
What is Undecidability
Computationally impossible: there is no algorithm that can solve the problem on every input, even with unlimited time and space
57
Example of undecidable problem
halting problem

GA (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions