CSCI 3160 Design and Analysis of Algorithms Tutorial 4 Chengyu Lin
CSCI 3160 Design and Analysis of Algorithms Tutorial 4 Chengyu Lin
Outline More examples about 2-SAT More randomized algorithms -Verifying Matrix Multiplication String Equality Test 。Design Patterns
Outline • More examples about 2-SAT • More randomized algorithms – Verifying Matrix Multiplication – String Equality Test • Design Patterns
2-SAT .Given (X1V-X2)A(X2V-X3)A(X4 VX3)A(X5 VX1)A(X4V-X5) .(X1,X2,X3,X4,Xs)=(T,T,T,T,T)is a satisfying assignment. Suppose you do not know about this solution You do not even know if there exists a solution for this formula How to decide if there is one using randomness?
2-SAT • Given (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • (x1 , x2 , x3 , x4 , x5 ) = (T, T, T, T, T) is a satisfying assignment. • Suppose you do not know about this solution • You do not even know if there exists a solution for this formula • How to decide if there is one using randomness?
2-SAT (X1V-X2)(X2V-X3)(X4VX3)(X5VX)(X4V-X5) 0 Start with a random assignment, -say (X1,X2,X3,Xa,Xs)=(F,T,F,F,T) Number of xis that agrees with the solution(i.e.number of i such thatx;=T) 0 2 3 5
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Start with a random assignment, – say (x1 , x2 , x3 , x4 , x5 ) = (F, T, F, F, T) 0 1 2 3 4 5 Number of xi s that agrees with the solution (i.e. number of i such that xi = T)
2-SAT (X1V-X2)^(X2V-X3)^(X4VX3)A(x5VX1)A(X4V-X5) clauses X1 X2 X3 Xa X5 current F T F F T Find an unsatisfied clause:(X4VX3) flip one of the value of x3 and x4 randomly If we flip x3,then we jump from 2 to 3 If we flip x4,then we jump from 2 to 3
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x4∨x3 ) • flip one of the value of x3 and x4 randomly – If we flip x3 , then we jump from 2 to 3 – If we flip x4 , then we jump from 2 to 3 x1 x2 x3 x4 x5 current F T F F T clauses
2-SAT (X1V-X2)A(X2V-x3)A(X4VX3)(x5VX1)(X4V-X5) clauses X1 X2 X3 Xa X5 current F T F T Find an unsatisfied clause:(XV-X2) flip one of the value of xi and x2 randomly -If we flip x1,then we jump from 3 to 4 If we flip x2,then we jump from 3 to 2
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x1∨¬x2 ) • flip one of the value of x1 and x2 randomly – If we flip x1 , then we jump from 3 to 4 – If we flip x2 , then we jump from 3 to 2 x1 x2 x3 x4 x5 current F T T F T clauses
2-SAT (X1V-X2)^(X2V-X3)^(X4VX3)A(x5VX1)A(X4V-X5) clauses X1 X2 X3 Xa X5 current F F T F T Find an unsatisfied clause:(X2 V-X3) flip one of the value of x2 and x3 randomly If we flip x2,then we jump from 2 to 3 If we flip x3,then we jump from 2 to 1
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x2∨¬x3 ) • flip one of the value of x2 and x3 randomly – If we flip x2 , then we jump from 2 to 3 – If we flip x3 , then we jump from 2 to 1 x1 x2 x3 x4 x5 current F F T F T clauses
2-SAT (X1V-X2)A(X2V-x3)A(X4VX3)(x5VX1)(X4V-X5) clauses X1 X2 X3 Xa X5 current F T T F T Find an unsatisfied clause:(XV-X2) flip one of the value of xi and x2 randomly -If we flip x1,then we jump from 3 to 4 If we flip x2,then we jump from 3 to 2
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x1∨¬x2 ) • flip one of the value of x1 and x2 randomly – If we flip x1 , then we jump from 3 to 4 – If we flip x2 , then we jump from 3 to 2 x1 x2 x3 x4 x5 current F T T F T clauses
2-SAT (X1V-X2)^(X2V-X3)^(X4Vx3)A(x5VX1)A(X4V-X5) clauses X1 X2 X3 Xa s current T T T F T Find an unsatisfied clause:(X4V-X5) flip one of the value of x4 and x5 randomly If we flip xa,then we jump from 4 to 5 If we flip xs,then we jump from 4 to 3
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x4∨¬x5 ) • flip one of the value of x4 and x5 randomly – If we flip x4 , then we jump from 4 to 5 – If we flip x5 , then we jump from 4 to 3 x1 x2 x3 x4 x5 current T T T F T clauses
2-SAT (X1V-X2)A(X2V-x3)(X4VX3)(x5VX1)(X4V-X5) clauses X1 X2 X3 Xa X5 current T T T T T Find an unsatisfied clause:none We have a satisfying assignment!=
2-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: none • We have a satisfying assignment! =) x1 x2 x3 x4 x5 current T T T T T clauses