1、L o g oL o g o1Designing and Analysis of AlgorithmL o g oL o g o2Section 1.1-Section 1.4Chapter 1. IntroductionL o g oL o g oContentsWhat is an Algorithm?1Fundamentals of Algorithmic Problem Solving2 Important Problem Type3Fundamental Data Structure45Algorithmic IdeasL o g oL o g oWhat is an Algorit

2、hm?L o g oL o g ovAlgorithmics is more than a branch of computer science. It is the core of computer science, and, in all fairness, can be said to be relevant to most of science, business, and technology. Har92, p.6.vDavid Harel.L o g oL o g oWhat is an algorithm? An algorithm is a sequence of unamb

3、iguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.“computer” problemalgorithminputoutputL o g oL o g oWhat is an algorithm?v Recipe（秘訣）, process, method, technique, procedure, routine, with following requirements:1. F

4、initenessbterminates after a finite number of steps2. Definitenessbrigorously and unambiguously specified3. Inputbvalid inputs are clearly specified4. Outputbcan be proved to produce the correct output given a valid input5. Effectivenessbsteps are sufficiently simple and basicL o g oL o g oWhy study

5、 algorithms?vTheoretical importance the core of computer sciencevPractical importance A practitioners （從業(yè)者） toolkit （工具包） of known algorithms Framework for designing and analyzing algorithms for new problemsL o g oL o g oAlgorithmvAn algorithm is a sequence of unambiguous instructions for solving a

6、problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.L o g oL o g oHistorical PerspectivevEuclids（歐幾里得） algorithm for finding the greatest common divisorvMuhammad ibn Musa al-Khwarizmi（花拉子模） 9th century mathematician /science/parshall

7、/khwariz.htmlL o g oL o g oNotion of algorithm“computer” Algorithmic solutionproblemalgorithminputoutput The range of inputs for which an algorithm works has to be specified carefully. The same algorithm can be represented in several different ways. Several algorithms for solving the same problem ma

8、y exist. Algorithms for the same problem can be based on very different ideas and can solve the with dramatically different speeds.L o g oL o g oEuclids AlgorithmProblem: Find gcd(m,n), the greatest common divisor of two nonnegative, not both zero integers m and nExamples: gcd(60,24) = 12, gcd(60,0)

9、 = 60, gcd(0,0) = ? Euclids algorithm is based on repeated application of equalitygcd(m,n) = gcd(n, m mod n)until the second number becomes 0, which makes the problem trivial.Example: gcd(60,24) = gcd(24,12) = gcd(12,0) = 12L o g oL o g oTwo descriptions of Euclids algorithmStep 1 If n = 0, return m

10、 and stop; otherwise go to Step 2Step 2 Divide m by n and assign the value fo the remainder to rStep 3 Assign the value of n to m and the value of r to n. Go to Step 1.while n 0 do r m mod n m n n r return mL o g oL o g oOther methods for computing gcd(m,n)Consecutive integer checking algorithmStep

11、1 Assign the value of minm,n to tStep 2 Divide m by t. If the remainder is 0, go to Step 3; otherwise, go to Step 4Step 3 Divide n by t. If the remainder is 0, return t and stop; otherwise, go to Step 4Step 4 Decrease t by 1 and go to Step 2L o g oL o g oOther methods for gcd(m,n) cont.Middle-school

12、 procedureStep 1 Find the prime factorization （因式） of mStep 2 Find the prime factorization of nStep 3 Find all the common prime factorsStep 4 Compute the product of all the common prime factors and return it as gcd(m,n)Is this an algorithm?L o g oL o g ovExample: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

13、 17 18 19 20 21 22 23 24 25L o g oL o g oSieve of EratosthenesInput: Integer n 2Output: List of primes less than or equal to nfor p 2 to n do Ap pfor p 2 to n do if Ap 0 /p hasnt been previously eliminated from the list j p* p while j n do Aj 0 /mark element as eliminated j j + pL o g oL o g ov/copy

14、 the remaining elements of A to array L of the primes i 0 for p 2 to n do if Ap 0 Li Ap i i+1 return LL o g oL o g ovFundamentals of Algorithmic Problem SolvingL o g oL o g o1.2 Fundamentals of Algorithmic Problem SolvingvWe can consider algorithms to be procedural solutions to problems.vIt is this

15、emphasis on precisely defined constructive procedures that makes computer science distinct from other disciplines.L o g oL o g oAlgorithm design and analysis processvUnderstand the problemv Decide on: computational means, exact vs. approximate solving, data structure(s), algorithm design techniquevD

16、esign an AlgorithmvProve correctnessvAnalyze the algorithmvCode the algorithmL o g oL o g oUnderstand the problemvAn input to an algorithm specifies an instance of the problem the algorithm solves.vIt is very important to specify exactly the range of instances the algorithm needs to handle.vIf you f

