The CS 5 Times CS 5 and Physics Penguins Stranded in Spaceship Crash Wellington (AP): Two HMC penguins were missing after their spaceship lost power and crashed into the southern ocean. The CS penguin had kindly offered a ride to her friend, blubbered a distraught professor, and apparently he was fiddling with the flight computer just before takeoff. I dont know what Ill do for classroom examples now. With weather worsening, there is little hope for rescue. A memorial service will be held Sunday in the Hoch-Shanahan freezer. This Week

Homework 3: Reading Black lab (Problem 1) is same as Gold this week Youre ready for this today! Problem 2: Spel Chekking Problem 3: Word Break Youre ready for this today! Thursday! Beyond LCS: Edit Distance >>> ED("ATTATCG", "ACATTC") 4 ATTAT-CG A-CATTC-

The lower the edit distance the better! Beyond LCS: Edit Distance >>> ED("ATTATCG", "ACATTC") 4 ATTAT-CG A-CATTC>>> ED("spam", "scramble") 5 sp_am___ scramble spam -> scam -> scram -> scramb -> scrambl -> scramble Beyond LCS: Edit Distance

>>> ED("spam", "scramble") 5 spam -> scam -> scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return ??? elif S2 == '': return ??? elif S1[0] == S2[0]: return ??? else: # substitute, insert, or delete! Beyond LCS: Edit Distance >>> ED("spam", "scramble") 5

spam -> scam -> scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return len(S2) elif S2 == '': return len(S1) elif S1[0] == S2[0]: return ??? else: # substitute, insert, or delete! Beyond LCS: Edit Distance >>> ED("spam", "scramble") 5 spam -> scam ->

scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return len(S2) elif S2 == '': return len(S1) elif S1[0] == S2[0]: return ED(S1[1:], S2[1:]) else: # substitute, insert, or delete! substitute = insert = delete = return min(substitute, insert, delete) Beyond LCS: Edit Distance >>> ED("spam", "scramble") 5

spam -> scam -> scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return len(S2) elif S2 == '': return len(S1) elif S1[0] == S2[0]: return ED(S1[1:], S2[1:]) else: # substitute, insert, or delete! substitute = 1 + ED(S1[1:], S2[1:]) insert = delete = return min(substitute, insert, delete) Beyond LCS: Edit Distance

>>> ED("spam", "scramble") 5 spam -> scam -> scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return len(S2) elif S2 == '': return len(S1) elif S1[0] == S2[0]: return ED(S1[1:], S2[1:]) else: # substitute, insert, or delete! substitute = 1 + ED(S1[1:], S2[1:]) insert = 1 + ED(S1, S2[1:]) delete = return min(substitute, insert, delete)

Beyond LCS: Edit Distance >>> ED("spam", "scramble") 5 spam -> scam -> scram -> scramb -> scrambl -> scramble def ED(S1, S2): if S1 == '': return len(S2) elif S2 == '': return len(S1) elif S1[0] == S2[0]: return ED(S1[1:], S2[1:]) else: # substitute, insert, or delete! substitute = 1 + ED(S1[1:], S2[1:]) insert = 1 + ED(S1, S2[1:])

delete = 1 + ED(S1[1:], S2) return min(substitute, insert, delete) Problem 2 This Week New! Millisoft Office, featuring Millisoft Sentence (word processor) Energy Dot (presentation software) Succeed (spreadsheet software) Spelling A La Millisoft (SPAM) Gill Bates Aside: Another Way to map def doubleList1(L): return list(map(lambda x: 2*x, L)) def doubleList2(L): return [2*x for x in L] def doubleListFiltered1(L):

return list(map(lambda x: 2*x, filter(lambda x: x != 42, L))) def doubleListFiltered2(L): return [2*x for x in L if x != 42] These are called list comprehensions! Conditionalizing lambda >>> list(map(lambda x: "nice" if x == 42 else blech!, [42, 7, 6, 42, 3])) [nice, blech!, blech!, nice, blech!] >>> list(map(lambda x: "HM" if x == 42 else "PO" if x == 47 else x, [42, 7, 6, 47, 3])) ['HM', 7, 6, 'PO', 3] >>> ["HM" if x == 42 else "PO" if x == 47 else x for x in [42, 7, 6, 47, 3]]

['HM', 7, 6, 'PO', 3] The Aliens Life Advice Dont always win, even if you can. Nobody likes losing all the time. Easy Problems Sorting a list of n numbers: [42, 3, 17, 26, , 100] n log2 n Multiplying two n x n matrices: n (

3 1 2 9 5 6 4 3 2 7 8 9 6 10 2 12 n

)( 1 5 5 5 12 8 7 6 1 9 23 5 n 4 6 5 8 ) ( )

