Chapter 5:Algorithms and HeuristicsCS105: Great Insights in Computer ScienceHere’s Where We Stand• In the last chapter, we asked and answered some philosophical questions about computation.• Before that, 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 the lower levels for granted and build on them to create new capabilities.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 Sorter A• Strategy: Repeat until basket empty- Grab a sock.- Grab another.- If they don’t match, toss them back in the basket.• Will this procedure ever work?• Will it always work?Measuring Performance• Hillis asserts that the time-consuming part of this operation is reaching into the basket.• Let’s say we have 8 pairs of socks.• How many times does this strategy reach into the basket?• Min?• Max?• Average?• How do these values grow with increasing numbers of pairs of socks?Sock Sorter B• Strategy: Repeat until basket empty- Grab a sock.- Is its match already on the bed?- If not, put it on the bed.Measuring Performance• Once again, let’s imagine we have 8 pairs of socks.• How many times does this strategy reach into the basket?• Min?• Max?• Average?• How do these values grow with increasing numbers of pairs of socks?Repeat For Each Sock• Do you have a matching pair? Set it aside.• Do you have a non-matching pair? 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 sockBNotable 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• Strategy: Repeat until basket empty- Grab a sock.- Grab another.- Repeat until they match:- Toss one into the basket.- Grab a replacement.Measuring Performance• Once again, let’s imagine we have 8 pairs of socks.• How many times does this strategy reach into the basket?• Min?• Max?• Average?• How do these values grow with increasing numbers of pairs of socks?Round #2• Do you have a matching pair? Set it aside.• Do you have a non-matching pair? Put them both back in the basket.• Do you have a matching pair? Set it aside.• Do you have a non-matching pair? Put one back in the basket.sockA sockCAnalysis of sockC• Roughly the same number of matching operations, but since it always holds onto one sock, roughly half the number of socks taken out of the basket.• 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• Given a notion of “time” (# of socks removed or # of statements executed), 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.• Algorithms researchers pride themselves on finding simple-sounding problems for which the best algorithm is not obvious.• Ah, but what’s a problem? It should have a well-defined input and a well-defined output.Decision Problems on Lists• A natural class of problems is decision problems on lists of numbers. That is, the input is a list of numbers and the output is a decision, essentially a bit (True or False, yes or no).• We’ll try some examples and see if we can find efficient algorithms for solving different problems.Finding the Max• Problem: “Is the max x”? Given a list of numbers and a number x, is the largest number in the list equal to x?• Is the max 98?48, 40, 14, 46, 31, 0, 27, 12, 22, 71, 45, 63, 30, 64, 83, 28, 97, 90, 85, 52How Do You Do It?• Specifying an algorithm to the computer is like talking to a little kid. You need to spell out everything precisely.• Let’s try.def isMax(x):global listlargest = 0for i in range(len(list)):if list[i] > largest:largest = list[i]if x == largest: return Truereturn FalseFinding the Median• Problem: “Is the median x”? Given a list of numbers and a number x, is the median number in the list equal to x?• Is the median 45?48, 40, 14, 46, 31, 0, 27, 12, 22, 71, 45, 63, 30, 64, 83, 28, 90, 85, 52Sum Divisible By 5?• Problem: “Is the sum divisible by 5”? Given a list of numbers, is the sum of the numbers divisible by 5?• Is the sum divisible by 5?48, 40, 14, 46, 31, 0, 27, 12, 22, 71, 45, 63, 30, 64, 83, 28, 90, 85, 52Product Divisible By 5?• Problem: “Is the product divisible by 5”? Given a list of numbers, is the product of the numbers divisible by 5?• Is the product divisible by 5?48, 41, 14, 46, 31, 2, 27, 12, 22, 71, 44, 63, 33, 64, 83, 28, 96, 87, 52How Do It Fast? Median• If there are 19 numbers, median is the one in the 10th position when the list is sorted.• Straightforward algorithm is: (1) sort the list, (2) find the median in the sorted list, (3) check if it equals x.• That’s fine, but, there’s a shortcut: (1) count the number of numbers less than x (L) and the number equal to x (E), (2) check if L < 10 and L+E > 9.• Let’s try it! Is the median 47?9, 13, 2, 24, 13, 60, 31, 62, 59, 70, 47, 47, 77, 46, 46, 70, 39, 6, 63How Do It Fast? Sum• Straightforward algorithm is: (1) sum up the numbers in the list , (2) divide the grand total by 5, (3) check if there’s no remainder.• There are a few shortcuts we can use: (A) A number is divisible by 5 if and only if it ends in 5 or 0. (B) The sum of two numbers is divisible by 5 only if the sum of their last digits is divisible by 5.• Faster algorithm: (1) Keep a running total of the last digits, keeping only the last digit of the sum, (2) check if it’s 0 or 5. Let’s try: Is the sum divisible by 5?9, 13, 2, 24, 13, 60, 31, 62, 59, 70, 47, 47, 77, 46, 46, 70, 39, 6,