17、ail to do this, your algorithm may work correctly for a majority of inputs but crash on some “boundary” value.L o g oL o g oAscertaining the Capabilities of a Computational DevicevOnce you completely understand a problem, you need to ascertain the capabilities of the computational device the algorit

18、hm is intended for.vvon Neumann machinevRandom-access machine (RAM)vSequential algorithmsvParallel algorithmsL o g oL o g oChoosing between Exact and Approximate Problem SolvingvExact algorithm Solving the problem exactlyvApproximation algorithm Solving the problem approximately1.There are important

19、 problems that simply cannot be solved exactly for most of their instances;2.Available algorithms for solving a problem exactly can be unacceptably slow because of the problems intrinsic complexity.L o g oL o g oDeciding on Appropriate Data StructurevSome algorithms do not demand any ingenuity in re

20、presenting their inputs.vBut others are, in fact, predicated on ingenious data structures.vAlgorithms + Data Structure = ProgramsL o g oL o g oAlgorithm Design TechniquesvAn algorithm design technique (or “strategy” or “paradigm”) is a general approach to solving problems algorithmically that is app

21、licable to a variety of problems from different areas of computing.Why to learn the technique.v1. The technique provide guidance for designing algorithm for new problems for there is no known satisfactory algorithm.v2. Algorithm are the cornerstone of computer science.L o g oL o g oMethods of Specif

22、ying an AlgorithmvOnce you have designed an algorithm, you need to specify it in some fashion.vNatural languagevPseudocodevFlowchartL o g oL o g oL o g oL o g oL o g oL o g oProving an Algorithms correctnessvOnce an algorithm has been specified, you have to prove its correctness.vWe have to prove th

23、at algorithm yields a required result for every legitimate input in finite amount of time.vFor some algorithms, a proof of correctness is quite easy; for others, it can be quite complex.vMathematical inductionvInvestigation L o g oL o g oAnalyzing an AlgorithmvTime efficiency indicates how fast the

24、algorithm runs.vSpace efficiency indicates how much extra memory the algorithm needs.vAnother desirable characteristic of an algorithm is simplicity.vFor example, most people would agree that Euclids algorithm is simpler than the middle-school procedure for computing gcd(m,n).L o g oL o g oCoding an

25、 AlgorithmvOnce an algorithm is selected, a 10-50% speedup may be worth an effort.v“As a rule, a good algorithm is a result of repeated effort and rework.”vIn the academic world, the question leads to an interesting but usually difficult investigation of an algorithms optimality.L o g oL o g ovThere

26、 is nothing further from the truth:“Inventing (or discovering?) algorithms is a very creative and rewarding process.”L o g oL o g ovImportant Problem TypeL o g oL o g oImportant problem typesvsortingvsearchingvstring processingvgraph problemsvcombinatorial problemsvgeometric problemsvnumerical probl

27、emsL o g oL o g o(1)Example of computational problem: sortingvStatement of problem: Input: A sequence of n numbers Output: A reordering of the input sequence so that ai aj whenever i jvInstance: The sequence vAlgorithms: Selection sort Insertion sort Merge （合并）sort (many others)L o g oL o g o(2)Exam

28、ple of computational problem: SearchingvThe searching problem deals with finding a given value, called a search key, in a given set.vThe latter algorithms are of particular importance for real-life applications because they are indispensable for storing and retrieving information from large database

29、s.L o g oL o g o(3)Example of computational problem: String ProcessingvA string is a sequence of characters from an alphabet.vString matching problem: Several algorithms that exploit the special nature of this type of searching have been invented.L o g oL o g o(4) Example of computational problem: G

30、raph problemvGraph algorithms: oldest and most interestingArea in algorithmicTraveling salesman problemGraph-coloring problemL o g oL o g o(5)Example of computational problem: Combinatiorial ProblemsvCombinatorial problems are the most difficult problems in computing, from both the theoretical and p

31、ractical standpoints. The number of combinatorial objects typically grows extremely fast with a problems size. There are no known algorithms for most computer scientists believe that such algorithms do not exist.L o g oL o g oSome Well-known Computational ProblemsvSortingvSearchingvShortest paths in

32、 a graphvMinimum spanning treevPrimality testing （素性測試）vTraveling salesman problemvKnapsack problemvChessvTowers of HanoivProgram terminationL o g oL o g o(6) Geometric ProblemsvGeometric algorithms deal with geometric objects such as points, lines, and polygons.vTwo classic problems of computationa

33、l geometry:. The closet-pair problem is self-explanatory: given n points in the plane, find the closet pair among them. The convex-hull problem ask to find the smallest convex polygon that would include all the points of a given set.L o g oL o g o(7) Numerical ProblemsvProblems involving mathematical objects of continuous nature:vSolving equations and systems of equationsvComputing definite integralsvEvaluating functionsL o g oL o g ovFundamental Data StructureL o g oL o g oFundamental data structuresv list array linked list stri