Chapter 5:Algorithms and HeuristicsCS105: Great Insights in Computer Science• problems on lists of numbers• algorithm vs. heuristic• heuristic search in subset sum?Here’s Where We Stand• Up until now, we discussed how a computer could be created starting from bits and wires and working up to a high-level language.• In classic CS style (reduction!), we now take all these lower levels for granted and build on them to create new capabilities.• The next block of lectures takes a high-level language as our starting point. So, it would help for you to hear a bit more details about it.Python Tutorial• Although you don’t need to learn to program in this class, I’d like you to be able to read a simple program to see what it does.Variables and Stringsprint “hello”helloit = “hello”print ithelloprint “it”itprint ‘it’ + “ “ + itit hellox = “tuna”y = “fish”print xtunaprint x + ytunafishprint x + “ “ + ytuna fishprint “x + y”x + ySubroutinesdef d(z): print z + “ are delicious”d(”salmon”)salmon are deliciousd(x)tuna are deliciousd(y)fish are deliciousd(x+y)tunafish are deliciousd(”x+y”)x+y are deliciousFunctionsdef s(w): return “fried ” + wprint s(”potatoes”)fried potatoesprint s(x)fried tunad(s(”eggs”))fried eggs are deliciousprint s(x) + s(y)fried tunafried fishConditional Branchnum = 17if num > 10: print “multidigit”multidigitif num % 2 == 0: print “even”else: print “odd”oddif num < 10: print “single digit”Listsz = [”Paul”, “George”, “Ringo”, John”]print z['Paul', 'George', 'Ringo', 'John']print z[0]Paulprint z[3]Johnprint z[1:][’George’, ‘Ringo’, ‘John’]print z + [”Stuart”, “Billy”]['Paul', 'George', 'Ringo', 'John', ‘Stuart’, ‘Billy’]print len(z)4print range(4)0, 1, 2, 3Strings as Listsprint xtunaprint x[0]tprint x[1:]unaprint (s(y))[1:8]ried fidef reverse(s): if s == “”: return “” return reverse(s[1:])+x[0]reverse(”swordfish”)hsifdrowsdel z[2]print z[’John’, ‘Paul’, ‘Ringo’]Numbersprint 1+1, 2-2, 3*3, 4/4, 10/32 0 9 1 3print 1 + x<error>print str(1) + x1tunadef frac(x,y): print x/y, x-y*(x/y), “/”, yfrac(1,3)0 1 / 3frac(14,3)4 2 / 3Loopsfor b in z: print b + “ was a Beatle.”Paul was a Beatle.George was a Beatle.x = 1000; y = 1Ringo was a Beatle.while x > 1:John was a Beatle. y = y + 1; x = x / 2print y10Next Goal• We looked at different ways of writing programs to produce the same output (Macdonald #1, #2, and #3, for example).• None was definitively better, except aesthetically.• We’ll look at another way of comparing programs...Sock Matching• Hillis begins Chapter 5 with an example.• We’ve got a basketful of mixed up pairs of socks.• We want to pair them up reaching into the basket as few times as we can.Sock ‘Ops• getSock(): pulls a sock out of the basket and provides its value.• match(sock1, sock2): takes two socks and returns True if they match (and pairs them) and False otherwise.• replaceSock(sock): puts the given sock back in the laundry basket.• emptyBasket(): returns True if the basket is empty and False if there are still more socks.Sock Sorter A• Grab two socks.• If they don’t match, toss them back in the basket.• Will this procedure ever work?• Will it always work?def sockA(): x = getSock() y = getSock() if not match(x,y): replaceSock(x) replaceSock(y)Measuring Performance• Hillis asserts that the time-consuming part of this operation is reaching into the basket: getSock().• Let’s say we have 8 pairs of socks.• How many getSock() operations are done by sockA() do?• Min?• Max?• Average?• How do these values grow with increasing numbers of pairs of socks?Sock Sorter B• Make a pile.• Grab a sock (as long as there is 1).• Look for its mate in the pile.• If found, shrink pile.• If not, add to the pile.• Min/Max/Mean?def sockB(): pile = [] while not emptyBasket(): x = getSock() matched = False for i in range(len(pile)): if not matched and match(x,pile[i]): matched = True del pile[i] if not matched: pile = pile + [ x ]Analysis• Gets every sock exactly once!• A bit of extra work keeping the pile in proper shape.• How might this approach be considered less good than the previous approach?Repeat For Each Sock• Do you have a matching pair? Set it aside.• Do you have a non-matching paper? Put them back in the basket.• Is there a match on the table? Pair them and set the pair aside.• Otherwise, find an empty place on the table and set the sock down.sockA() sockB()Notable if No Table• One disadvantage of sockB() is that you must have a big empty space available.• What if you can only hold two socks at a time?• Suggest for a competitor for sockA()?Sock Sorter C• Grab two socks.• If they don’t match, put one back and grab a replacement.• Repeat until a match is found.• Ever? Always? Min, max, average? Better/worse/same?def sockC(): x = getSock() y = getSock() while not match(x,y): replaceSock(y) y = getSock()Round #2• Do you have a matching pair? Set it aside.• Do you have a non-matching paper? Put them both back in the basket.• Do you have a matching pair? Set it aside.• Do you have a non-matching paper? Put one back in the basket.sockA() sockC()Analysis of sockC()• Roughly the same number of matching operations, but since it always holds onto one sock, roughly half the number of getSocks().• When might this approach fail in the real world?• Does sockA() suffer from this difficulty?Algorithms• sockA(), sockB(), and sockC() represent different approaches to solving the problem of sock sorting.• A concrete approach to solving a problem is called an algorithm.• Different algorithms can be better or worse in different ways.Lessons Learned• If we have a notion of “time” (getSock() or number of statements executed), we can compare different algorithms based on the time they take.• They really are different, so use good algorithms.• I once redesigned a colleague’s algorithm and it ran in seconds where it used to take an hour.• Hard to believe they solved the same problem.You Think You Have Problems• The sock matching problem is a little silly, because the right answer seems sort of obvious.•