Greedy Algorithms: Horn-SAT, Encoding Problem & Proof Sketch
Explore the concepts of Greedy Algorithms through examples like Horn-SAT logical formulas and the Hoffman tree Encoding Problem. Understand how to determine satisfying assignments and optimize binary code lengths. Dive into proof sketches to validate algorithmic approaches.
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
Example 3: Horn-SAT Logical formulas Variable ? true or false Negation ? Horn Clauses ? ? ? ? ? ? ? Problem: Given a set of Horn clauses, determine whether there exists an assignment to variables such that all clauses are satisfied.
Different Clauses ?1 ?4 ?2 ?1 ?2 ?3 ?1 ?2 ?1 ?3 ?1 ?2 ?4 Type 1: If some variables are true, x is true Type 2: Variable x is true Type 3: At least one of these variables is false. Algorithm: First set everything to false x1 = true (clause 3); x2 = true (clause 4) x3 = true (clause 2); check clauses 5 and 6, clause 5 is violated, output No
Proof Idea If the algorithm succeeds, then there is clearly an assignment Need to show: if the algorithm fails, then no assignment can satisfy the clauses Assume there is actually an assignment, how to find a contradiction?
Proof Sketch Algorithm: x1=x2=x3 = true x4=false Case 1: If the satisfying assignment also has x1=x2=x3 = true Then clause 5 is violated So one of x1,x2,x3 must be false, look for the first variable that is false. ?1 ?4 ?2 ?1 ?2 ?3 ?1 ?2 ?1 ?3 ?1 ?2 ?4
Proof Sketch Algorithm: x1=x2=x3 = true x4=false Case 2: If x1 or x2 if false Then clause 3 or 4 is violated ?1 ?4 ?2 ?1 ?2 ?3 ?1 ?2 ?1 ?3 ?1 ?2 ?4
Proof Sketch Algorithm: x1=x2=x3 = true x4=false Case 3: If x3 is the first variable that is false Both x1 and x2 are true. Clause 2 is violated. ?1 ?4 ?2 ?1 ?2 ?3 ?1 ?2 ?1 ?3 ?1 ?2 ?4
Example 4: The Encoding Problem (Hoffman Tree) Problem: Given a long string with n different characters in alphabet, find a way to encode these characters into binary codes that minimizes the length. Example: aababc , n = 3, alphabet = {a,b,c} If a = 0 , b = 11 , c = 10 , then the string can be encoded as 001101110 .
Why dont just use ASCII? Different letters appear with very different frequency. Using an encoding of varying length can save space. Now of course memory/disk are cheap, but some communications can be expensive.
What kind of encodings are allowed? Bad example: If a = 0 , b = 01 , c = 1 Given encoding 00010011, it can be aababc , but can also be aaacabc (and others) Want an encoding that allow unique decoding. Sufficient condition: Prefix free encoding Definition: No code should be a prefix of another code. (In previous example, encoding of a is a prefix for encoding of b.)
Prefix-free encoding vs. Trees 0 1 a = 00 b = 01 c = 110 d = 111 1 0 1 a b 0 1 c d Character = Leaves of the Tree Encoding = Path from root to the character Prefix free = no characters for intermediate nodes
Cost of the Tree 0 1 Cost = sum of Frequency * Depth = 5*2 + 10*2 + 3*3 + 6*3 = 57 1 0 1 a b 0 1 5 10 c d 3 6
Hoffman Tree problem Given a long string with n different characters in alphabet, find a way to encode these characters into binary codes that minimizes the length. Given an alphabet of n characters, character i appears wi times, find an encoding tree with minimum cost.
Cost of the Tree - Revisited Cost = 24 = 15 + 9 Cost = 15 = 5 + 10 0 1 Cost = 9 = 3 + 6 1 0 0 1 a b c d 3 6 5 10 Claim: Cost of the tree = sum of cost for each node.
Algorithm Hoffman Tree 1. REPEAT 2. Select two characters with smallest frequencies 3. Merge them into a new character, whose frequency is the sum 4. UNTIL there is only one character abcd 24 acd 14 ac 8 a b c d 6 3 5 10
Proof Sketch Use induction: Assume algorithm finds the optimal solution for alphabet of size n, we want to prove that it works for alphabet of size n+1. Base Case: n = 1 is trivial. (cost = 0 in this case)
Induction Step i j i j First merged i, j i, j may be in different branches (characters with lowest frequency) Goal: Convince OPT that it is OK to merge i, j first.
Induction Step j i j i After ALG and OPT both merged i, j, it reduces to a problem of size n! Induction hypothesis ALG is optimal, OPT cannot be better.
