16.03.

2026

Empirical analysis
Running a program and measuring its performance

Building Java Programs [Link]()

– Returns an integer representing the number of milliseconds that
Chapter 11 have passed since 12:00am, January 1, 1970.
• The result is returned as a value of type long, which is like int but
with a larger numeric range (64 bits vs. 32).
Java Collections Framework
– Can be called twice to see how many milliseconds have elapsed
between two points in a program.
Copyright (c) Pearson 2020.
All rights reserved.

• How much time does it take to store Moby Dick into a List?
4

1 4

Java collections framework Sets (11.2)

• set: A collection of unique values (no duplicates allowed)
that can perform the following operations efficiently:
– add, remove, search (contains)

– We don't think of a set as having indexes; we just

add things to the set in general and don't worry about order

"the"
"if" "of"
[Link]("to") "to"
"down" "from" true
"by" "she"
[Link]("be") "you" false
"in"
"why" "him"

set
2 5

2 5

Exercise Set implementation

• Write a program that counts the number of unique words in a • in Java, sets are represented by Set interface in [Link]
large text file (say, Moby Dick or the King James Bible).
– Store the words in a collection and report the # of unique words.
• Set is implemented by HashSet and TreeSet classes

– HashSet: implemented using a "hash table" array;

– Once you've created this collection, allow the user to search it to very fast: O(1) for all operations
see whether various words appear in the text file. elements are stored in unpredictable order

– TreeSet: implemented using a "binary search tree";

• What collection is appropriate for this problem? pretty fast: O(log N) for all operations
elements are stored in sorted order

– LinkedHashSet: O(1) but stores in order of insertion

3 6

3 6
 16.03.2026

Set methods The "for each" loop (7.1)

List<String> list = new ArrayList<String>(); for (type name : collection) {
...
Set<Integer> set = new TreeSet<Integer>(); // empty statements;
Set<String> set2 = new HashSet<String>(list); }

– can construct an empty set, or one based on a given collection

• Provides a clean syntax for looping over the elements of a Set,
List, array, or other collection
add(value) adds the given value to the set
contains(value) returns true if the given value is found in this set Set<Double> grades = new HashSet<Double>();
...
remove(value) removes the given value from the set
clear() removes all elements of the set for (double grade : grades) {
size() returns the number of elements in list [Link]("Student's grade: " + grade);
}
isEmpty() returns true if the set's size is 0
toString() returns a string such as "[3, 42, -7, 15]"
– needed because sets have no indexes; can't get element i
7 10

7 10

Set operations Maps vs. sets

• A set is like a map from elements to boolean values.
– Set: Is "Marty" found in the set? (true/false)

"Marty" true
Set
false
addAll retainAll removeAll

addAll(collection) adds all elements from the given collection to this set
containsAll(coll) returns true if this set contains every element from given set
returns true if given other set contains the same elements
– Map: What is "Marty" 's phone number?
equals(set)
iterator() returns an object used to examine set's contents (seen later) "Marty" "206-685-2181"
removeAll(coll) removes all elements in the given collection from this set Map

retainAll(coll) removes elements not found in given collection from this set
toArray() returns an array of the elements in this set
8 11

8 11

Sets and ordering keySet and values

• HashSet : elements are stored in an unpredictable order • keySet method returns a Set of all keys in the map
Set<String> names = new HashSet<String>(); – can loop over the keys in a foreach loop
[Link]("Jake");
[Link]("Robert"); – can get each key's associated value by calling get on the map
[Link]("Marisa");
[Link]("Kasey"); Map<String, Integer> ages = new TreeMap<String, Integer>();
[Link](names); [Link]("Marty", 19);
// [Kasey, Robert, Jake, Marisa] [Link]("Geneva", 2); // [Link]() returns Set<String>
[Link]("Vicki", 57);
• TreeSet : elements are stored in their "natural" sorted order for (String name : [Link]()) { // Geneva -> 2
int age = [Link](name); // Marty -> 19
Set<String> names = new TreeSet<String>(); [Link](name + " -> " + age); // Vicki -> 57
... }
// [Jake, Kasey, Marisa, Robert]
• values method returns a collection of all values in the map
• LinkedHashSet : elements stored in order of insertion
– can loop over the values in a foreach loop
Set<String> names = new LinkedHashSet<String>();
... – no easy way to get from a value to its associated key(s)
// [Jake, Robert, Marisa, Kasey] 9 12

