CSC 143/Chapter 11

Chapter 11: Java Collections Framework

Sections:

11.1 Lists

11.2 Sets

11.3 Maps

Section 11.1: Lists

11.1 Definitions

Definitions:

• Collection
• Linked list
• Iterator
• Abstract data type

11.1 Material

Collection types:

• Lists
• Sets
• Maps

Types of lists:

• LinkedList versus ArrayList
• List iterators
• Abstract data types (ADTs)

LinkedList case study: Sieve

Section 11.2: Sets

11.2 Definitions

Definitions:

• Set

11.2 Material

Sets

• Mathematical concept, and membership
• TreeSet vs HashSet
• Set operators and set operations

Set example: lottery

Section 11.3: Maps

11.3 Definitions

Definitions:

• Maps

11.3 Material

Maps:

• Functions, mapping one set onto another, math/logic connection
• TreeMap vs HashMap
• Map attributes: keys and values
• Map operations

Map case study: wordcount

Chapter 11 Summary

Deliverables

Must be able to:

• Identify major data types (list, map, set)
• Identify what types of algorithms or applications work best for each data type (problem-solving, conceptual grasp)
• Know difference between tree/hash/linked/array/etc all implementations
• Identify correct/incorrect syntax
• Write pseudocode to deal with iteration and indexing and other
• Conditional logic + data containers = data analysis

(Which of the following best describes a hash map)

(Which of the following best describes a linked list)

Chapter 11 Homework

HW Questions

(Recommended) Self-check problems: #3, #4, #5, #11, #13, #14, #18, #20

(Required) Exercises: #1, #7, #11, #14, #18

(Required) Projects: (none)

HW Details

Self-check:

• 3 - what is an iterator
• 4 - code to count dupes in list
• 5 - insert string into list
• 11 - tree set vs hash set
• 13 - mystery set
• 14 - union and intersection of sets
• 18 - mystery map
• 20 - mystery map

Exercises:

• 1 - improve sieve algorithm
• 7 - count common
• 11 - symmetric diff of 2 sets
• 14 - map intersection
• 18 - reverse map

Projects:

• None

Chapter 11 Code

Lecture Code

List Collection:

• List brief example: Death Star maintenance to-do
• List detailed example: Number sieve

Set Collection:

• Set brief example: Stooges
• Set detailed example: Lottery numbers

Map Collection:

• Map brief example: Death Star salary map
• Map detailed example: Word count for Ulysses

Worksheet Code

Seattle Public School data

• Find the answers to the following questions using lists, maps, or sets.
• X Y Z
• Create dictionary of schools and their distance to school X

Chapter 11 Goodies

Puzzle 4

Nice. Now they have a sieve.

Affine cipher, gcd, Euclid's algorithm

Puzzles/Crypto Level 2/Puzzle 4