Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

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
Q

How many constraints in an LP?

A

m+n (m constraints + n non-negativity constraints)

26
Q

What shape is an LP’s feasible region?

A

convex polyhedron

27
Q

what is the Upper bound on number of vertices in an LP?

A

N+m choose N vertices

28
Q

what is the Upper bound on number of neighbors?

A

n*m

29
Q

Simplex Algorithm

A
  • 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
Q

What makes a region infeasible?

A

the constriants

31
Q

How to check if an LP is feasible?

A

Check at x = 0 and check all the constraints to see if a region is feasible or not

32
Q

what is an Unbounded area?

A

The optimal values for the objective function are arbitrarily large

33
Q

What is the dual LP?

A

Finding the smallest upper bound for the primal LP

34
Q

Dual LP general form

A

Min b transpose y
A transpose y >= c
Y >= 0

35
Q

Weak Duality

A

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
Q

Weak Duality Corollary

A

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
Q

rules on primal/dual feasibility and bounds

A
  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
Q

If dual is infeasible, then…?

A

primal is either infeasible or unbounded

39
Q

How to check if LP is unbounded (using dual)?

A

If dual is infeasible and primal is feasible => primal is unbounded

40
Q

Strong duality

A

If primal LP is feasible and bounded, then the dual LP is both feasible and bounded (and vice verse)

41
Q

Strong Duality Corollary:

A

Primal has optimal x* if and only if dual has optimal y. c^T x == b^T y*

42
Q

What other theorem can be proved using strong duality?

A

Max-Flow Min-Cut

43
Q

Max-SAT

A

Similar to SAT, except the output is the assignment that maximizes the number of satisfiable clauses

44
Q

What class is Max-SAT?

A

NP-Hard

45
Q

Max-SAT simple solution and expected value

A

Randomly assign variables to T/F

Expected number of satisfiable clauses (E[W]) >= 1/2

46
Q

Probability that clause is satisfied in Max-SAT simple solution

A

1-2^k

47
Q

what class is ILP?

A

NP-Complete

48
Q

In ILP, where is the optimal point?

A

Not guaranteed to be on a vertex

49
Q

How to do LP Relaxation

A

remove requirement that variables are ints

50
Q

How to convert an LP solution back to an ILP and what is the expected value?

A

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
Q

How can we use ILP/LP to get heuristics for NP-Hard problems?

A

Reduce NP-Hard to ILP
Relax to LP and solve
Do Randomized Rounding
=> Results in a feasible point and reasonable heuristic

52
Q

How can we use ILP/LP to get heuristics for NP-Hard problems?

A

Reduce NP-Hard to ILP
Relax to LP and solve
Do Randomized Rounding
=> Results in a feasible point and reasonable heuristic

53
Q

3/4 approximation

A

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
Q

LP-Relaxation probability of Max-SAT clause evaluating to true

A

1-(1-1/k)^k

55
Q

Subset sum

A
  • Input = set of integers and t
    • Output = subset of integers that add up to exactly t
      NP-Complete
56
Q

What is Undecidability

A

Computationally impossible: there is no algorithm that can solve the problem on every input, even with unlimited time and space

57
Q

Example of undecidable problem

A

halting problem

GA (3 decks)

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