Understanding Properties of Algorithms in Computing
Explore the fundamental properties of algorithms used in computing, including input, output, definiteness, correctness, effectiveness, finiteness, and generality. Learn how algorithms work, their significance, and essential characteristics for solving problems efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE 222 Discrete Structures for Computing Algorithms
What is an Algorithm? What is an Algorithm?
An algorithm algorithm is a finite sequence of precise instructions for performing a computation or solving a problem. source: Discrete Mathematics and Its Applications, 7th edition by Rosen
A Recipe is an Algorithm Algorithm
The set of steps to assemble a Piece of Furniture is an Algorithm. Algorithm.
Describe an algorithm for finding the maximum value in a list of integers. Take 2 minutes Express the algorithm naturally (i.e. don t use code)
Properties of Algorithms Properties of Algorithms 1.Input 2.Output 3.Definiteness 4.Correctness 5.Effectiveness 6.Finiteness 7.Generality
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality An algorithm has input values from a specified set.
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a An algorithm has input values from a specified set. specified set. The output values are the solution to the problem.
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a The steps of an algorithm must be defined precisely. An algorithm has input values from a specified set. specified set. The output values are the solution to the problem.
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a The steps of an algorithm must be defined precisely. each set of input values. An algorithm has input values from a specified set. specified set. The output values are the solution to the problem. An algorithm should produce the correct output values for
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a The steps of an algorithm must be defined precisely. each set of input values. It must be possible to perform each step of an algorithm exactly and in a finite An algorithm has input values from a specified set. specified set. The output values are the solution to the problem. An algorithm should produce the correct output values for amount of time.
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a The steps of an algorithm must be defined precisely. each set of input values. any input in the set. It must be possible to perform each step of an algorithm exactly and in a finite (but perhaps large) An algorithm should produce the desired output after a finite An algorithm has input values from a specified set. specified set. The output values are the solution to the problem. An algorithm should produce the correct output values for amount of time. number of steps for
Properties of Algorithms 1. Input 2. Output 3. Definiteness 4. Correctness 5. Effectiveness 6. Finiteness 7. Generality From each set of input values, an algorithm produces output values from a The steps of an algorithm must be defined precisely. each set of input values. any input in the set. just for a particular It must be possible to perform each step of an algorithm exactly and in a finite (but perhaps large) for all problems of An algorithm should produce the desired output after a finite should be applicable An algorithm has input values from a specified set. specified set. The output values are the solution to the problem. set of input values. The procedure An algorithm should produce the correct output values for amount of time. number of steps for the desired form, not
Activity What properties of algorithms do the following have? Instant Ramen Instructions IKEA Bookshelf Assembly Instructions Time limit: 5 minutes
Psuedocode Psuedocode is an intermediate between an English description and an implementation in a particular language of an algorithm.
Does the max-finding algorithm have all of these properties? Input Output Definiteness Correctness Finiteness Effectiveness Generality
Activity The hailstone path length of an integer ?is the number of times the hailstone function can be applied until the result becomes 1, i.e. the value of ? such that ??= 1 for ?0= ?. ?? 1 2 3?? 1+ 1 ?? 1 is odd What are the inputs? What are the outputs? What are the steps to solve the problem? Write your algorithm in text form. Do not write in a programming language. Time limit: 5 minutes ?? 1 is even ??= hailstone
Example Solution 1 (natural language) To compute the hailstone path length of an integer n, the input is the integer n, the output is an integer giving the length of the path, and the processing is to: declare a variable with initial value 0 to keep track of the path length, do the following until n is equal to 1: if n is even, then divide n by 2; otherwise, multiply n by 3 and add 1; add 1 to the value of the length counter; return the value of the length counter.
Example Solution 2 (pseudocode) Procedurehailstone Inputs:n (integer) Outputs:m (integer) ifn is even then else returnm Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path m = n / 2 m = 3 * n + 1
Basic Elements of Pseudocode Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode: Assignment Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode: Loop Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode: Subroutine Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path Procedurehailstone Inputs:n (integer) Outputs:m (integer) ifn is even then else returnm // the next element of the hailstone path m = n / 2 m = 3 * n + 1
Basic Elements of Pseudocode: Conditional Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path Procedurehailstone Inputs:n (integer) Outputs:m (integer) ifn is even then else returnm // the next element of the hailstone path m = n / 2 m = 3 * n + 1
Basic Elements of Pseudocode: Returned Values Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Elements of Pseudocode: Comments Procedurehailstone-path-length Inputs:n (integer) Outputs:l (integer) l = 0 whilen > 1 n = hailstone(n) l = l + 1 returnl // the length of the hailstone path
Basic Outline of Pseudocode Procedure name-of-procedure Inputs:name (type), Outputs:name (type), // comments assumptions / initializations processing return name,
