Algorithms CS APMA 202 Rosen section 2 1 Aaron Bloomfield 1 What is an algorithm An algorithm is a finite set of precise instructions for performing a computation or for solving a problem A program is one type of algorithm All programs are algorithms Not all algorithms are programs Directions to somebody s house is an algorithm A recipe for cooking a cake is an algorithm The steps to compute the cosine of 90 is an algorithm 2 Some algorithms are harder than others Some algorithms are easy Finding the largest or smallest value in a list Finding a specific value in a list Some algorithms are a bit harder Sorting a list Some algorithms are very hard Finding the shortest path between Miami and Seattle Some algorithms are essentially impossible Factoring large composite numbers In section 2 2 we ll see how to rate how hard algorithms are 3 Algorithm 1 Maximum element Given a list how do we find the maximum element in the list To express the algorithm we ll use pseudocode Pseudocode is kinda like a programming language but not really 4 Algorithm 1 Maximum element Algorithm for finding the maximum element in a list procedure max a1 a2 an integers max a1 for i 2 to n if max ai then max ai max is the largest element 5 Algorithm 1 Maximum element procedure max a1 a2 an integers max a1 for i 2 to n max if max ai then max ai 9 7 4 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 4 1 7 0 5 2 9 3 6 8 i 10 9 8 7 6 5 4 3 2 6 Maximum element running time How long does this take If the list has n elements worst case scenario is that it takes n steps Here a step is considered a single step through the list 7 Properties of algorithms Algorithms generally share a set of properties Input what the algorithm takes in as input Output what the algorithm produces as output Definiteness the steps are defined precisely Correctness should produce the correct output Finiteness the steps required should be finite Effectiveness each step must be able to be performed in a finite amount of time Generality the algorithm should be applicable to all problems of a similar form 8 Searching algorithms Given a list find a specific element in the list We will see two types Linear search a k a sequential search Binary search 9 Algorithm 2 Linear search Given a list find a specific element in the list List does NOT have to be sorted procedure linear search x integer a1 a2 an integers i 1 while i n and x ai i i 1 if i n then location i else location 0 location is the subscript of the term that equals x or it is 0 if x is not found 10 Algorithm 2 Linear search take 1 procedure linear search x integer a1 a2 an integers ii 11 while i n and x ai while i n and x ai i i 1 x 3 i i 1 if i n then location i if i location n then location i else 0 location 8 else location 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 4 1 7 0 5 2 9 3 6 8 i 1 8 7 6 5 4 3 2 11 Algorithm 2 Linear search take 2 procedure linear search x integer a1 a2 an integers ii 11 while i n and x ai while i n and x ai i i 1 x 11 i i 1 if i n then location i if i location n then location i else 0 location 0 else location 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 4 1 7 0 5 2 9 3 6 8 i 90 8 7 6 5 4 3 2 1 11 12 Linear search running time How long does this take If the list has n elements worst case scenario is that it takes n steps Here a step is considered a single step through the list 13 Algorithm 3 Binary search Given a list find a specific element in the list List MUST be sorted Each time it iterates through it cuts the list in half procedure 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 begin m i j 2 m is the point in the middle if x am then i m 1 else j m end if x ai then location i else location 0 location is the subscript of the term that equals x or it is 0 if x is not found 14 Algorithm 3 Binary search take 1 procedure binary search x integer a1 a2 an increasing integers i 1 j n while i j begin m i j 2 if x am then i m 1 else j m end if x ai then location i else location 0 x location 14 7 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 2 4 6 8 10 12 14 16 18 20 i 1 6 7 m 5 8 7 6 j 10 8 7 15 Algorithm 3 Binary search take 2 procedure binary search x integer a1 a2 an increasing integers i 1 j n while i j begin m i j 2 if x am then i m 1 else j m end if x ai then location Ii else location 0 x location 15 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 2 4 6 8 10 12 14 16 18 20 i 1 6 8 m 5 8 7 j 10 8 16 Algorithm 3 Binary search A somewhat alternative view of what a binary search does 17 Quick survey a b c d I felt I understood the search algorithms Very well With some review I ll be good Not really Not at all 18 Today s demotivators 19 Binary search running time How long does this take worst case If the list has 8 elements It takes 3 steps If the list has 16 elements It takes 4 steps If the list has 64 elements It takes 6 steps If the list has n elements It takes log2 n steps 20 Sorting algorithms Given a list put it into some order Numerical lexicographic etc We will see two types Bubble sort Insertion sort 21 Algorithm 4 Bubble sort One of the most simple sorting algorithms Also one of the least efficient It takes successive elements and bubbles them up the list procedure bubble sort a1 a2 an for i 1 to n 1 for j 1 to n i if aj aj 1 then interchange aj and aj 1 a1 an are in increasing order 22 Algorithm 4 Bubble sort An example using physical objects 24 Bubble sort running time Bubble sort algorithm for i 1 to n 1 for j 1 to n i if aj aj 1 …