Everyday Algorithms- Computers are devices that do only one kind of thing:They carry out algorithms to process information.- To computer scientists, the algorithm is the central unifying concept of computing, the mode of thought that is the core of the computing perspective.What is an algorithm?- A set of logical steps to accomplish a task.- A “recipe of action”.- A way of describing behavior.Everyday AlgorithmsWhat is wrong with the following algorithm? (From the back of a shampoo bottle.) Directions: Wet hair. Apply a small amount of shampoo, lather, rinse, repeat.Algorithms - 1Basics of AlgorithmsChocolate Chip CookiesIngredients:2 ¼ cups flour 1 tsp salt1 tsp baking soda 2 eggs¾ cup brown sugar 1 tsp vanilla extract¾ cup granulated sugar 1 cup soft butter12 oz. semi-sweet chocolate chipsSteps:Preheat oven to 375 degreesCombine flour, salt, baking soda, in bowl. Set mixture aside.Combine sugars, butter, vanilla and beat until creamy.Add eggs and beat.Add dry mixture and mix well.Stir in chocolate chips.Drop mixture by teaspoons onto ungreased cookie sheet.Bake 8 to 10 minutes.If you follow this algorithm, you will never finish washing your hair!Algorithms in ComputingIn the realm of computer algorithms, an algorithm is useful only if:- The algorithm accepts input data (not all do, however).- The algorithm processes that data in some fashion.- The algorithm produces some output (the results).However, to be a correct algorithm, it must correctly solve the problem forany valid input data. Also, for the same input data, it must always give thesame answer. Invalid input data should produce an error message or someother indication that the algorithm cannot correctly solve the problem. Itshould not produce an answer when given incorrect data since the user willthink that the answer is valid.Successful algorithms must consider all possible cases presented byacceptable data. You will succeed more quickly at constructing algorithmsif you make it a habit to:- Think about the problem and its data, then- Enumerate all the special cases that the algorithm must handle.Describing AlgorithmsIn specifying behavior, an algorithm must be:- Precise- Unambiguous- Complete- CorrectThere are various techniques that can be used to describe algorithms:- Natural language (English)- Pictures (flow-charts)- Pseudocode or a specific programming languageAlgorithms - 2Example – Algorithm RepresentationConsider an algorithm for registering for classes at UCF.Natural Language Algorithm1. Make a list of courses you want to register for, in order of priority.2. Start with an empty schedule. Number of hours = 0.3. Choose highest priority class on list.4. If the chosen class is not full and its class time does not conflict with any class already in the schedule, then register for the class:4a. Add the class to the schedule.4b. Add the class hours to the number of hours scheduled.5. Cross that class off your list.6. Repeat steps 3 through 5 until the number of hours scheduled is >= 15, or until all classes have been crossed out.7. Stop.Flowchart no yes yes no yes no no yesProperties of “Good” Algorithms1. PrecisionAlgorithms - 3BeginMake list of classes you want to takeNum_Hours = 0Choose highest priority class on listIs this class full?Is there a time conflict?Add class to class scheduleAdd class hours to Num_HoursMore classes?ENDNum_Hours >= 15Cross class off list- Each step must be clear and unambiguous in its meaning.- The order of execution of the steps must be clear.- The number of steps must be finite.- Each step must be finite.2. Simplicity- Each step must be simple enough that it can be easilyunderstood.- Each step should translate into only a few (or one) computeroperation(s) or instruction (s).3. Levels of Abstraction- The steps in the algorithm should be grouped into relatedmodules or blocks.- Modules may be nested (one inside another).- Other algorithms may be referred to by name rather thanincluding all of their steps in another algorithm.Abstraction refers to the logical grouping of concepts or objects. Thisallows you to define and implement in general terms without requiring orspecifying the details. Well-defined algorithms are organized in terms of abstraction. This meansthat we can refer to each of the major logical steps without being distractedby the details that make up each one. The simple instructions that makeup each logical step are hidden inside modules. These modules allow usto function at a higher level, to hide the details of each step inside amodule, and then refer to that module by name whenever we need to useit.Modularization allows us to:- Build and test each module independently.- Interchange equivalent modules.- Reuse modules whenever/wherever required.By hiding the details inside appropriate modules, we can understand themain ideas without being distracted. This is a key goal of using variouslevels of abstraction.- Each module represents an abstraction. The name of the moduledescribes the idea that the module implements. The instructionsAlgorithms - 4hidden within the module specify how that abstraction is toimplemented.- We can see what is being done (the idea) by reading the descriptivename of the module without having to pay attention to how it is beingimplemented.- If we want to understand how it is implemented, then we can lookinside the module to find out.Example – Levels of AbstractionConsider the following pie recipe:1. Prepare apple filling.2. Prepare crust.3. Fill crust.4. Top pie with lattice crust.5. Bake at 350 degrees for 45 minutes.6. Cool and serve.Module Prepare applie filling...Module Prepare crust...The Development of AlgorithmsIn computer science the algorithm is most often takes the form of software.In order to develop software to solve a particular problem the followingsteps must be followed:1. Understanding of the Problem- The problem must be completely understood in order to determinewhat is required for its solution.- In the university/learning environment this means that you need toread the problem carefully!Algorithms - 52. Analysis- Identify the problem inputs and outputs.3. Design- Develop a list of steps (algorithm) to solve the problem.- Refine the steps of this algorithm. (divide and