Discrete Math CS 2800The algorithm problemExamples of algorithmic problemsInstance of an algorithmic problem Size of an instanceExamples of instancesAlgorithmProperties of an AlgorithmAlgorithm: Finding the Maximum Element in a Finite SequenceSlide 9Searching AlgorithmsAlgorithm: The Linear Search AlgorithmBinary searchAlgorithm: The Binary Search AlgorithmSlide 14Complexity of AlgorithmsSlide 16Example: Insertion SortDifferent notions of complexitySlide 19Slide 20Growth RatesGrowth RatesComparing algorithms wrt complexityCA2(n) = 5 n ≥ CA1(n) = 0.5 n2 for n ≤ 10CA1(n) = 0.5 n2 >CA2(n) = 5 n for n >10Growth RatesGrowth of RatesGrowth of functionsSlide 30Slide 31Slide 32Growth of functions (examples)x2 vs. (x2 + x) (x <=20)x2 vs. (x2 + x) (x2 + x) is O(n2) (oh of n-squared)Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Estimating FunctionsSlide 44Growth of functionsSlide 46Combination of Growth of functionsGrowth of functions – two more theoremsGrowth of functions - two definitionsGrowth of functions - other estimatesGrowth of functions - other estimatesSlide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 601Discrete MathCS 2800Prof. Bart [email protected] Algorithms and Growth Rates2The algorithm problemSpecification ofall legal inputsandSpecification ofdesired outputas a function of the inputAny legalinputThe algorithmThe desiredoutputExamples of algorithmic problemsProblem 1: Input: A list L, of integers Output: The sum of the integers on LProblem 3: Input: A road map of citieswith distances attached to the road map, and two designated cities A and B Output: A description of theshortest path between A and BProblem 2: Input: Two texts A and B in English Output: The list of common words in both textsInstance of an algorithmic problemSize of an instanceAn instance of an algorithmic problem is a concrete case of such a problem with specific input. The size of an instance is given by the size of its input.Examples of instances:–An instance of problem 1: L= 2, 5, 26, 8, 170, 79, 1002Problem 1: Input: A list L, of integers Output: The sum of the integers on LSize of instance length of listSize of instance = |L| = 7We use a “natural”measure of input size.Why generally ok?Strictly speaking weshould count bits.Examples of instances Problem 3: Input: A road map of citieswith distances attached to the road map, and two designated cities A and B Output: A description of theshortest path between A and B123456242 1342 32Size of instance Number of cities and roadsA particular instance:Size of instance:6 nodes9 edgesThe size of an instance is given by the size of its input.6AlgorithmDefinition:An algorithm is a finite set of precise instructions for performing a computation or for solving a problem.In general we describe algorithms using pseudocode: i.e., a language that is an intermediate step between an English language description of an algorithm and an implementation of this algorithm in a programming language7Properties of an AlgorithmInput: an algorithm has input values from a specified set.Output: for each set of input values an algorithm produces output values from a specified set. The output values are the solution of the problem.Definiteness: The steps of an algorithm must be defined precisely.Correctness: An algorithm should produce the correct output values fro each set of input values.Finiteness: an algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.Effectiveness: It must be possible to perform each step of an algorithm exactly and in a finite amount of time.Generality: the procedure should be applicable for all the problems of the desired from, not just for a particular set of input values.Distinction between: “problem” and “problem instance”Quite confusing for folks outside CS. Alg. should work for all instances!8Algorithm: Finding the Maximum Element in a Finite Sequenceprocedure max(a1,a2,…, an: integers)max := a1for i := 2 to nif max < ai then max := ai{max is the largest element}Computer ProgrammingProgrammer(human)Compiler(software)AlgorithmprogrammingProgram in high-level language (C, Java, etc)compilationEquivalent program inassembly languageEquivalent program inmachine codecomputer execution10Searching AlgorithmsSearching problems: the problem of locating an element in an ordered list.Example: searching for a word in a dictionary.11Algorithm:The Linear Search Algorithmprocedure linear search( x: integer, a1,a2,…, an: distinct integers)i := 1while (i ≤ n and x  ai )i := i +1if i < n then location := ielse location := 0{location is the subscript of the term that equals x, or is 0 if x is not found}12Binary searchTo search for 19 in the list1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22First split:1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22Second split12 13 15 16 18 19 20 22Third Split18 19 20 2219 is located as 14th item.13Algorithm:The Binary Search Algorithmprocedure binary search( x: integer, a1,a2,…, an: increasing integers)i := 1 {i is left endpoint of search interval}j := n {j is right endpoint of search interval}while i < j beginm := (i +j)/2if x > am then i := m + 1else j := mendif x = ai then location := ielse location := 0{location is the subscript of the term that equals x, or is 0 if x is not found}14Just because we know how to solve a given problem – we have an algorithm - that does not mean that the problem can be solved.The procedure (algorithm) may be so inefficient that it would not be possible to solve the problem within a useful period of time.So we would like to have an idea in terms of the “complexity” of our algorithm.15Complexity of Algorithms16Complexity of AlgorithmsThe complexity of an algorithm is the number of steps that it takes to transform the input data into the desired output.Each simple operation (+,-,*,/,=,if,etc) and each memory access corresponds to a step.(*)The complexity of an algorithm is a function of the size of the input (or size of the instance). We’ll denote the complexity of algorithm A by CA(n), where n is the size of the input.(*) This model is a simplification but still valid to give us a good idea of the complexity of algorithms.What does this mean for the complexity of, say, chess?Complexity: CA(n) = O(1)Two issues: (1) fixed input size(2) Memory access just 1 stepSo, model/defn. not always “useful”!17Example: Insertion SortFrom: Introduction to