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.


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


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

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



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)
    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