Design1Algorithmic Designz The “science” of problem solvingz Using invariants to reason about problem solvingz Design Patternsz Representing problems graphicallyDesign2Algorithmsz 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) Hoarez An algorithm is a recipe, a plan, or a set of instructionsz What we think about and what we teach is often how to design algorithms or just solve problems.Design3Problem Solvingz 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 precisez Teachers often speak of a magical “problem solving intuition”z Does such a thing exist?z Is it really just experience and pattern recognition?z What are some tools to help learning programmers to solve problems?Design4Loop Invariantsz Want to reason about the correctness of a proposed iterative solutionz 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 gamez Can contains N black beans and M white beans initiallyz 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 gamez Analyze the link between the initial state and the final state z 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) dopick 2 beans randomlyif bean1-color == bean2-color thenput-back black beanelseput-back white beanodDesign7Bean Can Analysisz 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 0z Examine the final states for 2 bean and 3 bean initial statesz Any guesses for the correct strategy?z What is the process invariant?Design8The Game of Nimz Two Piles of counters with N and M counters in each pilez 2 players take turns:Ê Remove some number of counters (≥ 1) from one pileÊ Player who removes last counter winsz PropertiesÊ Complete information: could exhaustively search for winning solutionÊ Impartial: same moves are available for each playerDesign9Nim Analysisz Denote state by (x,y): number of counters in each pilez What about simple case of (1,1)?z For whom is (1,1) a “safe” state?z How about (1,2) or (1,3)?z How about (2,2)?z 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) dolet opponent remove q counters from a pileremove q counters from other pileodDesign11City Battlez Robots placed in opposite corners of rectangular city (nxm)z City map is grid of horizontal and vertical streetsz Robots move in alternating turns, moving either horizontally or verticallyz The goal of each robot is to have its opponent enter its line offire (vertically or horizontally)z What is the strategy for winning the game?Ê Hint: Another Loop invariantDesign12Dropping Glass Ballsz Tower with N Floorsz Given 2 glass ballsz Want to determine the lowest floor from which a ball can be dropped and will breakz How?z What is the most efficient algorithm?z How many drops will it take for such an algorithm (as a function of N)?Design13Numbers from Endsz Game begins with some even number of numbers on a line10 5 7 9 6 12z Players take turns removing numbers from the ends while keeping running sum of numbers collected so farz Player with largest sum winsz Complete information but how to win without search?Design14Pennies Heads UpFrom Car Talk!z 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. z I will tell you that a certain number of the pennies are facing heads up. Let's say 10 are facing heads up.z 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 needed Design15Patterns"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!zWhat is a programming or design pattern?zWhy are patterns important?Design16What is a pattern?z “… 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 ushow to create that thing, and when we must create it.”Christopher AlexanderÊ name factory, aka virtual constructorÊ problem delegate creation responsibility: expression tree nodesÊ solution createFoo() method returns aFoo, bFoo,...Ê consequences potentially lots of subclassing, ...z more a recipe than a plan, micro-architecture, frameworks, language idioms made abstract, less than a principle but more than a heuristicz patterns capture important practice in a form that makes the practice accessibleDesign17Patterns are discovered, not inventedz You encounter the same “pattern” in developing solutions to programming or design problemsÊ develop the pattern into an appropriate form that makes it accessible to othersÊ fit the pattern into a language of other, related patternsz Patterns transcend programming languages, but not (always) programming paradigmsÊ OO folk started the patterns movementÊ language idioms, programming templates, programming patterns, case