Today’s topics§2.1: AlgorithmsAlgorithm CharacteristicsOur Pseudocode Language: §A2procedure procname(arg: type)variable := expressionInformal statementbegin statements end{comment}if condition then statementwhile condition statementSlide 12for var := initial to final stmtSlide 14procedure(argument)Max procedure in pseudocodeInventing an AlgorithmAlgorithm-Inventing ExampleIsPrime example, cont.Optimizing IsPrimeAnother example taskSearch alg. #1: Linear SearchSearch alg. #2: Binary SearchSlide 24Practice exercisesOrders of Growth - MotivationVisualizing Orders of GrowthConcept of order of growthDefinition: O(g), at most order gPoints about the definition“Big-O” Proof ExamplesBig-O example, graphicallyUseful Facts about Big OMore Big-O factsOrders of Growth (§1.8) - So FarOrder-of-Growth ExpressionsOrder of Growth EquationsSlide 38Definition: (g), exactly order gRules for exampleOther Order-of-Growth RelationsRelations Between the RelationsWhy o(f)O(x)(x)Strict Ordering of FunctionsReview: Orders of Growth (§1.8)CompSci 102 © Michael Frank 4.1Today’s topics•AlgorithmsAlgorithms–Algorithm review–Orders of Growth•Reading: Sections 2.1-3.3Reading: Sections 2.1-3.3•UpcomingUpcoming–IntegersIntegersCompSci 102 © Michael Frank 4.2§2.1: Algorithms•The foundation of computer programming.The foundation of computer programming.•Most generally, an Most generally, an algorithmalgorithm just means a definite just means a definite procedure for performing some sort of task.procedure for performing some sort of task.•A computer A computer programprogram is simply a description of an is simply a description of an algorithm, in a language precise enough for a computer to algorithm, in a language precise enough for a computer to understand, requiring only operations that the computer understand, requiring only operations that the computer already knows how to do.already knows how to do.•We say that a program We say that a program implementsimplements (or “is an (or “is an implementation of”) its algorithm.implementation of”) its algorithm.CompSci 102 © Michael Frank 4.3Algorithm CharacteristicsSome important general features of algorithms:Some important general features of algorithms:•InputInput. . Information or data that comes in.Information or data that comes in.•Output. Output. Information or data that goes out.Information or data that goes out.•Definiteness. Definiteness. Algorithm is precisely defined.Algorithm is precisely defined.•Correctness.Correctness. Outputs correctly relate to inputs.Outputs correctly relate to inputs.•Finiteness. Finiteness. Won’t take forever to describe or run.Won’t take forever to describe or run.•Effectiveness. Effectiveness. Individual steps are all do-able.Individual steps are all do-able.•Generality. Generality. Works for many possible inputs.Works for many possible inputs.•Efficiency.Efficiency. Takes little time & memory to run.Takes little time & memory to run.CompSci 102 © Michael Frank 4.4Our Pseudocode Language: §A2procedureprocedurenamename((argumentargument: : typetype))variablevariable :=:= expressionexpressioninformal statementinformal statementbeginbegin statementsstatements endend{{commentcomment}}ifif conditioncondition then then statementstatement [else [else statementstatement]]for for variablevariable :=:= initial initial valuevalue to to final valuefinal value statementstatementwhilewhile conditioncondition statementstatementprocnameprocname((argumentsarguments)) Not defined in book:Not defined in book:returnreturn expressionexpressionCompSci 102 © Michael Frank 4.5procedure procname(arg: type)•Declares that the following text defines a Declares that the following text defines a procedure named procedure named procnameprocname that takes that takes inputs (inputs (argumentsarguments) named ) named argarg which are which are data objects of the type data objects of the type typetype..–Example:Example:procedureprocedure maximummaximum((LL: list of integers): list of integers)[statements defining [statements defining maximummaximum…]…]CompSci 102 © Michael Frank 4.6variable := expression•An An assignment assignment statement evaluates the statement evaluates the expression expression expressionexpression, then reassigns the , then reassigns the variable variable variablevariable to the value that results. to the value that results.–Example assignment statement:Example assignment statement:vv :=:= 3 3xx+7 (If +7 (If xx is 2, changes is 2, changes vv to 13.) to 13.)•In pseudocode (but not real code), the In pseudocode (but not real code), the expressionexpression might be informally stated: might be informally stated:–xx :=:= the largest integer in the list the largest integer in the list LLCompSci 102 © Michael Frank 4.7Informal statement•Sometimes we may write a statement as an Sometimes we may write a statement as an informal English imperative, if the meaning informal English imperative, if the meaning is still clear and precise: is still clear and precise: e.g.e.g.,“swap ,“swap xx and and yy”” •Keep in mind that real programming Keep in mind that real programming languages never allow this.languages never allow this.•When we ask for an algorithm to do so-and-When we ask for an algorithm to do so-and-so, writing “Do so-and-so” isn’t enough!so, writing “Do so-and-so” isn’t enough!–Break down algorithm into detailed steps.Break down algorithm into detailed steps.CompSci 102 © Michael Frank 4.8begin statements end•Groups a sequence of Groups a sequence of statements together:statements together:beginbegin statement 1statement 1 statement 2statement 2 … … statement nstatement n endend•Allows the sequence to Allows the sequence to be used just like a be used just like a single statement.single statement.•Might be used:Might be used:–After a After a procedureprocedure declaration.declaration.–In an In an ifif statement after statement after thenthen or or elseelse..–In the body of a In the body of a forfor or or whilewhile loop. loop.Curly braces {} are used insteadin many languages.CompSci 102 © Michael Frank 4.9{comment}•Not executed (does nothing).Not executed (does nothing).•Natural-language text explaining some Natural-language text explaining some aspect of the procedure to human readers.aspect of the
View Full Document
Unlocking...