DOC PREVIEW
UNL CSCE 235 - Algorithms

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

UNL CSCE 235 - Algorithms

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?