Algorithms: A Brief IntroductionSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSection 2.1 of [email protected] 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 mathematicianNotesAlgorithmsFormal DefinitionDefinitionAn algorithm is a sequences of unambiguous instructions forsolving a problem. Algorithms must beIFinite – must eventually terminate.IComplete – always gives a solution when there is one.ICorrect (sound) – always gives a “correct” solution.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.NotesAlgorithmsGeneral 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 include1. Brute Force (enumerative techniques, exhaustive search)2. Divide & Conquer3. Transform & Conquer (reformulation)4. Greedy TechniquesNotesPseudo-codeAlgorithms 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 implementationspecific (i.e. actual C++ or Java code or giving every step of asub-process).Good pseudo-code abstracts the algorithm, makes good use ofmathematical notation and is easy to read.NotesGoo d 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.NotesDesigning An AlgorithmA general approach to designing algorithms is as follows.1. Understand the problem, assess its difficulty2. Choose an approach (e.g., exact/approximate,deterministic/probabilistic)3. (Choose appropriate data structures)4. Choose a strategy5. Prove termination6. Prove correctness7. Prove completeness8. Evaluate complexity9. Implement and test it.10. Compare to other known approaches and algorithms.NotesMAXWhen designing an algorithm, we usually give a formal statementabout the problem we wish to s olve.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, saya1then compare it to eve ry other intege r, and update the storedmaximum if a new maximum is ever found.NotesMAXPseudo-codeMaxInput : 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 i7NotesMAXAnalysisThis is a simple enough algorithm that you should be able to:IProve it correctIVerify that it has the properties of an algorithm.IHave some intuition as to its cost.That is, how many “steps” would it take for t his algorithm tocomplete its run? What constitutes a step? How do we measurethe complexity of the step?These questions will be answered in the next few lectures, for nowlet us just take a look at a couple more examples.NotesOther examplesCheck Bubble Sort and Insertion Sort in your textb ooks, which youhave seen ad nauseum, in CSE155, CSE156, and will see again inCSE310.I will be glad to discuss them with any of you if you have not seenthem yet.NotesGreedy algorithmOptimizationIn many problems, we wish to not only find a solution, but to findthe best or optimal solution.A simple technique that works for some optimization problems iscalled 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 toproduce the best globally optimal solution.NotesExampleChange-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 want tominimize 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 and kis minimized.NotesExampleChange-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 and k isminimized.C ← ∅1for i = 1, . . . , r do2while n ≥ cido3C ← C ∪ {ci}4n ← n − ci5end6end7output C8NotesChange-Making AlgorithmAnalysisWill this algorithm always produce an optimal answer?Consider a coinage system:Iwhere c1= 20, c2= 15, c3= 7, c4= 1Iand 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, for threecoins, while the optimal is one c2and one c3for two coins.NotesChange-Making AlgorithmOptimal?What about the US currency system—is the algorithm correct inthis case?Yes, in fact, we c an prove it by contradiction.For simplicity, let c1= 25, c2= 10, c3= 5, c4= 1.NotesChange-Making AlgorithmProving optimalityProof.ILet C = {d1, d2, . . . , dk} be the solution given by the greedyalgorithm for some integer n. By way of contradiction, assumethere is another solution C0= {d01, d02, . . . , d0l} with l < k.IConsider the case of quarters. Say in C there are q quartersand in C0there are q0. If q0> q we are done.ISince the greedy algorithm uses as many quarters as possible,n = q(25) + r. where r < 25, thus if q0< q, then inn = q0(25) + r0, r0≥ 25 and so C0does not provide anoptimal solution.IFinally, if q = q0, then we continue this argument on dimesand nickels. Eventually we reach a contradiction.IThus, C = C0is our optimal solution.NotesChange-Making AlgorithmProving optimalityWhy (and where) does this proof fail in our previous counterexample to the general case?We need the following lemma:If n is a positive integer then n cents in change using quarters,dimes, nickels, and
View Full Document
Unlocking...