Lecture Notes – April 5, 2005

Show and discuss PlayWithText.java

• We’ve been using both StringTokenizer and Scanner to obtain data from a file or from the keyboard.
• By default both classes pick up Strings
• Scanner can pick up numeric values; StringTokenizer requires and addition step to convert picked up value
• StringTokenizer allows you to pick up the delimiter itself. It does not appear that Scanner does.
• A pattern (regular expression) can be used as the delimiters for Scanner. Patterns are enclosed in square brackets [ ] and can be of the form [A-Z] which uses every upper case letter as a delimieter or of the form [A-H, M-Z, 1-3] which uses every one of the values in the three ranges inclusively as delimiters.

Show and discuss TestArrayList.java

Show and discuss TestArrayList2.java

Show and discuss TestArrayList3.java

Material on Sorting and Searching

n Web

n Introduction to Computer Science, chapter 6.4 and 6.5

n Lewis and Loftus 9.4 and 9.5

http://maven.smith.edu/~thiebaut/java/sort/demo.html

http://cg.scs.carleton.ca/~morin/misc/sortalg/

Talk about sorting

Act out sorts

Bubble

Insertion

Selection

Merge

Show and discuss Sorting2.java

Show and discuss Sorting3.java

Talk about Searching

Act out

Linear - list of n items, on average, search looks at n/2 items

Binary - list of n items search looks at log₂n items