tailieunhanh - Lecture Discrete mathematics and its applications (7/e) – Chapter 3: Algorithms

Lecture Discrete mathematics and its applications (7/e) – Chapter 3: Algorithms. This chapter presents the following content: Algorithms, example algorithms, algorithmic paradigms, growth of functions, big-o and other notation, complexity of algorithms. | Algorithms Chapter 3 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Algorithms Example Algorithms Algorithmic Paradigms Growth of Functions Big-O and other Notation Complexity of Algorithms Algorithms Section Section Summary Properties of Algorithms Algorithms for Searching and Sorting Greedy Algorithms Halting Problem Problems and Algorithms In many domains there are key general problems that ask for output with specific properties when given valid input. The first step is to precisely state the problem, using the appropriate structures to specify the input and the desired output. We then solve the general problem by specifying the steps of a procedure that takes a valid input and produces the desired output. This procedure is called an algorithm. Algorithms Definition: An algorithm is a finite set of precise instructions for performing a computation or for solving a problem. Example: Describe an algorithm for finding the maximum value in a finite sequence of integers. Solution: Perform the following steps: Set the temporary maximum equal to the first integer in the sequence. Compare the next integer in the sequence to the temporary maximum. If it is larger than the temporary maximum, set the temporary maximum equal to this integer. Repeat the previous step if there are more integers. If not, stop. When the algorithm terminates, the temporary maximum is the largest integer in the sequence. Abu Ja’far Mohammed Ibin Musa Al-Khowarizmi (780-850) Specifying Algorithms Algorithms can be specified in different ways. Their steps can be described in English or in pseudocode. Pseudocode is an intermediate step between an English language description of the steps and a coding of these steps using a programming language. The form of pseudocode we use is specified in Appendix 3. It uses some of the structures found in popular | Algorithms Chapter 3 With Question/Answer Animations Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education. Chapter Summary Algorithms Example Algorithms Algorithmic Paradigms Growth of Functions Big-O and other Notation Complexity of Algorithms Algorithms Section Section Summary Properties of Algorithms Algorithms for Searching and Sorting Greedy Algorithms Halting Problem Problems and Algorithms In many domains there are key general problems that ask for output with specific properties when given valid input. The first step is to precisely state the problem, using the appropriate structures to specify the input and the desired output. We then solve the general problem by specifying the steps of a procedure that takes a valid input and produces the desired output. This procedure is called an algorithm. Algorithms Definition: An algorithm is a finite set of precise instructions for .