DOC PREVIEW
Duke CPS 100E - Data and Information

This preview shows page 1-2 out of 5 pages.

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

Unformatted text preview:

Compsci 100e 5.1 Data and Information How and why do we organize data? Differences between data and information? What about knowledge? Compsci 100e 5.2 Organizing Data: ideas and issues ! Often there is a time/space tradeoff ! If we use more space (memory) we can solve a data/information problem in less time: time efficient ! If we use more more time, we can solve a data/information problem with less space: space efficient ! Search v Store: repeating the same thing again … ! We’re not “smart” enough to avoid the repetition • Learn new data structures or algorithms! ! The problem is small enough or done infrequently enough that being efficient doesn’t matter ! Markov illustrates this (next assignment) Compsci 100e 5.3 Map: store pairs of (key,value) ! Search engine: web pages for “clandestine” ! Key: word or phrase, value: list of web pages ! This is a map: search query->web pages ! DNS: domain name duke.edu ! IP: 152.3.25.24 ! Key: domain name, value: IP address ! This is a map: domain name->IP address ! Map (aka table, hash) associates keys with values ! Insert (key,value) into map, iterate over keys or pairs ! Retrieve value associated with a key, remove pair Compsci 100e 5.4 Maps, another point of view ! An array is a map, consider array arr ! The key is an index, say i, the value is arr[i] ! Values stored sequentially/consecutively, not so good if the keys/indexes are 1, 100, and 1000, great if 0,1,2,3,4,5 ! Time/space trade-offs in map implementations, we’ll see more of this later ! TreeMap: most operations take time log(N) for N-elements ! HashMap: most operations are constant time on average • Time for insert, get, … doesn’t depend on N (wow!) ! But! Elements in TreeMap are in order and TreeMap uses less memory than HashMapCompsci 100e 5.5 Map (foreshadowing or preview) ! Any kind of Object can be inserted as a key in a HashMap ! But, performance might be terrible if hashValue isn’t calculated well ! Every object has a different number associated with it, we don’t want every object to be associated with 37, we want things spread out ! Only Comparable object can be key in TreeMap ! Basically compare for less than, equal, or greater ! Some objects are naturally comparable: String, Integer ! Sometimes we want to change how objects are compared ! Sometimes we want to invent Comparable things Compsci 100e 5.6 Traceroute: where’s the map here? traceroute www.cs.dartmouth.edu traceroute to katahdin.cs.dartmouth.edu (129.170.213.101), 64 hops max, 1 lou (152.3.136.61) 2.566 ms 2 152.3.219.69 (152.3.219.69) 0.258 ms 3 tel1sp-roti.netcom.duke.edu (152.3.219.54) 0.336 ms 4 rlgh7600-gw-to-duke7600-gw.ncren.net (128.109.70.17) 184.752 ms 5 rlgh1-gw-to-rlgh7600-gw.ncren.net (128.109.70.37) 1.379 ms 6 rtp11-gw-to-rpop-oc48.ncren.net (128.109.52.1) 1.840 ms 7 rtp7600-gw-to-rtp11-gw-sec.ncren.net (128.109.70.122) 1.647 ms 8 dep7600-gw2-to-rtp7600-gw.ncren.net (128.109.70.138) 2.273 ms 9 internet2-to-dep7600-gw2.ncren.net (198.86.17.66) 10.494 ms 10 ge-0-1-0.10.nycmng.abilene.ucaid.edu (64.57.28.7) 24.058 ms 11 so-0-0-0.0.rtr.newy.net.internet2.edu (64.57.28.10) 45.609 ms 12 nox300gw1-vl-110-nox-internet2.nox.org (192.5.89.221) 33.839 ms 13 … 14 … 15 border.ropeferry1-crt.dartmouth.edu (129.170.2.193) 50.991 ms 16 katahdin.cs.dartmouth.edu (129.170.213.101) 50.480 ms Compsci 100e 5.7 John von Neumann “Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.” “There's no sense in being precise when you don't even know what you're talking about. “ “There are two kinds of people in the world: Johnny von Neumann and the rest of us.” Eugene Wigner, Noble Physicist Compsci 100e 5.8 Interface at work: Frequencies.java ! From recitation: key is a string, value is # occurrences ! Code below is slightly modified version of recitation code ! What clues for prototype of map.get and map.put? ! What if a key is not in map, what value returned? ! What kind of objects can be put in a map? ! Kinds of maps? for(String s : words) {! s = s.toLowerCase();! Integer count = map.get(s);! if (count == null){! map.put(s,1);! }! else{! map.put(s,count+1);! }! }Compsci 100e 5.9 Coding Interlude: FrequenciesSorted ! Nested classes in FrequenciesSorted ! WordPair: combine word and count together, why? • ! WPFreq: allows WordPair objects to be compared by freq • ! How are WordPair objects created? ! In doFreqsA is the comparable-ness leveraged? ! What about in sorting? ! Alternative in doFreqsB ! Use TreeMap, then ArrayList then sort, why? ! Is comparable-ness leveraged? Sorting? Compsci 100e 5.10 What can an Object do (to itself)? ! http://www.cs.duke.edu/csed/java/jdk1.6/api/index.html ! Look at java.lang.Object ! What is this class? What is its purpose? ! toString() ! Used to print (System.out.println) an object ! overriding toString() useful in new classes ! String concatenation: String s = "value "+ x; ! Default is basically a pointer-value Compsci 100e 5.11 What else can you do to an Object? ! equals(Object o) ! Determines if guts of two objects are the same, must override, e.g., for using a.indexOf(o) in ArrayList a ! Default is ==, pointer equality ! hashCode() ! Hashes object (guts) to value for efficient lookup ! If you're implementing a new class, to play nice with others you must ! Override equals and hashCode ! Ensure that equal objects return same hashCode value Compsci 100e 5.12 Objects and values ! Primitive variables are boxes ! think memory location with value ! Object variables are labels that are put on boxes String s = new String("genome"); String t = new String("genome"); if (s == t) {they label the same box} if (s.equals(t)) {contents of boxes the same} s t What's in the boxes? "genome" is in the boxesCompsci 100e 5.13 Objects, values, classes ! For primitive types: int, char, double, boolean ! Variables have names and are themselves boxes (metaphorically) ! Two int variables assigned 17 are equal with == ! For object types: String, ArrayList, others ! Variables have names and are labels for boxes ! If no box assigned, created, then label applied to null ! Can assign


View Full Document

Duke CPS 100E - Data and Information

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 Data and Information
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 Data and Information 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 Data and Information 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?