AlgorithmsWhat is an algorithm?Some algorithms are harder than othersAlgorithm 1: Maximum elementSlide 5Slide 6Maximum element running timeProperties of algorithmsSearching algorithmsAlgorithm 2: Linear searchAlgorithm 2: Linear search, take 1Algorithm 2: Linear search, take 2Linear search running timeAlgorithm 3: Binary searchAlgorithm 3: Binary search, take 1Algorithm 3: Binary search, take 2Slide 17Binary search running timeSorting algorithmsAlgorithm 4: Bubble sortSlide 22Bubble sort running timeAlgorithm 5: Insertion sortInsertion sort running timeComparison of running times11AlgorithmsAlgorithmsCS 202CS 202Epp section ???Epp section ???Aaron BloomfieldAaron Bloomfield22 What is an algorithm?What is an algorithm?An algorithm is “a finite set of precise An algorithm is “a finite set of precise instructions for performing a computation or for instructions for performing a computation or for solving a problem”solving a problem”A program is one type of algorithmA program is one type of algorithmAll programs are algorithmsAll programs are algorithmsNot all algorithms are programs!Not all algorithms are programs!Directions to somebody’s house is an algorithmDirections to somebody’s house is an algorithmA recipe for cooking a cake is an algorithmA recipe for cooking a cake is an algorithmThe steps to compute the cosine of 90The steps to compute the cosine of 90°° is an is an algorithmalgorithm33 Some algorithms are harder than Some algorithms are harder than othersothersSome algorithms are easySome algorithms are easyFinding the largest (or smallest) value in a listFinding the largest (or smallest) value in a listFinding a specific value in a listFinding a specific value in a listSome algorithms are a bit harderSome algorithms are a bit harderSorting a listSorting a listSome algorithms are very hardSome algorithms are very hardFinding the shortest path between Miami and SeattleFinding the shortest path between Miami and SeattleSome algorithms are essentially impossibleSome algorithms are essentially impossibleFactoring large composite numbersFactoring large composite numbersIn section 2.2, we’ll see how to rate how “hard” In section 2.2, we’ll see how to rate how “hard” algorithms arealgorithms are44 Algorithm 1: Maximum elementAlgorithm 1: Maximum elementGiven a list, how do we find the maximum Given a list, how do we find the maximum element in the list?element in the list?To express the algorithm, we’ll use To express the algorithm, we’ll use pseudocodepseudocodePseudocode is kinda like a programming Pseudocode is kinda like a programming language, but not reallylanguage, but not really55 Algorithm 1: Maximum elementAlgorithm 1: Maximum elementAlgorithm for finding the maximum element Algorithm for finding the maximum element in a list:in a list:procedureprocedure max ( max (aa11, , aa22, …, , …, aann: integers): integers)maxmax := := aa11forfor i := 2 i := 2 toto n nifif max < max < aaii thenthen maxmax := := aaii{{maxmax is the largest element} is the largest element}66 procedureprocedure max ( max (aa11, , aa22, …, , …, aann: integers): integers)maxmax := := aa11forfor ii := 2 := 2 toto n nifif max < max < aaii thenthen maxmax := := aaii maxmax := := aa11forfor ii := 2 := 2 toto n nifif max < max < aaii thenthen maxmax := := aaiiAlgorithm 1: Maximum elementAlgorithm 1: Maximum element44117700552299336688aa11aa22aa33aa44aa55aa66aa77aa88aa99aa1010maxmaxii234567891047977 Maximum element running timeMaximum element running timeHow long does this take?How long does this take?If the list has If the list has nn elements, worst case elements, worst case scenario is that it takes scenario is that it takes nn “steps” “steps”Here, a step is considered a single step Here, a step is considered a single step through the listthrough the list88 Properties of algorithmsProperties of algorithmsAlgorithms generally share a set of properties:Algorithms generally share a set of properties:Input: what the algorithm takes in as inputInput: what the algorithm takes in as inputOutput: what the algorithm produces as outputOutput: what the algorithm produces as outputDefiniteness: the steps are defined preciselyDefiniteness: the steps are defined preciselyCorrectness: should produce the correct outputCorrectness: should produce the correct outputFiniteness: the steps required should be finiteFiniteness: the steps required should be finiteEffectiveness: each step must be able to be Effectiveness: each step must be able to be performed in a finite amount of timeperformed in a finite amount of timeGenerality: the algorithm Generality: the algorithm shouldshould be applicable to all be applicable to all problems of a similar formproblems of a similar form99 Searching algorithmsSearching algorithmsGiven a list, find a specific element in the Given a list, find a specific element in the listlistWe will see two typesWe will see two typesLinear searchLinear searcha.k.a. sequential searcha.k.a. sequential searchBinary searchBinary search1010 Algorithm 2: Linear searchAlgorithm 2: Linear searchGiven a list, find a specific element in the listGiven a list, find a specific element in the listList does NOT have to be sorted!List does NOT have to be sorted!procedureprocedure linear_search ( linear_search (xx: integer; : integer; aa11, , aa22, …, , …, aann: : integers)integers)ii := 1 := 1whilewhile ( ( ii ≤ ≤ nn and and xx ≠ ≠ aaii ) )ii := := ii + 1 + 1ifif ii ≤≤ nn thenthen locationlocation := i := ielseelse locationlocation := 0 := 0{{locationlocation is the subscript of the term that equals x, or it is is the subscript of the term that equals x, or it is 0 if x is not found}0 if x is not found}1111 procedureprocedure linear_search ( linear_search (xx: integer; : integer; aa11, , aa22, …, , …, aann: integers): integers)ii := 1 := 1whilewhile ( ( ii ≤ ≤ nn and and xx ≠ ≠ aaii ) )ii := := ii + 1 + 1ifif ii ≤≤ nn thenthen locationlocation := i := ielseelse locationlocation := 0 := 0 ii := 1 := 1whilewhile ( ( ii ≤ ≤ nn and and xx ≠ ≠ aaii ) )ii := := ii + 1 + 1ifif ii ≤≤ nn thenthen locationlocation := i := ielseelse locationlocation := 0 := 0Algorithm 2: