Tackling Hard Problems

Andy Novocin

Math Problem of day


Suppose you have a "pattern" matrix with each entry as either 0 or non-zero.


What can you say about the minimum rank of this matrix over all possible entry values?

Interview Question


Delayed until mid-lecture!

HW twiddling


Final Homework cancelled next one pushed back.


Only 5 now.

Six classes left


I want to cover:

Some classical hard problems

Satisfiability (SAT)


Given a set of boolean variables \(U = \{u_1, \ldots, u_n \}\)

Also a set of clauses \(C = \{c_1, \ldots, c_m \}\).


Is there an assignment of the \(u_i\) such that each \(c_j\) is True.


A clause \(c_j\) is a set of variables from \(U \cup \bar{U}\) joined by \( \lor \).


For instance \(c_j = \bar{u}_1 \lor u_2 \lor \bar{u}_4 \lor u_5 \).

ICUP SAT-style

Simple version of NP


P, NP, NP-Complete, NP-Hard are all sets of problems (not algorithms).


P is the set of all problems which, in the worst case, can be resolved in polynomial time.


NP is the set of all problems which, given a potential answer, can be verified in polynomial time.


NP-Hard is the set of all problems which can be used to solve any NP problem.


NP-Complete is the NP-hard problems that are also NP (can be quickly verified).

SAT is a big deal


In 1971 Cook showed that SAT can be used to solve any problem which can be verified in polynomial time.


It is the first NP-Complete problem, everyone else gets to do it the easy way.


http://www.satcompetition.org/


If you can solve SAT in polynomial time, you can solve a huge set of hard problems in polynomial time.

3-SAT


Just like SAT but each clause is limited to 3 variables.


(2-SAT is in P, 3-SAT is in NP-Complete).

ICUP 3-SAT

Note


If I give you a solution to that problem, you can check it quickly.

K-th Largest Subset


If I give you a set of integers, find the \(k\)-th largest subset of that set.


If I give you a possible answer, how quickly can you verify it?

Brute Force


Before we start getting too clever. We have to know how to just force our way through a problem.


If the problem involves finding the right subset then we can brute force up until about 20-40 items.


If the problem involves finding the right permutation then we can brute force up until about 10-15.


Recall the chart from earlier this semester.

Backtracking: a framework


We want to march our way through all possible answers of some problem.


We can see this (very abstractly) as finding all appropriate arrays \([a_1, \ldots, a_n]\) where I can map that array to an appropriate answer.


For instance a particular subset of an \(n\) element set can be seen as \([1,0,1,\ldots, 0,0,1]\) (in or out for each element).


Another example, every permutation of \(\{1, 2, \ldots, n \}\) is naturally an array (i.e. \([3,5,1,2,4]\)).

Backtracking Pseudo-Code 

def backtrack(ans_so_far, data):
  if is_valid(ans_so_far, data):
    process_solution(ans_so_far, data)
  else:
    next_options = create_options(ans_so_far, data)
    for option in next_options:
      add_option(ans_so_far, option, data)
      backtrack(ans_so_far, data)
      remove_option(ans_so_far, option, data)

How to use


This framework builds an answer array as we go and has some key components

For Subsets


ans_so_far at each stage is \(k\) boolean values.


create_options returns the array \([1,0]\) (True, False).


add/remove just append and remove current option.


is_valid checks if \(n == k\) (is the answer long enough)


process_solution Can print the subset or do whatever.

ICUP Warmup for interview


How do I set up backtracking for traversing permutations?

Interview Question


Write a function to find all permutations of the letters in a particular string.

If there is more time


Mention Hamiltonian Circuit, Vertex Cover, and Partition Problem