Algorithm Design Techniques in CSCI 3160 Tutorial 4
Explore examples and strategies for solving 2-SAT problems efficiently through randomized algorithms. Learn how to verify matrix multiplication, test string equality, and identify design patterns using randomness.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
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
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 (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) Number of xis that agrees with the solution (i.e. number of i such that xi = T) 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 F x2 T x3 F x4 F x5 T current Find an unsatisfied clause: (x4 x3) flipone 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) clauses x1 F x2 T x3 T x4 F x5 T current Find an unsatisfied clause: (x1 x2) flipone 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
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 F x2 F x3 T x4 F x5 T current Find an unsatisfied clause: (x2 x3) flipone 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) clauses x1 F x2 T x3 T x4 F x5 T current Find an unsatisfied clause: (x1 x2) flipone 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
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 F x5 T current Find an unsatisfied clause: (x4 x5) flipone 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
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T current Find an unsatisfied clause: none We have a satisfying assignment! =)
Analysis To do the analysis, assume we have a satisfying assignment in mind, call it solution Of course, we do not know if a satisfying assignment exists when we run the algorithm we do this for the analysis only We compare the current assignment with the solution And record the number of variables that are assigned to the same T/F value in both (current and solution) assignments
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current F T F F T Find an unsatisfied clause: (x4 x3) flipone 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 Number of xis that agrees with the solution (i.e. xi = T) with prob. 1 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current F T T F T Find an unsatisfied clause: (x1 x2) flipone 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 Number of xis that agrees with the solution (i.e. xi = T) with prob. 1/2 with prob. 1/2 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current F F T F T Find an unsatisfied clause: (x2 x3) flipone 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 Number of xis that agrees with the solution (i.e. xi = T) with prob. 1/2 with prob. 1/2 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current F T T F T Find an unsatisfied clause: (x1 x2) flipone 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 Number of xis that agrees with the solution (i.e. xi = T) with prob. 1/2 with prob. 1/2 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current T T T F T Find an unsatisfied clause: (x4 x5) flipone 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 Number of xis that agrees with the solution (i.e. xi = T) with prob. 1/2 with prob. 1/2 0 1 2 3 4 5
2-SAT (x1 x2) (x2 x3) (x4 x3) (x5 x1) (x4 x5) clauses x1 T x2 T x3 T x4 T x5 T Solution current T T T T T Find an unsatisfied clause: none We have a satisfying assignment! =) Number of xis that agrees with the solution (i.e. xi = T) 0 1 2 3 4 5
2-SAT with prob. 1 0 1 2 3 4 5 with prob. 1/2 with prob. 1/2 0 1 2 3 4 5 with prob. 1/2 with prob. 1/2 0 1 2 3 4 5 with prob. 1/2 with prob. 1/2 0 1 2 3 4 5 with prob. 1/2 with prob. 1/2 0 1 2 3 4 5 0 1 2 3 4 5 We always move to the right with probability at least 1/2
2-SAT We always move forward with probably at least 1/2 a satisfying assignment must satisfy every clause x1 x2 e.g. (x1 x2) good T F good T T good F F bad F T When we find an unsatisfied clause, it must be bad The values of the literals in a satisfying assignment must be one of the good ones Hence, can always flip one to move to the right
2-SAT We always move forward with probably at least 1/2 When we reach n (i.e. 5 in the example), we have a satisfying assignment. Sufficient condition, not necessary. There may be other satisfying assignments But that will only improve the running time This is random walk on line and so we expect O(n2) jumps to hit n (refer to lecture notes)
2-SAT Randomized algorithm: Repeat O(n2) times, if we hit 5 in the middle of these O(n2) flips, return there is an assignment otherwise, return there is NO satisfying assignment
Verifying Matrix Multiplication Given 3 n x n integer matrices A, B and C, verify if AB = C Na ve algorithm Compute AB, check if it is equal to C Runs in time O(n3), dominated by computing AB How to do faster with high probability?
Verifying Matrix Multiplication Given 3 n x n integer matrices A, B and C, verify if AB = C Consider AB C Check if AB C is a zero matrix Lecture: how to check if two polynomials are identical? Evaluate the polynomials at different points
Verifying Matrix Multiplication Given 3 n x n integer matrices A, B and C, verify if AB = C Now, multiply AB C by different random vectors To avoid computing AB, we compute A(Bx) Cx We have Working over modulo 2, If AB C, then Pr[(AB - C)x 0] 1/2
String equality Alice has an n-bit string (a1, a2, , an) Bob has an n-bit string (b1, b2, , bn) Alice can communicate with Bob How to send as few bits as possible so that they know the two strings are equal?
String equality Alice has an n-bit string (a1, a2, , an) Bob has an n-bit string (b1, b2, , bn) Represent (a1, a2, , an) by a1 + a2x + + anxn-1 (b1, b2, , bn) by b1 + b2x + + bnxn-1 Polynomial Identity Testing! This idea can be extended to pattern matching
Design Patterns Las Vegas algorithm Always produces the correct answer Usually only expected running time is guaranteed Example: randomized quick sort
Design Patterns Monte Carlo algorithm Running time is deterministic Small probability of error Usually repeats a simple procedure to get a large success probability Example: min-cut
End Questions?