9 12
 16.03.2026

Problem: opposite mapping Exercises

• It is legal to have a map of sets, a list of lists, etc. • Modify the word count program to print every word that
appeared in the book at least 1000 times, in sorted order from
• Suppose we want to keep track of each TA's GPA by name. least to most occurrences.
Map<String, Double> taGpa = new HashMap<String, Double>();
[Link]("Jared", 3.6);
[Link]("Alyssa", 4.0);
[Link]("Steve", 2.9); • Write a program that reads a list of TA names and quarters'
[Link]("Stef", 3.6); experience, then prints the quarters in increasing order of how
[Link]("Rob", 2.9); many TAs have that much experience, along with their names.
...
[Link]("Jared's GPA is " +
[Link]("Jared")); // 3.6 Allison 5 1 qtr: [Brian]
Alyssa 8 2 qtr: ...
Brian 1 5 qtr: [Allison, Kasey]
• This doesn't let us easily ask which TAs got a given GPA.
Kasey 5
– How would we structure a map for that? ...
13 16

13 16

Reversing a map
• We can reverse the mapping to be from GPAs to names.
Map<Double, String> taGpa = new HashMap<Double, String>();
[Link](3.6, "Jared");

Iterators
[Link](4.0, "Alyssa");
[Link](2.9, "Steve");
[Link](3.6, "Stef");
[Link](2.9, "Rob");
...
[Link]("Who got a 3.6? " +
[Link](3.6)); // ??? reading: 11.1; 15.3; 16.5

• What's wrong with this solution?

– More than one TA can have the same GPA.
– The map will store only the last mapping we add.
14

14 17

Proper map reversal Examining sets and maps

• Really each GPA maps to a collection of people. • elements of Java Sets and Maps can't be accessed by index
Map<Double, Set<String>> taGpa = – must use a "foreach" loop:
new HashMap<Double, Set<String>>();
Set<Integer> scores = new HashSet<Integer>();
[Link](3.6, new TreeSet<String>());
for (int score : scores) {
[Link](3.6).add("Jared");
[Link](4.0, new TreeSet<String>()); [Link]("The score is " + score);
[Link](4.0).add("Alyssa"); }
[Link](2.9, new TreeSet<String>());
[Link](2.9).add("Steve"); – Problem: foreach is read-only;
[Link](3.6).add("Stef"); » cannot modify set while looping
[Link](2.9).add("Rob");
... for (int score : scores) {
[Link]("Who got a 3.6? " + if (score < 60) {
[Link](3.6)); // [Jared, Stef] // throws a ConcurrentModificationException
[Link](score);
– must be careful to initialize the set for a given GPA before adding }
15 } 18

15 18
 16.03.2026

Iterators (11.1) Iterator example 2

Map<String, Integer> scores = new TreeMap<String, Integer>();
• iterator: An object that allows a client to traverse the [Link]("Kim", 38);
elements of any collection. [Link]("Lisa", 94);
[Link]("Roy", 87);
– Remembers a position, and lets you: [Link]("Marty", 43);
• get the element at that position [Link]("Marisa", 72);
...
• advance to the next position
• remove the element at that position Iterator<String> itr = [Link]().iterator();
while ([Link]()) {
String name = [Link]();
index 0 1 2 3 4 5 6 7 8 9 "the" int score = [Link](name);
set [Link](name + " got " + score);
list value 3 8 9 7 5 12 0 0 0 0 "to" "we"
size 6 "from" // eliminate any failing students
if (score < 60) {
[Link](); // removes name and score
current element: 9 current element: "from" }
iterator iterator
current index: 2 next element: "the" }
[Link](scores); // {Lisa=94, Marisa=72, Roy=87}
19 22

19 22

Iterator methods Exercise

