1CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)Lecture Set #14:Algorithms and Design1. Algorithmic Design2. Algorithmic Analysis3. System DesignCMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)1What is an algorithm?The method used to solve a particular problem is called an algorithm.Example: Make a peanut butter and jelly sandwich:Get a loaf of breadRemove two slicesGet a jar of peanut butterGet a knifeOpen the jarUsing the knife, get some peanut butter and spread it on one slice…blah, blah, blahThere is essentially one sequential process being described.2CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)2Low-Level Design:Pseudo-Code and AlgorithmsWe have already talked about pseudo-code as a design techniqueNOT EnglishNOT a programSomething in-betweenCaptures the logic, flow of desired codeNote that pseudo-code could be translated into any programming language (not just Java)Pseudo-code is used to represent algorithms = step-by-step solutions to problemsAlgorithms are often coded as single methodsCMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)3Concerns at the Algorithmic Level of DesignCorrectnessDoes my algorithm correctly solve the problem?EfficiencyIs my algorithm fast enough for the job?ClarityIs my algorithm understandable? and is it implementable?3CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)4Putting all your eggs in one basketProblem: I have 16 baskets full of 12 eggs each; I want to “put all of my eggs in one basket”. ☺Algorithm #1 ??Combine #1 and #2Combine result with #3Combine result with #4; etc.Algorithm #2 ??Combine #1, #2; combine #3, #4; combine #5, #6…Combine <1,2> with <3,4>; Combine <5,6> with <7,8>…Combine <1,2,3,4> with <5,6,7,8>Combine last two …CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)5Algorithmic Efficiency AnalysisMeasuring which is better for time.What if the time required for the merging machine is constant?both have 15 calls to the merging machine when there are 16 baskets to mergewhat if the number of baskets is another value?What if the time required for the merging machine is dependent on the number of eggs being merged?for example 1 second per egg (i.e. merging two baskets of 12 each takes 24 seconds)this takes more math when you want to generalized on the number of baskets4CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)6Big-O NotationCategories of formulasWhat takes over as n approaches infinityO(log n)O(n)O(n * log n)O(n2)O(n2* log n)CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)7Coding vs. Software DesignCoding: writing of (Java) code to implement classes, methods, etc.Projects so far have been primarily codingWe have told you what to codeDesign: determination of what to codeWhat classes are needed? How should classes interact?What methods belong in each class?How should method functionality be implemented?High-levelLow-level5CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)8Interfaces and DesignNext level up the design hierarchy: what methods should go in classes?This information can be captured using interfacesThese interfaces can also be used to identify opportunities for polymorphism (reusable code)Rules of ThumbKeep interfaces smallThink carefully about operations needed “between classes”Use interfaces to support polymorphism (and keep code size down)CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)9Upper Levels of Software DesignWhere do ideas for classes, interactions between classes come from?Software development part of larger system design processSystem design requires identifying what system users expect system to doThese user requirements often suggest system components and how they fit togetherFirst part of software design: understand system design6CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)10System Design: What Is It?System design is concerned with:coordinating a collection of entities…… to achieve a complex processEach entity has its own responsibilities to the others to achieve an overall objectiveE.g. Running a restaurant involves a coordinated interaction of many entities within one system:Entities Chef, owners, waiters, etc.System RestaurantCMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)11Other Examples of SystemsClassroom environment: Lecturers, TAs, students, …Library: Circulation (checkout and return), indexing services (online catalogue), library users, book buyers, shelvers, …Pharmacy: Patients (and medical records), pharmacists, doctors, drug retailers, the pharmacy (products in stock), …Video game: Race cars, motorcycles, warriors, space ships, death squads, monsters, aliens, mutants, guns, swords, weapons of mass destruction, cute Japanese cartoon animals with huge eyes, …Pikachu visits Doom37CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)12Essential QuestionsChallenges: System design is very hard. Once the number of entities and interactions becomes large, it is very hard to foresee all the possible consequences of these interactions.Essential Questions:What is the desired behavior of the program (as a whole)?system design - overviewWhat are the entities that produce this behavior?classes or objectsHow do these entities interact?API for each classHow does each one work?algorithm for each taskCMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)13BehaviorSpecifying Desired Behavior: A use caseis a description of the interaction of a user and the system. It includes:Prerequisites (pre-conditions): What must hold for this use case to arise?Possible actions and interactions: What happens?Effects (post-conditions): What conditions hold, what changes have taken place, as a result of these actions.Example: Customer in a restaurant.Pre-conditions: Customer: hungry and has moneyRestaurant: has foodActions: get menu, order food, be served, eat, pay, leavePost-conditions: Customer: less hungry and less moneyRestaurant: more money and less food.8CMSC 131 Spring 2008Jan Plane (Adapted from Bonnie Dorr)14Principal Design ElementsComponents:What are the entities that make up our system?What are the roles they play?How do we separate the system into distinct units? State: What is the
View Full Document