Algorithms: ABriefIntroductionCSE235Algorithms: A Brief IntroductionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 2.1 of [email protected] / 1Algorithms: ABriefIntroductionCSE235AlgorithmsBrief IntroductionReal World Computing WorldObjects Data Structures, ADTs, ClassesRelations Relations and functionsActions OperationsProblems are instances of objects and relations between them.Algorithms1are methods or procedures that solve instances ofproblems1”Algorithm” is a distortion of al-Khwarizmi, a Persian mathematician2 / 1Algorithms: ABriefIntroductionCSE235AlgorithmsFormal DefinitionDefinitionAn algorithm is a sequences of unambiguous instructions forsolving a problem. Algorithms must beFinite – must eventually terminate.Complete – always gives a solution when there is one.Correct (sound) – always gives a “correct” s olution.For an algorithm to be a feasible solution to a problem, it mustalso 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 / 1Algorithms: ABriefIntroductionCSE235AlgorithmsGeneral TechniquesThere are many broad categories of Algorithms: Randomizedalgorithms, Monte-Carlo algorithms, Approximation algorithms,Parallel algorithms, et al.Usually, algorithms are studied corresponding to relevant datastructures. Some general styles of algorithms include1Brute Force (enumerative techniques, exhaustive search)2Divide & Conquer3Transform & Conquer (reformulation)4Greedy Techniques4 / 1Algorithms: ABriefIntroductionCSE235Pseudo-codeAlgorithms are usually presented using some form ofpseudo-code. Good pseudo-code is a balance between clarityand detail.Bad pseudo-code gives too many details or is tooimplementation specific (i.e. actual C++ or Java code or givingevery step of a sub-process).Good pseudo-code abstracts the algorithm, makes good use ofmathematical notation and is easy to read.5 / 1Algorithms: ABriefIntroductionCSE235Good Pseudo-codeExampleIntersectionInput : Two sets of integers, A and BOutput : A set of integers C such that C = A ∩ BC ← ∅1if |A| > |B| then2swap(A, B)3end4for every x ∈ A do5if x ∈ B then6C ← C ∪ {x}7end8end9output C10Latex notation: \leftarrow.6 / 1Algorithms: ABriefIntroductionCSE235Designing An AlgorithmA general approach to designing algorithms is as follows.1Understand the problem, assess its difficulty2Choose an approach (e.g., exact/approximate,deterministic/probabilistic)3(Choose appropriate data structures)4Choose a strategy5Prove termination6Prove correctness7Prove completeness8Evaluate complexity9Implement and test it.10Compare to other known approaches and algorithms.7 / 1Algorithms: ABriefIntroductionCSE235MAXWhen designing an algorithm, we usually give a formalstatement about the problem we wish to solve.ProblemGiven 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 a1then compare it to every other integer, and update thestored maximum if a new maximum is ever found.8 / 1Algorithms: ABriefIntroductionCSE235MAXPseudo-co deMaxInput : A set A = {a1, a2, . . . , an} of integers.Output : An index i such that ai= max{a1, a2, . . . , an}index ← 11for i = 2, . . . , n do2if ai> aindexthen3index ← i4end5end6output i79 / 1Algorithms: ABriefIntroductionCSE235MAXAnalysisThis is a simple enough algorithm that you should be able to:Prove it correctVerify 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 tocomplete its run? What constitutes a step? How do wemeasure the complexity of the step?These questions will be answered in the next few lectures, fornow let us just take a look at a couple more examples.10 / 1Algorithms: ABriefIntroductionCSE235Other examplesCheck Bubble Sort and Insertion Sort in your textbooks, whichyou have seen ad nauseum, in CSE155, CSE156, and will seeagain in CSE310.I will be glad to discuss them with any of you if you have notseen them yet.11 / 1Algorithms: ABriefIntroductionCSE235Greedy algorithmOptimizationIn many problems, we wish to not only find a solution, but tofind the best or optimal solution.A simple technique that works for some optimization problemsis called the greedy technique.As the name suggests, we solve a problem by beinggreedy—that is, choosing the best, most immediate solution(i.e. a local solution).However, for some problems, this technique is not guaranteedto produce the best globally optimal solution.12 / 1Algorithms: ABriefIntroductionCSE235ExampleChange-Making ProblemFor anyone who’s had to work a service job, this is a familiarproblem: we want to give change to a customer, but we wantto minimize the number of total coins we give them.ProblemGiven An integer n and a set of coin denominations(c1, c2, . . . , cr) with c1> c2> · · · > crOutput A set of coins d1, d2, · · · , dksuch thatPki=1di= n andk is minimized.13 / 1Algorithms: ABriefIntroductionCSE235ExampleChange-Making AlgorithmChangeInput : An integer n and a set of coin denominations(c1, c2, . . . , cr) with c1> c2> · · · > cr.Output : A set of coins d1, d2, · · · , dksuch thatPki=1di= n andk is minimized.C ← ∅1for i = 1, . . . , r do2while n ≥ cido3C ← C ∪ {ci}4n ← n − ci5end6end7output C814 / 1Algorithms: ABriefIntroductionCSE235Change-Making AlgorithmAnalysisWill this algorithm always produce an optimal answer?Consider a coinage system:where c1= 20, c2= 15, c3= 7, c4= 1and 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 c4and two c1, forthree coins, while the optimal is one c2and one c3for twocoins.15 / 1Algorithms: ABriefIntroductionCSE235Change-Making AlgorithmAnalysisWill this algorithm always produce an optimal answer?Consider a coinage system:where c1= 20, c2= 15, c3= 7, c4= 1and 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 c4and two c1, forthree coins, while the optimal is one c2and one c3for twocoins.16 / 1Algorithms: ABriefIntroductionCSE235Change-Making AlgorithmAnalysisWill this algorithm always produce an optimal answer?Consider a coinage system:where c1= 20, c2= 15, c3= 7, c4= 1and we want to give 22 “cents” in
View Full Document