Today s topics Algorithms Algorithm review Orders of Growth Integers Michael Frank Reading Sections 2 1 3 3 Upcoming CompSci 102 4 1 2 1 Algorithms Michael Frank 4 2 The foundation of computer programming Most generally an algorithm just means a definite procedure for performing some sort of task A computer program is simply a description of an algorithm in a language precise enough for a computer to understand requiring only operations that the computer already knows how to do We say that a program implements or is an implementation of its algorithm CompSci 102 Algorithm Characteristics Michael Frank 4 3 Some important general features of algorithms Input Information or data that comes in Output Information or data that goes out Definiteness Algorithm is precisely defined Correctness Outputs correctly relate to inputs Finiteness Won t take forever to describe or run Effectiveness Individual steps are all do able Generality Works for many possible inputs Efficiency Takes little time memory to run CompSci 102 Our Pseudocode Language A2 for variable initial value to final value statement while condition statement procname arguments Not defined in book return expression Michael Frank procedure name argument type variable expression informal statement begin statements end comment if condition then statement else statement CompSci 102 4 4 procedure procname arg type Michael Frank Example procedure maximum L list of integers statements defining maximum Declares that the following text defines a procedure named procname that takes inputs arguments named arg which are data objects of the type type CompSci 102 4 5 variable expression An assignment statement evaluates the expression expression then reassigns the variable variable to the value that results Example assignment statement v 3x 7 If x is 2 changes v to 13 Michael Frank x the largest integer in the list L In pseudocode but not real code the expression might be informally stated CompSci 102 4 6 Informal statement Break down algorithm into detailed steps Michael Frank 4 7 Sometimes we may write a statement as an informal English imperative if the meaning is still clear and precise e g swap x and y Keep in mind that real programming languages never allow this When we ask for an algorithm to do so andso writing Do so and so isn t enough CompSci 102 4 8 After a procedure declaration In an if statement after then or else In the body of a for or while loop Allows the sequence to be used just like a single statement Might be used begin statements end Groups a sequence of statements together begin statement 1 statement 2 statement n end Michael Frank Curly braces are used instead in many languages CompSci 102 comment Michael Frank Note that v is the largest integer seen so far Not executed does nothing Natural language text explaining some aspect of the procedure to human readers Also called a remark in some real programming languages e g BASIC Example might appear in a max program CompSci 102 4 9 if condition then statement Evaluate the propositional expression condition If the resulting truth value is True then execute the statement statement otherwise just skip on ahead to the next statement after the if statement Michael Frank Like before but iff truth value is False executes stmt2 Variant if cond then stmt1 else stmt2 CompSci 102 4 10 while condition statement Michael Frank 4 11 Evaluate the propositional Boolean expression condition If the resulting value is True then execute statement Continue repeating the above two actions over and over until finally the condition evaluates to False then proceed to the next statement CompSci 102 while condition statement end Michael Frank Also equivalent to infinite nested ifs like so if condition begin statement if condition begin statement continue infinite nested if s end CompSci 102 4 12 for var initial to final stmt Michael Frank 4 13 Initial is an integer expression Final is another integer expression Semantics Repeatedly execute stmt first with variable var initial then with var initial 1 then with var initial 2 etc then finally with var final Question What happens if stmt changes the value of var or the value that initial or final evaluates to CompSci 102 for var initial to final stmt Michael Frank end For can be exactly defined in terms of while like so begin var initial while var final begin stmt var var 1 end CompSci 102 4 14 procedure argument Michael Frank A procedure call statement invokes the named procedure giving it as its input the value of the argument expression Various real programming languages refer to procedures as functions since the procedure call notation works similarly to function application f x or as subroutines subprograms or methods CompSci 102 4 15 Max procedure in pseudocode Michael Frank if ai v then v ai found bigger at this point v s value is the same as the largest integer in the list return v procedure max a1 a2 an integers v a1 largest element so far for i 2 to n go thru rest of elems CompSci 102 4 16 Inventing an Algorithm Requires a lot of creativity and intuition Like writing proofs Michael Frank Just look at lots of examples And practice preferably on a computer And look at more examples And practice some more etc etc Unfortunately we can t give you an algorithm for inventing algorithms CompSci 102 4 17 Algorithm Inventing Example Suppose we ask you to write an algorithm to compute the predicate IsPrime N T F Computes whether a given natural number is a prime number Michael Frank 4 18 Means d divides n evenly without remainder n IsPrime n 1 d n d n First start with a correct predicate logic definition of the desired function CompSci 102 IsPrime example cont 4 19 Means d does not divide n evenly the remainder is 0 Notice that the negated exponential can be rewritten as a universal 1 d n d n 1 d n d n 2 d n 1 d n Michael Frank for d 2 to n 1 Try all potential divisors 1 n if d n then return F n has divisor d not prime return T no divisors were found n must be prime This universal can then be translated directly into a corresponding for loop CompSci 102 Optimizing IsPrime Note smaller range of search The IsPrime algorithm can be further optimized for d 2 to n1 2 if d n then return F return T Michael Frank 4 20 Proof Suppose n s smallest divisor 1 is a and let b n a Then n ab but if a n1 2 then b n1 2 since a is n s smallest divisor and so n ab n1 2 2 n an absurdity Further optimizations are possible E g only try divisors that are primes less than n1 2
View Full Document
Unlocking...