CSCI103 03b Strategy_Formal(print)4

1 CSCI103 Autumn 2010 Algorithms and Problem Solving (S3b) Problem solving strategies and Formal problem solving Problem Solving Strategies • We have seen examples of how brute force can be  used, and how it isn’t always the best strategy. • We are going to look at some of the basic strategies  which are widely employed: B t F– Brute Force. – Trial & Error. – Analogy. – Divide & Conquer. – Heuristics. • There are many others, but this list is a good start. Brute Force • Work through every possible combination of  actions until you find that satisfies the  requirements for a solution. • If a recognisable solution exists, this method  will find it, but it may take a long time … – If … There may be no solution. – Recognisable … We may not recognise a solution. • Place the numbers 1‐9 into the boxes, such  that the sum of the entries in any row, or  any column, or any main diagonal, is the  same. 8 1 68 1 6 3 5 7 4 9 2 „ Max No of trials = 9! = 362 880. „ For a 4x4 square the maximum number of trails is 16! ≈ 2*1013. 2 Proofs by “brute force” • This is also known as proof by exhaustion, proof by cases, or  perfect induction. • This method of mathematical proof involves splitting the  problem into a finite number of cases, and proving each case  separately.  • A proof by exhaustion has two stages:A proof by exhaustion has two stages: – A proof that the cases are exhaustive; i.e., that each instance of the  statement to be proved matches the conditions of (at least) one of the  cases. – A proof of each of the cases.  • There is no upper limit to the number of cases allowed in a  proof by exhaustion.  • Sometimes there are only two or three cases, but there may  be thousands, millions or more. • For example, rigorously solving an endgame puzzle in  chess might involve considering a very large number of  possible positions in the game tree of that problem. – We will talk about game trees later. • A well known theorem to which proof by exhaustion  has been applied is the four colour theorem. – The first proof considered 1 936 casesThe first proof considered 1,936 cases. – The shortest known proof still has over 600 cases. • These proofs were controversial because the majority  of the cases were checked by a computer program, not  by hand. • Mathematicians prefer to avoid proofs with large  numbers of cases. – A proof with a large number of cases leaves an impression  that the theorem is only true by coincidence, and not  because of some underlying principle or connection.  • Other types of proofs, such as proof by mathematical  induction, are considered more elegant. • However, there are some important theorems for p which no other method of proof has been found. – The proof that there is no finite projective plane of order 10.  – The classification of finite simple groups.  – The Kepler conjecture. Find a solution to … • … this magic square problem, with the  sums needing to be 15, and distinct  values in every position. • How many possible solutions are there? • How long would brute force take? 84.5 8 2.5 3 5 7 7.5 2 5.5 „ Actually there aren’t any solutions if we are restricted to 1- 9… / – But there are an infinite number of solutions. „ This is a warning; Brute force when you don’t really understand the solution space or the problem is possibly a waste of time! 3 Another strategy: Trial and Error • A variation of Brute Force where you make guesses. – Dictionary attack for password guessing is somewhat like this. • Trying one candidate solution after another  until you are successful (if ever!) • When this strategy is combined with logical reasoning, it  eliminates impossible solutions. • We might have thought of using trial and error to solve the  matches problem. Another strategy: Analogy A tourist wants to convert $100 American dollars to  Australian dollars. If the rate is $1.3 AUD to the USD,  how many Australian dollars will he get? A car travelling at the average speed of 80 km/h reaches its destination after 5 hours. How far has it travelled? If you know how to solve the first problem, you can solve the second problem by analogy. Divide and Conquer • Consists of three main steps: – Divide the original problem into a number of smaller ones. – Solve (“conquer”) the sub‐problems. – Combine the solutions of the sub‐problems into a solution  for the original solutionfor the original solution. • We used this with one of the river crossing exercises. • Hopefully you came across something similar in the  “Where’s Wally / ZKP” tutorial. • Suppose that we are trying to find the thickest book in  the university library. • We could simplify the problem by finding the thickest  book on each floor of the library, and comparing the  thickness of each of those. • We could further divide the problem by finding the  thickest book on each shelf row, and find that bythickest book on each shelf row, and find that by  further division into each shelf. • Sometimes divide and conquer provides a purely  organisational advantage, other times a computational  advantage too. – The computational advantage occurs if we can distribute the  work. 4 Algorithms Revisited • An algorithm describes a method to  accomplish a task (carry out a process or solve  a problem). • An Algorithm is a finite sequence of g q instructions, each of which has a clear  meaning and can be performed with a finite  amount of effort in a finite length of time. – It’s finite! A Few Familiar (?) Algorithms Process Algorithm Typical steps in the algorithm Knitting a sweater Knitting pattern Knit one, purl one Baking a cake Building an electronic circuit … … … Recipe Assembly instructions Beat the eggs until smooth Solder motor leads to board Algorithms in Computer Science To carry out a process on a computer one  must: –Design an algorithm which describes how  the process is to be performed (this is  programming).programming). – Express the algorithm as a program in some  programming language (this is coding, or  one sort of coding anyway). –Get the computer to execute the program. (After you’ve completed the code what must you do to be  able to run it on a computer? This is a CSCI114 question…) Wearing a top hat… • So far we have been representing solutions to problems  in (mostly) fairly ad hoc ways, varied to suit the particular  problem. • In some tutorials and assignments you are required to  write solutions by indicating all the steps necessary to get  to the solution : This is your algorithm to solve the  problem. h l h k l h l ll• While this makes your solutions somewhat clear it is still  informal and it may not be clear enough. • In particular, the same solution may be written by  different students in very different ways. – And we might not even recognise them as being equivalent in  some sense. • We are going to introduce a more formal means of  describing algorithms, pseudocode. 5 What is Pseudocode? • It is a formal way of representing the solutions to  problems. – It is designed to be clear and precise. • Pseudocode is written in a natural language such• Pseudocode is written in a natural language such  as English, but … – In a structured and – … abbreviated manner, so … – … we can easily convert the description into a  programming language. • Assuming we know the syntax of that language! An Example • Write pseudocode to instruct someone  how to add up a list of prices using a pocket  calculator. turn on calculator clear calculatorclear calculator repeat the following instructions until all prices on the list have been entered key in next dollar amount key in decimal point (.) key in cents amount press addition (+) key press equals write down the total price turn off calculator “It has been said that a person does not really understand something until he teaches it. Actually a person does not really Actually a person does not really understand something until he can teach it to a computer.” (Donald Knuth 1974) How do we write pseudocode?  • There is no standard pseudocode at present. – And it is important not to get too tied up in the “syntax”. – You don’t compile pseudocode so a semicolon in the  wrong place shouldn’t break it. – Putting brackets in the wrong places in logic or arithmeticPutting brackets in the wrong places in logic or arithmetic  expressions could cause problems though so don’t be  sloppy. • Your pseudocode should be: – Clear. – Concise. – Consistent. 6 Important rules: • One pseudocode statement per line. • If you can't define a task by writing a short statement y y g on one line, it's too general: – Break it up into smaller tasks. • If you can't write a complete but simple statement,  the task is too specific. Another example Write a set of instructions to print a particular greeting to members of a  forum. A new member will get a standard welcome message, with  information on how to use the forum. An existing member will get a  greeting and a list of all new messages posted since the last visit.  Check member statusCheck member status IF the member is new THEN Display standard welcome message Change member status to old ELSE Display greeting Get date of last visit from database Get all messages posted after that date Display list of new messages ENDIF OTHERWISE is another choice The Three Constructs • So what goes into our pseudocode representation of  an algorithm? • There are three "constructs" or control structures that are used in most computer program algorithms: S– Sequence: • An ordered list or sequence of instructions (steps). – Decision (selection) • We often need to test if some condition is true or not true, and  have different sequences associated with different results. – Repetition (loop) • We may need to repeat some sequence of instructions. The Sequence Construct • Sequential control is indicated by writing one action  after another. • Each action on a line by itself. • All actions are aligned with the same indent. – This makes it easier to follow the sequenceThis makes it easier to follow the sequence. • The actions are performed in the order, top to bottom,  that they are written. Brush teeth Wash face Comb hair Smile in mirror 7 READ height of rectangle READ width of rectangle COMPUTE area as height times widthCOMPUTE area as height times width The capitalised words are special words, referred to as  keywords. Some more keywords • There are quite a few keywords: • Input:  READ, OBTAIN, GET • Output:  PRINT, DISPLAY, SHOWSHOW • Compute:  COMPUTE, CALCULATE, DETERMINE • Initialize:  SET, INIT • Add one:  INCREMENT The Decision Construct  • The general form is:  IF condition is true THEN sequence 1 ELSE sequence 2q ENDIF IF a student's grade is 50 or more THEN PRINT "passed" ELSE PRINT "failed" ENDIF Cascading Decisions  • The general form is:  IF condition A is true THEN sequence 1 ELSEIF condition B is true THENELSEIF condition B is true THEN sequence 2 ELSEIF condition C is true THEN sequence 3 ELSE sequence 4 ENDIF 8 IF a student's grade is greater than or equal to 85 THEN PRINT “High Distinction ☺☺☺” ELSEIF a student's grade is greater than or equal to 75 THEN PRINT “Distinction ☺☺” ELSEIF a student's grade is greater than or equal to 65 THEN PRINT “Credit ☺” ELSEIF a student's grade is greater than or equal to 50 THEN PRINT “Pass”PRINT Pass ELSEIF a student's grade is greater than or equal to 45 THEN PRINT “Pass conceded /” ELSE PRINT “Failed //” ENDIF Multiway Decision • The general form is:  CASE expression IS case 1 : sequence 1 q case 2 : sequence 2 ... case n : sequence n OTHERWISE: default sequence ENDCASE CASE Title IS Mr : PRINT "Mister“ Mrs : PRINT "Missus“ Miss : PRINT "Miss“ss ss Ms : PRINT "Ms“ Dr : PRINT "Doctor “ ENDCASE The Pre‐Test Repetition Structure • The general form is: WHILE condition is true sequencesequence ENDWHILE WHILE Population less than Limit COMPUTE Population as Population + Births - Deaths ENDWHILE 9 The Post‐Test Repetition Structure • The general form is:  REPEATREPEAT sequence UNTIL condition is true The sequence is performed at least once! The Counted Repetition Structure • The general form is:  DO n TIMESDO n TIMES sequence ENDDO Nested Constructs SET total to zero REPEAT READ Temperature IF Temperature > Freezing Indentation isi i l!p gTHEN INCREMENT total ENDIF UNTIL Temperature < zero PRINT total critical! Layered IF Statements (“Non‐linear”) IF studAttend = partTime THEN IF studGender = female THEN IF studAge > 21 THEN INCREMENTmatureFemPT ELSE INCREMENT F PTINCREMENT youngFemPT ENDIF ELSE INCREMENT malePT ENDIF ELSE INCREMENT FT ENDIF We can have many layers! 10 Two Basic Data types • Programming languages have different data  types, to represent different types of data. – Actually some programming languages have untyped  data which you have to use carefully. • We are going to start with two basic data types: Integer Numbers: 85, 21 Text:  “John” “7 Excellent Street, Wonderful, NSW” Variables • Data can be stored in variables – Variables are names for memory locations where data can  be stored, accessed and changed. • score=85 • age=21 • name=“John” dd “7 E ll t St t W d f l NSW”• address=“7 Excellent Street, Wonderful, NSW” 85 21 score age Johnname 7 Excellent Street, Wonderful, NSWaddress In a program variable names would usually be unique and should usually be meaningful Meaningful names • Why should names be meaningful? – This provides documentation to help us  understand what the algorithm is doing. • This is particularly important for an algorithm that weThis is particularly important for an algorithm that we  didn’t write and are trying to read. – It helps prevent inadvertent errors. Poor variable names … • Here goes (most of) a C++ program. • int _[3]={1},___=7744,__[2]={((1<<5)‐(1<<3))};void  a(){(_[0]>__[1])?(cout<<_[1]+(((2<<2)*('z'>>1)*'R')>>1)<