DOC PREVIEW
Duke CPS 100E - Analyzing Algorithms

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CompSci 100E7.1Analyzing Algorithmsÿ Remember SortByFreqs APT Problem:þ Start with array of words (Strings)þ Find frequency of each wordþ Return array of words ordered from most frequent to leastþ (In case of a tie, return in alphabetical order)public class SortByFreqs {public String[] sort(String[] data) {// fill in code here}}ÿ There are several approaches to a solutionþ Are they all equivalent?CompSci 100E7.2Analyzing Algorithmsÿ Consider three solutions to SortByFreqs, alsocode used in Anagram discussionþ Sort, then scan looking for changesþ Insert into Set, then count each unique stringþ Find unique elements without sorting, sort these, thencount each unique stringÿ We want to discuss trade-offs of these solutionsþ Ease to develop, debug, verifyþ Runtime efficiencyþ Vocabulary for discussionCompSci 100E7.3What is big-Oh about? (preview)ÿ Intuition: avoid details when they don’t matter, and they don’tmatter when input size (N) is big enoughþ For polynomials, use only leading term, ignore coefficientst = 3n t = 6n-2 t = 15n + 44t=n2t=n2-6n+9 t = 3n2+4nÿ The first family is O(n), the second is O(n2)þ Intuition: family of curves, generally the same shapeþ More formally: O(f(n)) is an upper-bound, when n is largeenough the expression c*f(n) is largerþ Intuition: linear function: double input, double time, quadraticfunction: double input, quadruple the timeCompSci 100E7.4More on O-notation, big-Ohÿ Big-Oh hides/obscures some empirical analysis,but is good for general description of algorithmþ Allows us to compare algorithms in the limito 20N hours vs N2microseconds: which is better?ÿ O-notation is an upper-bound, this means that Nis O(N), but it is also O(N2); we try to providetight bounds. Formally:þ A function g(N) is O(f(N)) if there exist constantscandnsuch that g(N) < cf(N) for all N>ncf(N)g(N)x=nCompSci 100E7.5Big-Oh calculations from codeÿ Search for element in an array:þ What is complexity of code (using O-notation)?þ What if array doubles, what happens to time?for(int k=0; k < a.length; k++) {if (a[k].equals(target)) return true;}return false;ÿ Complexity if we call N times on M-element vectors?þ What about best case? Average case? Worst case?CompSci 100E7.6Big-Oh calculations againÿ Alcohol APT: first string to occur 3 timesþ What is complexity of code (using O-notation)?for(int k=0; k < a.length; k++) {int count = 0;for(int j=0; j <= k; k++) {if (a[j].equals(a[k])) count++;}if (count >= 3) return a[k];};return ""; // nothing occurs three timesþ What happens to time if array doubles in size?þ 1+2+3+…+n-1, why and what’s O-notation?CompSci 100E7.7Amortization: Expanding ArrayListsÿ Expand capacity of list when add() calledÿ Calling add N times, doubling capacity as neededÿ What if we grow size by one each time?2m+1around 22m+2-22m+12m+1 - 2m+181.751485-841.5643-42122210001Capacity AfteraddResizing Costper itemCumulativecostResizing costItem #CompSci 100E7.8Some helpful mathematicsÿ 1+2+3+4+…+Nþ N(N+1)/2, exactly = N2/2 + N/2 which is O(N2) why?ÿ N + N + N + …. + N (total of N times)þ N*N = N2which is O(N2)ÿ N + N + N + …. + N + … + N + … + N (total of 3N times)þ 3N*N =3N2which is O(N2)ÿ 1+2+4+…+2Nþ 2N+1–1= 2x2N–1which is O(2N)ÿ Impact of last statement on adding 2N+1 elements to a vectorþ 1+2+…+2N+2N+1= 2N+2-1 = 4x2N-1 which is O(2N)CompSci 100E7.9Running times @ 106instructions/sec318centuries18.3 hr16.7 min0.0000301,000,000,00011.6 day19.91.00.0000201,000,0002.78 hr1.6610000.100000.000017100,0001.7 min0.1329000.010000.00001310,0001.00.0100000.001000.0000101,0000.10000.0006640.000100.0000071000.00010.0000330.000010.00000310O(N2)O(N log N)O(N)O(log


View Full Document

Duke CPS 100E - Analyzing Algorithms

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Analyzing Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Analyzing Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Analyzing Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?