15-451 Algorithms 12/04/13 recitation notes * String Matching - DFAs to find substrings - Suffix trees to find substrings * Auctions and VCG ================================================================= 1. Build a DFA that accepts string over the alphabet {a,b} exactly when the string contains abba as a substring. [Do example on the board] Observe that once we build this DFA, we can answer the question - does a given text T contain the string abba - output the location of the first occureence of the string abba in the text T. Both can be done in O(T) time given the DFA and the text. Alter the DFA above so that that reaches the accept state every time the previous 4 characters seen are abba. [Do this example on the board] This DFA can be used to output all locations of the string abba in the text T. ---------------------------------------- 2. Quick review of Suffix trees. [Lecture 26] Build the suffix tree for tartans\$. [Do this example on the board] To find the longest common substring between tartan and party, build the suffix tree for tartan%party\$ (which can be done in linear time), then delete parts of the tree that lie below some % symbol. Next, mark any node that can reach both % and \$ below itThen look for the deepest marked node. [Do this example on the board] Good. We can do fancier string searching. E.g., given S and T (and also A and B), output the longest common substring of S and T that does not occur in either A or B? Answer: build a suffix tree for A%B\$S#T&, where as usual we assume that the characters #&%\$ do not occur in S,T,A,B. Now traverse this suffix tree and delete any parts of the tree that lie below the delimiters %&\$#. Another traversal to mark any node that contains # and & below it (which means it corresponds to some substring of both S and T) but do not contain % or \$ below it (so it is not a substring of either A or B). Output the string corresponding to the deepest marked node. ---------------------------------------- We saw the VCG mechanism for incentive-compatible auctions in Lecture #27. There are 2 ad slots that LeGoog wants to sell on a page, the first slot has a clickthru rate of 0.5, the second has a clickthru rate of 0.3. There are 4 bidders, with the following valuations A: \$10 per click (so, e.g., this bidder values the first slot at 10*0.5 = 5, and the second slot at 10*0.3 = 3.) B: \$8 per click C: \$7 per click D: \$2 per click Each bidder can get at most one slot. What is the social-welfare maximizing allocation? [A gets the first slot, B gets the second. The total value to A is 5 and the value to B is 8*0.3 = 2.4. Total social welfare = 7.4 ] What are the VCG payments? [if A did not bid, B and C would get the first and second slots respectively. The social welfare would be 8*0.5 + 7*0.3 = 6.1. So A's payment is how much his presence caused B,C,D's welfare to fall, = (optimal welfare without A) - (optimal welfare of everyone else with A) = 6.1 - (2.4 + 0 + 0) = 3.7. if B did not bid, A and C would get the first and second slots respectively. The social welfare would be 10*0.5 + 7*0.3 = 7.1. So B's payment is how much his presence caused the others' welfare to decrease = (optimal welfare without B) - (optimal welfare of everyone else with B) = 7.1 - (5 + 0 + 0) = 2.1. ----------------------------------------