Algorithms A Brief Introduction CSE235 Algorithms A Brief Introduction Slides by Christopher M Bourke Instructor Berthe Y Choueiry Spring 2006 Computer Science Engineering 235 Introduction to Discrete Mathematics 1 1 Section 2 1 of Rosen Algorithms Brief Introduction Algorithms A Brief Introduction CSE235 Real World Objects Relations Actions Computing World Data Structures ADTs Classes Relations and functions Operations Problems are instances of objects and relations between them Algorithms1 are methods or procedures that solve instances of problems 2 1 1 Algorithm is a distortion of al Khwarizmi a Persian mathematician Algorithms Formal Definition Algorithms A Brief Introduction CSE235 Definition An algorithm is a sequences of unambiguous instructions for solving a problem Algorithms must be Finite must eventually terminate Complete always gives a solution when there is one Correct sound always gives a correct solution For an algorithm to be a feasible solution to a problem it must also be effective That is it must give a solution in a reasonable amount of time There can be many algorithms for the same problem 3 1 Algorithms General Techniques Algorithms A Brief Introduction CSE235 There are many broad categories of Algorithms Randomized algorithms Monte Carlo algorithms Approximation algorithms Parallel algorithms et al Usually algorithms are studied corresponding to relevant data structures Some general styles of algorithms include 4 1 1 Brute Force enumerative techniques exhaustive search 2 Divide Conquer 3 Transform Conquer reformulation 4 Greedy Techniques Pseudo code Algorithms A Brief Introduction CSE235 Algorithms are usually presented using some form of pseudo code Good pseudo code is a balance between clarity and detail Bad pseudo code gives too many details or is too implementation specific i e actual C or Java code or giving every step of a sub process Good pseudo code abstracts the algorithm makes good use of mathematical notation and is easy to read 5 1 Good Pseudo code Example Algorithms A Brief Introduction Intersection CSE235 1 2 3 4 5 6 7 8 Input Two sets of integers A and B Output A set of integers C such that C A B C if A B then swap A B end for every x A do if x B then C C x end 9 end 10 output C Latex notation leftarrow 6 1 Designing An Algorithm Algorithms A Brief Introduction CSE235 7 1 A general approach to designing algorithms is as follows 1 Understand the problem assess its difficulty 2 Choose an approach e g exact approximate deterministic probabilistic 3 Choose appropriate data structures 4 Choose a strategy 5 Prove termination 6 Prove correctness 7 Prove completeness 8 Evaluate complexity 9 Implement and test it 10 Compare to other known approaches and algorithms MAX Algorithms A Brief Introduction CSE235 When designing an algorithm we usually give a formal statement about the problem we wish to solve Problem Given a set A a1 a2 an integers Output the index i of the maximum integer ai A straightforward idea is to simply store an initial maximum say a1 then compare it to every other integer and update the stored maximum if a new maximum is ever found 8 1 MAX Pseudo code Algorithms A Brief Introduction CSE235 Max 1 2 3 4 5 Input A set A a1 a2 an of integers Output An index i such that ai max a1 a2 an index 1 for i 2 n do if ai aindex then index i end 6 end 7 output i 9 1 MAX Analysis Algorithms A Brief Introduction CSE235 This is a simple enough algorithm that you should be able to Prove it correct Verify that it has the properties of an algorithm Have some intuition as to its cost That is how many steps would it take for this algorithm to complete its run What constitutes a step How do we measure the complexity of the step These questions will be answered in the next few lectures for now let us just take a look at a couple more examples 10 1 Other examples Algorithms A Brief Introduction CSE235 Check Bubble Sort and Insertion Sort in your textbooks which you have seen ad nauseum in CSE155 CSE156 and will see again in CSE310 I will be glad to discuss them with any of you if you have not seen them yet 11 1 Greedy algorithm Optimization Algorithms A Brief Introduction CSE235 In many problems we wish to not only find a solution but to find the best or optimal solution A simple technique that works for some optimization problems is called the greedy technique As the name suggests we solve a problem by being greedy that is choosing the best most immediate solution i e a local solution However for some problems this technique is not guaranteed to produce the best globally optimal solution 12 1 Example Change Making Problem Algorithms A Brief Introduction CSE235 For anyone who s had to work a service job this is a familiar problem we want to give change to a customer but we want to minimize the number of total coins we give them Problem Given An integer n and a set of coin denominations c1 c2 cr with c1 c2 cr P Output A set of coins d1 d2 dk such that ki 1 di n and k is minimized 13 1 Example Change Making Algorithm Algorithms A Brief Introduction Change CSE235 Input Output An integer n and a set of coin denominations c1 c2 cr with c1 c2 cr P A set of coins d1 d2 dk such that ki 1 di n and k is minimized 1 C 2 for i 1 r do 3 while n ci do 4 C C ci 5 n n ci 6 end 7 end 8 output C 14 1 Change Making Algorithm Analysis Algorithms A Brief Introduction CSE235 15 1 Will this algorithm always produce an optimal answer Change Making Algorithm Analysis Algorithms A Brief Introduction CSE235 Will this algorithm always produce an optimal answer Consider a coinage system where c1 20 c2 15 c3 7 c4 1 and we want to give 22 cents in change What will this algorithm produce Is it optimal 16 1 Change Making Algorithm Analysis Algorithms A Brief Introduction CSE235 Will this algorithm always produce an optimal answer Consider a coinage system where c1 20 c2 15 c3 7 c4 1 and we want to give 22 cents in change What will this algorithm produce Is it optimal It is not optimal since it would give us one c4 and two c1 for three coins while the optimal is one c2 and one c3 for two coins 17 1 Change Making Algorithm Optimal Algorithms A Brief Introduction CSE235 What about the US currency system is the algorithm correct in this case Yes in fact we can prove it by contradiction For simplicity let c1 25 c2 10 c3 5 c4 1 18 1 Change Making Algorithm Proving optimality Algorithms A Brief Introduction CSE235 19 1 Proof Change Making Algorithm Proving optimality Algorithms A Brief
View Full Document
Unlocking...