= n n Easy Problems The Shortest Path Problem (i.e. Google Maps Edsgar Dijkstra Easy Problems Polynomial Time = Efficient n, n2, n3, n4, n5, How about something like n log2 n ? sorting

matrix multiplication shortest paths The class P Hard Problems Snowplows of Northern Minnesota Burrsburg Frostbite City Tundratown Freezeapolis Shiversville Brute-force? Greed?

Hard Problems The Traveling Salesperson Problem New York 2566 4664 San Francisco Moscow 366 2417 5868 5563 3627

6060 Claremont 5625 Brute Force? Greed? 1545 Paris The Hamiltonian Path Problem Athens, GA William Rowan Hamilton Homer, GA Rome, GA Damascus, GA

Bethlehem, GA Those are some peachy names! n2 Versus 2n atic M O Geoff The Geoff-O-Matic performs 109 operations/sec n = 10 n 2

2n n = 50 n = 70 100 < 1 sec 900 < 1 sec 2500 < 1 sec 4900 < 1 sec

1024 < 1 sec 109 1 sec 1015 11.6 days 1021 31,688 years 1057 years 1093 years < 1 sec

n! n = 30 1016 years Heres an Idea! Lets just buy a computer thats twice as fast! Size of largest problem solvable with old computer in one hour = S n Size of largest problem solvable with new twice-as-fast

computer in one hour n2 n3 n5 2n 2S 1.41S 1.26S 1.15S S+1 n! S Snowplows and Traveling Salesperson Revisited!

So are there polynomial time algorithms for the Snowplow and Travelling Salesperson, and Hamiltonian Path Problems?! Tens of thousands of other known problems go in this cloud!! Snowplow Problem Hamiltonian Path Problem Travelling Salesperson Problem NP-complete problems

Snowplows and Traveling Salesperson Revisited! If a problem is NP-complete, it doesnt necessarily mean that it cant be solved in polynomial time. It does mean Tens of thousands of other known problems go in this cloud!! Snowplow Problem Hamiltonian Path Problem Travelling Salesperson Problem NP-complete

problems I cant find an efficient algorithm. I guess Im too dumb. Cartoon courtesy of Computers and Intractability: A Guide to the Theory of NP-Completeness by M. Garey and D. Johnson I cant find an efficient algorithm because no such algorithm is possible! Cartoon courtesy of Computers and Intractability: A Guide to the Theory of NP-Completeness by M. Garey and D. Johnson I cant find an efficient algorithm, but neither can all these famous people. Cartoon courtesy of Computers and Intractability: A Guide to the Theory of NP-Completeness by M. Garey and D. Johnson $1 million

Vinay Deolalikar Are There Problems That Are Even Harder Than NP-Complete? Kryptonite problems? Is LCS NP-Complete? def LCS(S1, S2): if S1 == "" or S2 == "": return 0 elif S1[0] == S2[0]: return 1 + LCS(S1[1:], S2[1:]) else: return max(LCS(S1, S2[1:]), LCS(S1[1:], S2)) Demo LCS Two strings of length 100 nucleotides each

>>> steps = 2**100 >>> speed = 3 * 10**9 >>> seconds = steps / speed >>> years = seconds / (60*60*24*365.25) >>> years 13 trillion years! 13389807845846.213 >>> 60 seconds per minute 60 minutes per hour 24 hours per day 365.25 days per year LCS(spam, pims) LCS(spam, ims)

LCS(pam, pims) 1+ LCS(spam, ms) LCS(pam, ims) LCS(pam, ms) LCS(am, ims) LCS(am, ims) I love am and ims! Dictionaries Revisited >>> D = {spam : yummy!, (42, 42): an important point}

>>> D = {} >>> D[spam] = yummy! >>> D[(42, 42)] = an important point >>> D[[1, 2]] = but this is bad BARF! >>> "spam" in D True >>> 42 in D False >>> (42, 42) in D True >>> D[(42, 42)] an important point How Dictionaries Work: Hashing >>> D {"Ran": "spam", }

>>> x = (1, 2) >>> D[x] = "my tuple" >>> D {"Ran": "spam", (1, 2): "my tuple"} Memory locations D["Ran"] 5999 D[x] = D[(1, 2)] 3 Imagine that we now changed x[0]=42 1

2 3 "my tuple" 5999 6000 "spam" def LCS(S1, S2): if S1 == "" or S2 == "": return 0 elif S1[0] == S2[0]: return 1 + LCS(S1[1:], S2[1:]) else: return max(LCS(S1, S2[1:]), LCS(S1[1:], S2)) Old slow version memo = {} # global empty dictionary

def fastLCS(S1, S2): if (S1, S2) in memo: return memo[(S1, S2)] elif S1 == "" or S2 == "": answer = 0 elif S1[0] == S2[0]: answer = 1 + LCS(S1[1:], S2[1:]) else: answer = max(LCS(S1, S2[1:]), LCS(S1[1:], S2)) memo[(S1, S2)] = answer return answer New fast memoized version Changing change def change(value, coins):

if value <= 0: return 0 elif coins == []: return float("inf") loseIt = change(value, coins[1:]) if value < coins[0]: return loseIt else: useIt = 1 + change(value - coins[0], coins) return min(useIt, loseIt) Changing change memo = {} # Empty dictionary coins must be a tuple rather than a list!

def fastChange(value, coins): if (value, coins) in memo: return memo[(value, coins)] elif value <= 0: return 0 elif coins == []: return float("inf") # Finish writing this! Geoffs solution coming up Worksheet! Changing change memo = {} # Empty dictionary

coins must be a tuple rather than a list! def fastChange(value, coins): if (value, coins) in memo: return memo[(value, coins)] elif value <= 0: return 0 elif coins == []: return float("inf") loseIt = fastChange(value, coins[1:]) if value < coins[0]: memo[(value, coins)] = loseIt return loseIt else: useIt = 1 + fastChange(value - coins[0], coins) best = min(useIt, loseIt)

memo[(value, coins)] = best return best