Final

Question 1

Packing Problems

Answer 1

Choose k objects among a set given certain constraints

Question 2

Independent Set Problem

Answer 2

Given G and k, does G contain an independent set of at least size K

Question 3

Independent Set

Answer 3

Set of vertices in a graph where no two nodes are adjacent

Question 4

Set Packing

Answer 4

Given a set U, a collection of S subsets, and k, is there a collection of at least k subsets where no two subsets intersect

Question 5

Covering Problems

Answer 5

Given a set, choose a subset of only k objects

Question 6

Vertex Cover Problem

Answer 6

Given G and k, does G contain a vertex cover of at most size k?

Question 7

Vertex Cover

Answer 7

Set of vertices that includes at least one endpoint of every edge of the graph

Question 8

Set Cover

Answer 8

Given a set U, a collection of S subsets, and k, is there a collection of at most k subsets whose union is equal to all of U?

Question 9

Partitioning Problems

Answer 9

Search over all ways to divide a collection of objects into subsets so that each object appears in exactly one of the subsets

Question 10

3-D Matching Problem

Answer 10

Given disjoint sets X, Y, and Z, each of size n, and given set T as a subset of X x Y x Z of ordered triples, does there exist a set of n triples in T so that each element of X union Y union Z is contained in exactly one of these triples?

Question 11

Graph Coloring

Answer 11

Given G and k, does G have a k-coloring?

Question 12

Sequencing Problems

Answer 12

Search over all permutations of a collection of objects

Question 13

Hamiltonian Cycle

Answer 13

Visits each vertex in G exactly once, starting and ending at the same node

Question 14

Hamiltonian Cycle Problem

Answer 14

Does a directed graph G contain a Hamiltonian Cycle?

Question 15

Hamiltonian Path Problem

Answer 15

Does directed graph G contain a Hamiltonian Path

Question 16

Hamiltonian Path

Answer 16

Visits each vertex in G exactly once

Question 17

Traveling Salesman

Answer 17

Given a set of distances on n cities, and a bound D, is there a tour length of at most D?

Question 18

TF: Numerical Problems are always NP-complete

Answer 18

False. For small instances, Dynamic Programming can solve in polynomial time

Question 19

Subset Sum Problem

Answer 19

Given a set of numbers and a target, is there a subset of numbers that add up to exactly the target?

Question 20

3-SAT Problem

Answer 20

Given a set of clauses each of length 3 over a set of variables from 1 to n, does there exist a satisfying truth assignment?

Question 21

NP

Answer 21

Nondeterministic Polynomial Time

Question 22

Min cut

Answer 22

Cut with minimum outward flow separating s and t

Question 23

s-t path

Answer 23

P goes from s to t without visiting any node more than once

Question 24

Ford-Fulkerson Runtime

Answer 24

O(mC) - at most C iterations of max flow on m edges

Question 25

Edges in residual graph

Answer 25

2m

Question 26

Bipartite Matching runtime

Answer 26

O(mn)