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.

True Story Joseph Weizenbaum 1923-2008 Eliza, the Rogerian therapist 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: RNA folding Youre ready for this today! Thursday! 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]

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] 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 Travelling 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 Travelling 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 Travelling 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 What Is This?! Are There Problems That Are Even Harder Than NP-Complete? Kryptonite problems? Is LCS NP-Complete? Demo LCS, fastLCS 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[spam] yummy! >>> D[(42, 42)] an important point >>> D[ [zaster!, putrid, smoke!] ] BARF! 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 The Aliens Life Advice

Dont always win, even if you can. Nobody likes losing all the time. 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 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 coins must be a tuple rather than a list! 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 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) Gill Bates Spelling A La Millisoft (SPAM) DEMO!