CS 2420 Class Notes Week 4
CS 2420 Class Notes Week 4 CS 2420
Popular in Intro Algorithms and Data Structures
Popular in Computer science
This 3 page Class Notes was uploaded by Nick on Friday September 16, 2016. The Class Notes belongs to CS 2420 at University of Utah taught by Miriah Meyer in Fall 2016. Since its upload, it has received 7 views. For similar materials see Intro Algorithms and Data Structures in Computer science at University of Utah.
Reviews for CS 2420 Class Notes Week 4
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/16/16
CS 2420 9-12-16 submit code together time code together, write up separate Don’t copy yourself if took the class previously. If you use it, make sure GitHub is private! algorithm analysis programs now need to terminate in a reasonable amount of time. so choose the right algorithm. Binary search reduces search space by half each time how find the complexity of code: asymptotic behavior is what happens when the limit of the function goes to infinity worst case- commonly used, easy to get average case: challenging to compute best case: not used much whenever see doubling or halving, it will be a logN smallest difference between two arrays binary search complexity log N adding to the array is complexity of 1 because it only adds one element grow function is complexity N because it loops over each item and copies to the new array remove is complexity N in best and worst case sorting is used everywhere in computer science easy sorting run in quadratic time more complicated algorithms run in NlogN selection sort - (simplest) find minimum item and swap with beginning, and then repeat on unsorted portion of the array. inner loop complexity is a sum Gouse’s trick: 1+2+3+4+5+ 10+9+8+7+6 =11+11+11+... answer: ((n-1)^2+(n-1))/2 = (n^2-n)/2 best, and worst cases are the same because never terminates early insertion sort- best case complexity is N the more unsorted an array the more work is needed. Its complexity is O(N+I) worst is when reverse sorted. Gauss’s trick: (n^2+n)/2 average is half of worst case, and complexity is still N^2 insertion sort is better than selection sort because sometimes it is better. bubble sort -- 9-14-16 there is a short homework due before Lab Friday. make sure running Java 8 on own machine Ryan has office hours at 630pm average 10-15 hours for assignment 3 selection sort is known as the simplest kind of sort insertion sort is good for small N it’s measure of unsortedness is the number of inversions Each swap removes one inversion O(N+I) need to remove more than one inversion in each step what if consider swaping non-adjacent items shell Sort known as the smallest sub quadratic algorithm set gap size to N/2 considder subarrays with elements at gap size from each other do insertion sort on each of the subarrays divide the gap size by 2 repreat steps 2-4 until the gap size is < 1 insertion sort is a specific case of shellSort (gap size of 1) invented by shell also called diminishing gap sort the compexity of the best case is NlogN insertion sort performs better the more sorted the array, more than shellSort this is good for small to medium N when use log N thought of as divide and conquer bubble sort usually the most inefficient sort (worst) fo each item, compare i ti its next neighbor ad swap if ecessary repeat untill sorted the largest finds its final position after the first iteration. They ‘bubble’ up to the top the best and worst case are the same complexity, because can’t escapt early. if don’t do any swaps then it is in order and can optimize to break out early. but, best case almost never happens it is an algoritm of rabbits and turtles large numbers move fast variations try to remove the turtiles cocktail sort: start to end then end to start comb sort: diminishing gap fr compareing pairs of items remove more than one inversion at once.