hasNext() returns true if there are more elements to examine • Modify the Book Search program from last lecture to eliminate
next() returns the next element from the collection (throws a any words that are plural or all-uppercase from the collection.
NoSuchElementException if there are none left to examine)
remove() removes the last value returned by next() (throws an
IllegalStateException if you haven't called next() yet)
• Modify the TA quarters experience program so that it eliminates
any TAs with 3 quarters or fewer of experience.
• Iterator interface in [Link]
– every collection has an iterator() method that returns an
iterator over its elements

Set<String> set = new HashSet<String>();

...
Iterator<String> itr = [Link]();
...
20 23

20 23

Iterator example Exercise

Set<Integer> scores = new TreeSet<Integer>();
[Link](94); • Write a program to count the occurrences of each word in a
[Link](38); // Kim large text file (e.g. Moby Dick or the King James Bible).
[Link](87);
[Link](43); // Marty
[Link](72); – Allow the user to type a word and report how many times that
... word appeared in the book.
Iterator<Integer> itr = [Link]();
while ([Link]()) {
int score = [Link](); – Report all words that appeared in the book at least 500 times, in
alphabetical order.
[Link]("The score is " + score);

// eliminate any failing grades

if (score < 60) {
[Link](); • How will we store the data to solve this problem?
}
}
[Link](scores); // [72, 87, 94]
21 24

21 24
 16.03.2026

The Map ADT Map methods

• map: Holds a set of unique keys and a collection of values, put(key, value) adds a mapping from the given key to the given value;
if the key already exists, replaces its value with the given one
where each key is associated with one value.
get(key) returns the value mapped to the given key (null if not found)
– a.k.a. "dictionary", "associative array", "hash"
containsKey(key) returns true if the map contains a mapping for the given key

• basic map operations: remove(key) removes any existing mapping for the given key
clear() removes all key/value pairs from the map
– put(key, value ): Adds a
mapping from a key to size() returns the number of key/value pairs in the map
a value. isEmpty() returns true if the map's size is 0
toString() returns a string such as "{a=90, d=60, c=70}"
– get(key ): Retrieves the
value mapped to the key. keySet() returns a set of all keys in the map
– remove(key ): Removes values() returns a collection of all values in the map
the given key and its putAll(map) adds all key/value pairs from the given map to this map
mapped value. equals(map) returns true if given map has the same mappings as this one
[Link]("Juliet") returns "Capulet"
25 28

25 28

Maps and tallying Using maps

• a map can be thought of as generalization of a tallying array • A map allows you to get from one half of a pair to the other.
– the "index" (key) doesn't have to be an int – Remembers one piece of information about every index (key).

• recall previous tallying examples from CSE 142 // key value

put("Marty", "206-685-2181")
– count digits: 22092310907 index 0 1 2 3 4 5 6 7 8 9 Map
value 3 1 3 0 0 0 0 1 0 2

// (M)cCain, (O)bama, (I)ndependent – Later, we can supply only the key and get back the related value:
– count votes: "MOOOOOOMMMMMOOOOOOMOMMIMOMMIMOMMIO" Allows us to ask: What is Marty's phone number?

key "M" "O" "I" "M" 14 get("Marty")

"O" Map
value 16 14 3 3
"206-685-2181"
"I" 16
keys values 26 29

26 29

Map implementation Exercise solution

// read file into a map of [word --> number of occurrences]
• in Java, maps are represented by Map interface in [Link] Map<String, Integer> wordCount = new HashMap<String, Integer>();
Scanner input = new Scanner(new File("[Link]"));
while ([Link]()) {
• Map is implemented by the HashMap and TreeMap classes String word = [Link]();
if ([Link](word)) {
– HashMap: implemented using an array called a "hash table"; // seen this word before; increase count by 1
extremely fast: O(1) ; keys are stored in unpredictable order int count = [Link](word);
[Link](word, count + 1);
– TreeMap: implemented as a linked "binary tree" structure; } else {
very fast: O(log N) ; keys are stored in sorted order // never seen this word before
[Link](word, 1);
}
}
– A map requires 2 type parameters: one for keys, one for values.
Scanner console = new Scanner([Link]);
// maps from String keys to Integer values [Link]("Word to search for? ");
Map<String, Integer> votes = new HashMap<String, Integer>(); String word = [Link]();
[Link]("appears " + [Link](word) + " times.");

27 30

27 30
 16.03.2026

keySet and values Backus-Naur (BNF)

• keySet method returns a set of all keys in the map • Backus-Naur Form (BNF): A syntax for describing language
– can loop over the keys in a foreach loop grammars in terms of transformation rules, of the form:
– can get each key's associated value by calling get on the map
<symbol> ::= <expression> | <expression> ... | <expression>
Map<String, Integer> ages = new HashMap<String, Integer>();
[Link]("Marty", 19);
[Link]("Geneva", 2); – terminal: A fundamental symbol of the language.
[Link]("Vicki", 57); – non-terminal: A high-level symbol describing language syntax,
for (String name : [Link]()) { // Geneva -> 2
int age = [Link](age); name // Marty -> 19 which can be transformed into other non-terminal or terminal
[Link](name + " -> " + age); // Vicki -> 57 symbol(s) based on the rules of the grammar.
}

• values method returns a collection of all values in the map

– can loop over the values in a foreach loop – developed by two Turing-award-winning computer scientists in 1960 to
describe their new ALGOL programming language
– there is no easy way to get from a value to its associated key(s)
31 34

31 34

An example BNF grammar

<s>::=<n> <v>
<n>::=Marty | Victoria | Stuart | Jessica
<v>::=cried | slept | belched

Languages and Grammars • Some sentences that could be generated from this grammar:
Marty slept
Jessica belched
Stuart cried

35

32 35

Languages and grammars BNF grammar version 2

• (formal) language: A set of words or symbols. <s>::=<np> <v>
<np>::=<pn> | <dp> <n>
<pn>::=Marty | Victoria | Stuart | Jessica
• grammar: A description of a language that describes which <dp>::=a | the
sequences of symbols are allowed in that language. <n>::=ball | hamster | carrot | computer
<v>::=cried | slept | belched
– describes language syntax (rules) but not semantics (meaning)
– can be used to generate strings from a language, or to determine
whether a given string belongs to a given language
• Some sentences that could be generated from this grammar:
the carrot cried
Jessica belched
a computer slept

33 36

33 36
 16.03.2026

BNF grammar version 3 Sentence generation

<s>::=<np> <v> <s>
<np>::=<pn> | <dp> <adj> <n>
<pn>::=Marty | Victoria | Stuart | Jessica
<np> <vp>
<dp>::=a | the
<adj>::=silly | invisible | loud | romantic
<n>::=ball | hamster | carrot | computer <pn> <tv> <np>
<v>::=cried | slept | belched

<dp> <adjp> <n>

• Some sentences that could be generated from this grammar: <adj> <adjp>
the invisible carrot cried
Jessica belched <adj>
a computer slept
a romantic ball belched Fred honored the green wonderful child

37 40

37 40

Grammars and recursion

<s>::=<np> <v>
<np>::=<pn> | <dp> <adjp> <n>
<pn>::=Marty | Victoria | Stuart | Jessica
<dp>::=a | the
<adjp>::=<adj> <adjp> | <adj>
<adj>::=silly | invisible | loud | romantic
<n>::=ball | hamster | carrot | computer
<v>::=cried | slept | belched

• Grammar rules can be defined recursively, so that the

expansion of a symbol can contain that same symbol.
– There must also be expressions that expand the symbol into
something non-recursive, so that the recursion eventually ends.

38

38

Grammar, final version

<s>::=<np> <vp>
<np>::=<dp> <adjp> <n>|<pn>
<dp>::=the|a
<adjp>::=<adj>|<adj> <adjp>
<adj>::=big|fat|green|wonderful|faulty|subliminal
<n>::=dog|cat|man|university|father|mother|child
<pn>::=John|Jane|Sally|Spot|Fred|Elmo
<vp>::=<tv> <np>|<iv>
<tv>::=hit|honored|kissed|helped
<iv>::=died|collapsed|laughed|wept

• Could this grammar generate the following sentences?

Fred honored the green wonderful child
big Jane wept the fat man fat

• Generate a random sentence using this grammar. 39

39