CSC 143/Chapter 10

Chapter 10: ArrayLists

Sections:

10.1 ArrayLists

10.2 Comparable interface

10.3 Case study: Vocabulary comparison

Section 10.1: ArrayLists

10.1 Definitions

Definitions:

• Generic class
• Wrapper class
• Boxing
• Unboxing

10.1 Materials

Introduce ArrayList object the way you would introduce the Python list

• List: basic data type, very important
• Difference between list and array - memory allocation and element insertion
• Dynamic arrays

Array notation

• Wrapper class, everything is an object, treat primitive types as objects

What kind of things would you want to do with an ArrayList?

Basic basic operations:

• Get size

Other basic operations:

• Get item at index i
• Set item at index i
• Add item, add item at index i
• Remove item
• Modify item at index i

Now that we have defined these basic operations, we can move on to examples/algorithms/implementations.

Section 10.2: Comparable interface

10.2 Definitions

Definitions:

• Comparison function
• Natural ordering

10.2 Materials

First, need to mention unboxing: ArrayList<Integer> vs ArrayList<int>

• Unboxing is a really stupid side effect of Java's implementation
• Everything is an object. Except the primitive types. But everything is an object.

Comparison of objects

• extend idea behind o1.equals(o2) to comparisons
• lt/lte/gt/gte
• how to redefine comparison operator for our own objects

Section 10.3: Vocabulary comparison

10.3 Material

Some efficiency considerations

Version 1: compute vocabulary

• Add unique words to ArrayList, and sort

Version 2: compute overlap

• Number of matches between two sentences

Version 3: complete program

• so far, build vocab list for 2 files, compute overlap between them
• now, to deal with large files, print statistics (Nwords, Noverlapwords, Percent overlap)

Chapter 10 Summary

Deliverables

ArrayList

• Notation, how to use it
• Conceptualizing problems that can be easily resolved with ArrayList
• Adding/removing and looping over ArrayLists
• Wrapper classes

Comparable

• Natural ordering and compareTo() function
• Implementing the Comparable interface

Case study: Vocab comparison

• Count number of unique words
• Count overlap between two lists
• Compute statistics

Chapter 10 Homework

HW Questions

(Recommended) Self-check problems: #3, #4, #5, #6, #7, #13, #16, #18, #21

(Required) Exercises: #1, #6, #15, #17

(Required) Projects: #2

HW Details

Self-check:

• 3, 4, 5, 6 - string list
• 7 - populating list in a loop
• 13 - syntax
• 16, 18 - mystery
• 21 - comparison

Exercises:

• 1 - average number vowels
• 6 - move item to front
• 15 - filter with int range
• 17 - interleave

Projects:

• 2 - reverse lines and word order in file

Chapter 10 Code

Lecture Code

Removing plural words

• how to index items in a list
• how to add items to a list
• how to remove items from a list

Comparable Point

• implementing comparable interface

Worksheet Code

Euclidian algorithm for GCD

• Walk them through the algorithm
• Show them some examples
• Have them implement it
• Find GCD between terms of a given series

Chapter 10 Goodies

Puzzle 3

Caesar encoded with numbers in blocks of 8

Puzzles/Crypto Level 2/Puzzle 3