Algorithmic DesignAlgorithmsProblem SolvingLoop InvariantsBean Can gameBean Can AlgorithmBean Can AnalysisThe Game of NimNim AnalysisNim AlgorithmCity BattleDropping Glass BallsNumbers from EndsPennies Heads UpPatternsWhat is a pattern?Patterns are discovered, not inventedProgramming ProblemsRemoving DuplicatesSolving (related) problemsOne loop for linear structuresCoding PatternObserver/ObservableIteratorDesign patterns you shouldn’t miss( Fox - Rooster - Corn ) RiverOne key insightNaïve ApproachLeverage ProprieceptionRepresentationRepresentation (graphically)Slide 32Slide 33Slide 34( Fox - Rooster - Corn ) River Representation (graphically)Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48How this relates to CSConclusionsReferencesDesign1Algorithmic DesignThe “science” of problem solvingUsing invariants to reason about problem solvingDesign PatternsRepresenting problems graphicallyDesign2AlgorithmsWhat is Computer Science?What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline? My answer to these questions is simple --- it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex.C.A.R. (Tony) HoareAn algorithm is a recipe, a plan, or a set of instructionsWhat we think about and what we teach is often how to design algorithms or just solve problems.Design3Problem SolvingSome believe that being a good programmer will be a prerequisite for being a good mathematicianComputer-aided proofs are big (four color theorem, Kepler’s conjecture)Computer programs are very formally complete and preciseTeachers often speak of a magical “problem solving intuition”Does such a thing exist?Is it really just experience and pattern recognition?What are some tools to help learning programmers to solve problems?Design4Loop InvariantsWant to reason about the correctness of a proposed iterative solutionLoop invariants provide a means to effectively about the correctness of codewhile !done do // what is true at every step // Update/iterate // maintain invariantodDesign5Bean Can gameCan contains N black beans and M white beans initiallyEmptied according the following repeated processSelect two beans from the canIf the beans are:•same color: put a black bean back in the can•different colors: put a white bean back in the canPlayer who chooses the color of the remaining bean wins the gameAnalyze the link between the initial state and the final state Identify a property that is preserved as beans are removed from the canInvariant that characterizes the removal processDesign6Bean Can Algorithmwhile (num-beans-in-can > 1) do pick 2 beans randomly if bean1-color == bean2-color then put-back black bean else put-back white beanodDesign7Bean Can AnalysisWhat happens each turn?Number of beans in can is decreased by oneNumber of white beans is either reduced by 2 or 0Number of black beans is either reduced by 1 or 0Examine the final states for 2 bean and 3 bean initial statesAny guesses for the correct strategy?What is the process invariant?Design8The Game of NimTwo Piles of counters with N and M counters in each pile2 players take turns:Remove some number of counters (≥ 1) from one pilePlayer who removes last counter winsPropertiesComplete information: could exhaustively search for winning solutionImpartial: same moves are available for each playerDesign9Nim AnalysisDenote state by (x,y): number of counters in each pileWhat about simple case of (1,1)?For whom is (1,1) a “safe” state?How about (1,2) or (1,3)?How about (2,2)?What is the invariant to be preserved by the winning player?Design10Nim Algorithm// reach a state (x,y) where x=y on opponent’s // turn and then follow below algorithmwhile !empty(pile1) && !empty(pile2) do let opponent remove q counters from a pile remove q counters from other pileodDesign11City BattleRobots placed in opposite corners of rectangular city (nxm)City map is grid of horizontal and vertical streetsRobots move in alternating turns, moving either horizontally or verticallyThe goal of each robot is to have its opponent enter its line of fire (vertically or horizontally)What is the strategy for winning the game?Hint: Another Loop invariantDesign12Dropping Glass BallsTower with N FloorsGiven 2 glass ballsWant to determine the lowest floor from which a ball can be dropped and will breakHow?What is the most efficient algorithm?How many drops will it take for such an algorithm (as a function of N)?Design13Numbers from EndsGame begins with some even number of numbers on a line 10 5 7 9 6 12Players take turns removing numbers from the ends while keeping running sum of numbers collected so farPlayer with largest sum winsComplete information but how to win without search?Design14Pennies Heads UpFrom Car Talk!You're sitting at a table with a bunch of pennies on it. Some are facing heads up and some are facing tails up. You're wearing a blindfold, and you're wearing mittens so that you can't actually feel the coins and tell which side is facing up. I will tell you that a certain number of the pennies are facing heads up. Let's say 10 are facing heads up.Is it possible to separate those pennies into two groups, so that each group has the same number of pennies facing heads up? How do you do it? Pennies can be flipped or moved as much as neededDesign15Patterns"Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem,in such a way that you can use this solution a million times over, without ever doing it the same way twice”Alexander et. al, 1977A text on architecture!What is a programming or design pattern?Why are patterns important?Design16What is a pattern?“… a three part rule, which expresses a relation between a certain context, a problem, and a solution. The pattern is, in short, at the same time a thing, … , and the rule which tells us how to create that thing, and when we must create it.” Christopher Alexandername factory, aka