Class Note for EECS 210 with Professor Kinnersley at KU
Class Note for EECS 210 with Professor Kinnersley at KU
Popular in Course
Popular in Department
This 8 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Kansas taught by a professor in Fall. Since its upload, it has received 47 views.
Reviews for Class Note for EECS 210 with Professor Kinnersley at KU
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
EECS 210 Fall 2007 Algorithm analysis notes Most of the material below was discussed in the class lectures l ve expanded a bit on some of the examples An algorithm is a nite set of precise instructions for performing a computation or solving a problem An algorithm should have the following characteristics inputlnput values from a speci ed set output output values produced by an input set The values are the solution to the problem definiteness steps are precisely de ned correctness will return the correct output for each set of input values finiteness output must be produced in a nite number of steps generality will handle any legitimate data set without error The main thing to remember about a pseudocode algorithm is that it must be general enough to be translated into an arbitrary programming language Put another way the steps are Englishtype statements rather than code An algorithm should contain little if any language speci c syntax Indentation andor beginend blocks are used to indicate nesting or grouping Loops will be terminated with an end statement if necessary for clarity comments enclosed in braces or begin with comparison operators lt s gt 2 at Notice the use of mathematical notation eg 3 not l assignment operator You ll often see in other versions of pseudocode loops while Boolean condition or statement do test at top examples while there are vertices left to examine do while A lt 10 do for index start to nish do There may be an optional step increment size examples for i 1 to 10 do for i 1 to 30 step 3 do repeat statements to execute until Boolean condition always executes at least once example repeat examine next list item until no items remain if statements if Boolean condition then statements to execute endif if Boolean condition then statements to execute elseif Boolean condition statements to execute endif array or list elements Ai j or a Complexity of an algorithm The complexity of an algorithm is expressed in terms of the input size usually n For example sorting a list of 100 integers n 100 will take much less time than sorting a list of 1000000 integers n 1000000 We want an expression in terms of n that will describe the amount of time required to run the algorithm on an input of that size That way given a value for n we can predict how long it will take to produce an answer The complexity of an algorithm is usually expressed by one ofthree measures the best case the worst case or the average case The best case is the least amount of time required for any input of size n The best case is NOT when n 1 Typically this occurs when the input is a special case For example an already sorted list is often the best input for a sorting algorithm Similarly the worst case complexity is an expression that describes the amount of time needed for the worst possible input of size n For instance for some sorting algorithms the wors case is a list that is sorted in reverse order You can think of the worst case complexity as a guarantee in that you know no matter what the data set looks like the algorithm will never perform worse than the stated worst case complexity The average case complexity is just what the name implies if the algorithm were run on many different data sets averaging the times taken for all the data sets would give you a good idea of how long the algorithm would usually take for a data set of size n Now let s look at some algorithms and discuss how we might determine their best worst or average case complexities Example 1 Finding the largest element of a finite sequence maxa1 a2 an distinct integers max a1 initialize max to the first element of the list for i lt 2 to n if max lt ai then max ai returnmax If you also want to nd the location of the largest value the algorithm below should be used maxa1 a2 an integers max a1 initialize max to the first element of the list location 1 remember the location of max for i lt 2 to n if max lt ai then list item comparison max ai location i returnlocation If we use as the measure of complexity the number of comparisons of list items that the algorithm makes the best worst and average complexities are the same namely n 1 comparisons This makes sense because in order to find the largest of n elements all n items must be examined In the algorithms above list item comparisons occur in the for loop and the number of iterations of that loop is n 1 Example 2 Finding the largest and second largest elements of a list 1 Find the largest element by scanning from left to right 2 Go back through the list and find the second largest element big1a1 a2 an distinct integers max1 31 1 assignment for i lt 2 to n do n 1 iterations if ai gt ma thequot ma ai 1 assignment and one comparison ifmaX1 a1 thequot maxz az 1 assignment and one comparison else max2 a1 for i lt 2 to n do n 1 iterations if ai gt max2 and ai 2 max1 then 2 comparisons and one assignment each time max2 ai Total for loop 2n 1 comparisons and at most n 1 assignments returnmax1 max2 O1 constant complexity This gives us the following totals Total number of comparisons Number of assignments n 1firstforloop 1n11n 12n 1 if statement 2n 2 second for loop 3n 2 n Let s look at how the sum is computed forthe loops In the rst case we have 221 n 1 and n in the second we haveZ2 2 2n 1 Although the operations we want to count will vary frequently we count the number of comparisons or the number of assignments made Now let s look at a second method of nding the largest and second largest items in a list big2a1 a2 aquot distinct integers if a1 gt a then initialize max1 and max2 max1 lt a1 1 comparison and 2 assignments max2 lt a else max1 lt a max2 lt a1 for i lt 3 to n do n 2 iterations if ai gt max1 then 1 comparison and 2 assignments if max2 lt max1 the test succeeds othenNise ma ai there is another comparison in the else else if ai gt max 2 then max 2 ai statement returnmax1 max2 Thus in the worst case we have 2n 3 comparisons and 2n 2 assignments Notice that even though big2 and big1 both have complexity On big2 will run faster because the coef cient is smaller Note it is not possible to have both the worst case number of assignments and the worst case number of comparisons for the same list Just to keep things simple think of calculating the two quantities separately and taking the worst case value for each We now turn to the searching problem given a list ofn numbers a1 a2 an and a value X return the location of X if it is on the list and othenNise return 0 This is a linearor sequential search Notice that the algorithm below could describe either searching an array or searching a linked list If the data is in a linked list a pointer to the node contain X is returned and a nil pointer is returned ifx is not on the list Example 3 linear search linearsearchx int a1 a2 an distinct int i 1 1 assignment while i s n and x as ai 2 comparisons each time i i 1 1 assign each time ifi s n then location i 1 comparison and 1 assignment else location lt 0 Best Case X is in the rst position Two comparisons are needed in the while loop and one in the if statement for a total ofthree comparisons Worst Case lfx is not on the list 2n 2 comparisons are required 2n for the n executions ofthe while loop 1 to drop out of the while loop 1 in the if statement The worst case for a successful search is 2n 1 comparisons A question that naturally arises at this point is whether it is possible to do better than this The answer is yes if the list we are given is sorted In that case we employ the following approach compare X the value we re looking for with the element in the middle of the list If it is greater than the value in the middle search the last half of the list OthenNise search the rst half of the list This is known as a binary search This is the rst example we have of a divide and conquer algorithm Example 4 Binary search binarysearchx int a1 a2 an increasing int i 1 eft endpoint of search interval 1 assignment j lt n right endpoint of search interval 1 assignment while i ltj 1 comparison m Lij2J ifx gt am then i lt m 1 1 comparison and 1 assignment elsej lt m end ifx ai then location i 1 comparison and 1 assignment else location 0 You should go through the algorithm to convince yourself that it will terminate Also notice that we do not explicitly check if am X Instead when the size of the list is reduced to one item then we check if the item being sought is in that position Now let39s look at the complexity of binary search We39re going to count comparisons between X and elements of the list Let n 2quot Note how this is not a problem because we39re doing a worst case analysis and if the estimate is a little too high that39s not a problem There are k iterations of the while loop since i m j we can only divide the list in halfk times Thus 2k comparisons are needed 1 more comparison is needed to drop out of i m j the loop and another is needed in the if test at the bottom This gives us a total of 2k 2 comparisons Notice there is no best or worst case since every list of length n will take the same number of comparisons 21 If n 2k then k lg n Thus the complexity is 20 1 element 2 lg n 2 0Ig n We now look at two different methods that can be used to nd the largest and smallest elements of a list The second method is another divide and conquer algorithm In this case we39ll count the total number of steps Example 5 Largest and smallest list elements version 1 minmaxa1 a2 an Find the largest and smallest elements of a list miquot a1 1 assignment max a1 1 assignment for i lt 2 to n do n 1 iterations if min gtai then min ai 2n 1 2n 2 steps if max lt a then max 3 returnmax 1 returnmin 1 Total 2n 2 steps If we count only the comparisons that involve elements of the list there are 2n 2 comparisons made We now look at a recursive divide and conquer algorithm for finding the largest and smallest elements in a list The basic approach is this 1 Divide the list in half 2 Find the largest and smallest value in each half 3 Compare the two large values The larger ofthese is the largest element in the list 4 Compare the two small values The smaller of these is the smallest element in the list Obviously just dividing the list in half one time is not going to help us very much but we recursively use this process until we have a list of length two When there are just two elements one comparison is needed to determine which is the larger and which is the smaller value This is our basis case The conquer part of a divide and conquer algorithm puts the solutions of the two subproblems together For this problem steps 3 and 4 above combine the solutions That is it takes exactly two comparisons to combine the solutions of the subproblems The operation we will focus on is the number of comparisons of list items that are done in nding the max and min Example 6 Largest and smallest list elements version 2 recurminmaxbig small a1 a2 an Find the largest and smallest elements of a list if n 2 then if a1 gt a2 1 comparison big a1 small a2 else big a2 small a1 else recurminmaxbig1 small1 a1 anlz recurminmaxbigZ small2 an21 an big maxbig1 bigZ 1 comparison small minsmall1 small2 1 comparison The recurrence relation fn 2fn2 2 where the 2 represents the comparisons in the last two steps ofthe algorithm Basis case n 2 a2 1 n4 n4 n4 n4 Let s solve this by back substitution fn 2fn2 2 First note that fn2 2fn4 2 so substituting in we get fn 22fn4 2 2 22fn22 22 2 Let n 2k 222fn23 2 22 2 Then the basis case is M2 2k2k391 2 23fn23 23 22 2 we divide the list k 1 times until the list has length 2 2 f2 2 22 22 2 Now using the fact that f2 1 we get fn 2 22 2 2k 2 Remember the sum starts at i 0 not i 1 2 22 2 32 2 3n2 2 This method is faster than the first version above and in fact it can be shown that this algorithm is optimal in that no other algorithm for the problem uses fewer comparisons Sorting Another operation that we often look at is sorting a list into numerical or alphabetical order There are many different ways this can be done some of which are much more ef cient than others In sorting algorithms both comparisons and swaps of list items are counted in the analysis The algorithms we ll look at sort the list into nondecreasing order ie increasing order except there may be duplicates Let s begin with selection sort Example 7 Selection Sort selectsort A dataarray n integer Sort the list into increasing order using the following method Select the smallest element among ai an and swap with at continuing until the list is sorted 1 for i lt 1 to n 1 do Loop executes n 1 times 2 low i 3 forj i 1 to n do Number of comparisons 4 if a lt alow then n1 then n2 1 5 low j 6 swapai alaw n1 swaps one for each value ofi Let s begin with the complexity ofthe swap A swap line 6 requires three assignments Line 4 contains comparisons of list items Note that the number of comparisons remains the same no matter what the order of the list is originally The number of comparisons can be expressed by the sum n1 1in1n2 On2 Looking at the best worst and average case complexities we have swaps list item comparisons Best case n 1 nn 12 Worst case n 1 nn 12 Average case n 1 nn 12 This is On2 and also Qn2 The only real difference between the best and worst cases is the number of times the assignment in line 5 is made Since we re only looking at the number of swaps and the number of list item comparisons all three cases are exactly the same We now look at the insertion sort Example 8 Insertion Sort insertsort A data n integer AO contains a sentinel that is less than all list elements At the beginning ofthe for loop the first i 1 list items are in sorted order Then the item in position i is moved forward until its proper place is found 1 for i lt 2 to n do n1 iterations 2 llt ii tmp lt AU 2 assignments 3 while tmp lt Aj1 do up to i list item comparisons 4 All lt Ali1 1 assignment 5 l lt l 391 1 assignment 6 AU lt tmp 1 assignment How the algorithm works The initial part ofthe list is sorted Beginning with the rst element in the unsorted part of the array move that element fonNard until it s proper position is found In line 3 for each value of i at most i comparisons are made giving the total number of comparisons M 2i nn12 1 The 1 is subtracted because the sum starts with i 2 not i 1 Best case list is sorted in correct order In this case the test in the line 3 always fails Thus the total number of comparisions is n 1 and there is no movement of data Worst case list is sorted in reverse order In this case as noted above there are nn12 1 comparisons In line 4 i 1 list items will be moved for each value of i so there are On2 assignments as well The bound is fzghfsince there exists an input that requires this many comparisons and movements
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'