CSC 142/Chapter 7

Chapter is particularly large - 1.5 to 2 weeks. Useful for projects &c.

Chapter 7: Arrays

Sections:

7.1 Array basics

7.2 Array traversal algorithms

7.3 Reference semantics

7.4 Advanced array techniques

7.5 Multidimensional arrays

7.6 Case study: Benford's Law

Prior chapter focused on files: sequential in nature, always start search at the beginning

Many algorithms require accessing data multiple times in arbitrary order

Arrays aren't a complicated idea - but the implementation and usage can take some getting used to

Section 7.1: Array Basics

7.1 Definitions

Definitions:

• Array
• Index
• Zero-based indexing
• Auto initialization
• Array traversal
• Sequential access
• Random access

7.1 Material

Constructing arrays:

• Use bracket notation after the type:

int[] temperatures;
String[] names;
boolean[] flags;

Also have to declare a size (either here or later):

int[] temperatures = new int[30];

Can also populate arrays with our own objects:

Color[] colors = new Color[50];

Note that special rules apply with arrays of objects...

How it works:

(Crude drawing)

Temperatures variable refers to pre-allocated array space

Temperatures is not the array itself, it is a reference to the array

Auto-initialization:

• What values do temperatures start with?
• Auto-init starts with the equivalent zero value
• Zero to the computer means,

int - 0
double - 0.0
char - '\0'
bool - false
Objects - null

How to use:

• Replace lots of variables with 1 variable
• temp1, temp2, temp3 --> temperatures
• Replace lots of redundant scanner statements with one for loop:

for( int i=0; i<temperatures.length; i++) {
  temperatures[i] = scanner.nextDouble();
}

Note the difference between length of array and length of string:

• Array: temperatures.length
• String; temperatures.length()

General template/form:

for( int i=0; i < array.length; i++ ) {
  do something at array[i]
}

Accessing arrays:

• Occurs with square bracket and index

  temperatures[5]

• Walk through array creation and population
• Traversal in action:

Algebra and finding elements:

• First element: 0
• Last element: length - 1
• Algebra for accessing middle element of array:
  • If odd: only one middle element, at length / 2 (rounds down)
  • If even: two middle elements, second one is at N/2 (first one is at (N/2)-1)

Doing stuff with array elements:

• Can do anything with

  list[i]

  that you could do with primitive type (incrementing)

Illegal index:

• can create exception if try and access array at < 0 or >= N

Example: Array program

• High temperature of the day
• From set of high Ts, compute an average, and number of days above average temperature
• Breakdown of program:
• Main: ask how many days
• Record Ts, put into array
• Calc average
• Calc number of days above average

Random access

• Many algorithms so far have been sequential access algorithms
• Now talk about random access - possible because of how memory allocated
• Larger lesson: more details means better solutions but more complicated solutions

Arrays and methods:

• Can pass arrays to methods, and methods can modify them
• Here's the thing: don't return arrays from methods
• Diving into low-level implementation details
• What happens when we pass an array into a method?
• We pass in the array
• It is just a reference to a block of values
• Method changes numbers in that block of values
• Variable in calling code, up one scope level, still owns that same pointer to that same memory
• Values have been updated
• No need to return anything

Analogy: Bank accounts and balances

• CC/DC doesn't have actual money on it.. pointer to your account/money.

Special for-each syntax:

for( i : array ) {
}

Initialization shorthand:

• Cumbersome to initialize element-by-element, so can use shorthand notation with brackets:

int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23};

Arrays class:

• Attempts to make arrays easier to use
• Can't change size, but can use other methods
• example copyOf() creates a new copy of array - also called a "deep copy"
• printing arrays: Arrays.toString(primes)
• If you print array directly, you just see the memory addresses
• bank card doesn't tell you how much money you have on your acct, it tells you where to contact the bank and what account information to give them to conduct transactions

Can use equals() to compare arrays

Always use equals() - not ==

Section 7.2: Array Traversal Algorithms

7.2 Material

Two standard array manipulation patterns:

• For each (weird notation)
• Traversal

Printing arrays:

• Can't print directly
• Can use Array.toSTring()
• Can define our own for each loop
• Can print into CSV list using fencepost algorithm

print elem[0]
for i in 1 to length {
  print elem[i]
}

What if array is empty? will raise ArrayIndexOutOfBoundsException

Write your own toString() method, with the fencepost algorithm

Side note:

• How do the students discover what exceptions are raised? EXPERIMENT
• What to do if you want to know more? JAVA API DOCS

Find/replace:

• Counting number of occurrences of element in an array
• Determining where in a list of elements a particular element is located (index of first occurrence)
• Finding index: what happens if we don't find our element?
• Will run into exception: we need to return a value if nothing found
• Java convention: return -1 if nothing found (could also do something like 999999 or 666)

Remember: in a replace method, no return value is needed:

public static void replace() {
  for( i in list.length) {
    if( i is target) {
      list[i] = replacement
    }
  }
}

Testing for equality:

• Comparing objects always more complicated than comparing primitive types

Metaphor: Lamps...

• 2 table lamps: are they equal? (1 lamp, and 1 photo of a lamp)
• In what sense?
• Light emitted? power drawn?
• Appearance and design?
• Cosmic sense? objects composed of the exact same atoms?
• Replicant: different atoms but arranged exactly the same way?
• To check for equality: we must define equality
• To define equality...

Common pattern: to define what equals means, start by defining what NOT EQUALS means

For our case:

• Start by comparing lengths (number of elements should be same) - if different, definitely not equal
• Compare element-by-element - if any elements different, definitely not equal
• Any other conditions needing to be met? Not really - we're done.

Reversing arrays:

• Pattern: going to have to deal with 2 values at a time
• But the system we're playing within says we may only make 1 move at a time
• Can't say, "swap these two values"
• When broken down into one step at a time, info gets clobbered:
• Copy B into A, copy A into B
• Template: temporary variable

Analogy: Board games. Can't lift up a piece, play a round, then place it back down. Can't play a game of chess where both players have pieces off the board (timed competition chess tends to look a little bit like this though).

temp = x;
x = y;
y = temp;

Can define a swap method, that takes an array and two indexes. Must take the array directly:

public static void swap( int[] list, int ix1, int ix2 ) {
  ...
}

Further work on reverse algorithm:

• Let's think through ENTIRE algorithm
• If you implement the algorithm, it will go through ENTIRE array
• But when we get halfway through the array, we've swaped two elements at a time, so (half the space) * (double the operations) = 100% done.
• However, then we keep going through the second half, and reverse all of our changes. (second half of the space) * (double the operations) = 100% reversed.
• Test to implement: cut-in-half loop.

Strategy: does it work on a 3-element array? a 5-element array? a 6-element array?

String traversal algorithms:

• Strings can be thought of as char arrays
• Can utilize traversal algorithm with string:

for( int i = 0; i < length; i++ ) {
  do something with array[i]
}

Counting number of characters in a string

Reversing string

Section 7.3: Reference Semantics

7.3 Definitions

Definitions:

• Value types
• Reference types

7.3 Material

Have covered concept of values vs. reference

• Objects are references to data, not the data itself
• Why reference vs. value types?
• Objects can be very large
• Shared resources
• When in doubt - just imagine your object is a database storing 10 GB of data, which is specific to each instance of the object
• If Java had its way, there would be NO PRIMITIVE TYPES (yikes)

Multiple objects:

• An object is defined by code: it defines the different pieces of data and instructions associated with that object
• We have to be specfic when we say, give me a new object
• Example:

int[] list1 = new int[5];
int[] list2 = new int[5];

... populate list1 and list2....

int[] list3 = list2;

There is ambiguity here in the = sign: deep copy, or shallow copy?

• Convention with objects: shallow copy
• Duplicate reference, to same original data
• If you change data in list2, you will see those changes reflected in list3
• also affects the == operator:
• If two objects have same length, and same data, dos not mean they are equal: remember that "cosmic oneness", composed of same atoms, or different atoms but exact same arrangement? Here we go:

list1 -----\
                |-------> [_0_] [_1_] [_2_] [_3_] [_4_]
list2 -----/

vs.
list1 -----> [_0_] [_1_] [_2_] [_3_] [_4_]
list2 -----> [_0_] [_1_] [_2_] [_3_] [_4_]

• Using = operator checks address of array
• Using Arrays.equals() checks values of array

methods:

• Saw earlier that we can pass arrays into methods
• Arrays are passed by reference (hence, no return needed)

public static void main(String[] args) {
  int[] list = {1,2,3,4};
  increment(list);
}

public static void increment( int[] data ) {
  for( i in data.length ) {
    data[i]++
  }
}

Data and list point to the same data

Key message: when we pass array as a parameter to a method, method has ability to change array contents (directly)

Null:

• Can initialize objects to null value
• Example: Point object (x,y,z)
• Null means, x/y/z don't have values
• Does not mean, x=0, y=0, z=0

Section 7.4: Advanced Array Techniques

7.4 Material

Beyond simple traversal algorithms

Shifting values:

• Again: lifting pieces off the board, have to put them somewhere
• Put first value in a temporary variable
• Shift everything to the left by one
• Then put it in the last element

Approach:

• Write out explicitly, then translate into index ops

list[0] = list[1];
list[1] = list[2];

list[i] = list[i+1];

Indexing:

• Not quite 0 to len()-1
• Leads to off-by-one error
• Want to skip first element
• Store first
• Loop thru array, 1 to len-1, shifting
• Assign last to first
• ALT: rotate to right, not left... but be careful, this overwrites if you do it in the wrong direction!

Loop ordre (last-to-first or first-to-last) dictates assignment order (shift L, or shift R)

Array of Objects:

• Arrays of objects behave differently from arrays of primitive types
• Objects are stored as references, not as the object itself

List of points: the list points to allocated memory

But the allocated memory itself points to other allocated memory

So, let's walk through the 2 steps required here:

1. Create a list of points: that is, allocate space for an array ,with each element referring to a Point object

Point[] list = new Point[5];

2. Initialize the Point objects (they are initialized as NULL, not as (0,0,0))

Differentiate between zero to machine and zero within our system

Can initialize elemnt-by-element, or in loop, or in curly brackets

Command line arguments:

• Now we can finally revisit (and understand) the public static void main(String[] args) stuff
• String array args: command line arguments
• java Stuff val1 val2
• Now arguments array refers to

  args --> [ arg1 ][ arg2 ]

Nested loop algorithms:

• Inversion: a pair of numbers in hich the first number in the list is greater than the second number in the list

[1,2,3,4] --> no inversions

[3,1,4,2] --> (3,1), (3,2), (4,2)

[4,2,3,1] --> (4,3), (4,2), (4,1), (3,2), (3,1), (2,1)

We can't solve this with one traversal - we need two items to make an inversion

Use pseudocode to tacklet he problem

• NOTE: Pseudocode is the approach to use when you have to translate a fuzzy concept-idea-pattern into actual one-at-a-time tasks
• For every possible first value, check all remaining possible second values, and store any that are inversions

for( every poss 1st val) {
  print all poss inversions
}

Expanding:

for( every poss 1st val) {
  for( every poss 2nd val) {
    if( data[i] data[j]) {
      println()
    }
  }
}

But, we need an offset:

i = 0; i < data.length - 1; i++)
(j = i+1; j < data.length; j++ )

Section 7.5: Multidimensional Arrays

7.5 Material

Prior section only looking at 1D arrays

2D arrays useful: rows/columns, spreadsheets-Java bridge, matrices, multi-dimensional data

double - one double
double[] - 1D array of doubles
double[][] - 2D array of doubles
double[][][] - 3D array of doubles
etc.

Rectangular 2D array:

• Notation

double[][] temps = new double[8][10]

• Primitive type, init 0
• To print: if you pass it temps, it goes 1 level deep, prints addresses of the 8 arrays (10 elements each)
• to correct:
• Arrays.deepToString(temps)

Jagged arrays:

• Rectangular useful for some problems, jagged more useful for others
• Refer back to the hours worked example - rather than reading data directly out of the file, and processing it as we go, perhaps we want to store that data in an array so we can do more complicated calculations
• Each person works different number of hours, different number of days
• To initialize: don't specify second dimension

int[][] jag = new int[5][];

jag[0] = new int[2];
jag[1] = new int[4];
jag[2] = new int[3];

Pascal's Triangle example:

• Background about (x+y)^n and binomial theorem
• Coefficients for polynomials from Pascal's Triangle
• Each row comes from prior row
• Results for n = 0 to n = 4

PascalsTriangle.java

main() {
  int[][] triangle = new int[11][]; // 11 rows
  fillTriangle( triangle );
  print(triangle);
}
fillin() {
  for (triangle.length) {
    init triangle[i] (size i+1)
    triangle[i][0] = 1
    triangle[i][i] = 1
    for( j = 1 to i ) {
      [i][j] = (i-1)(j-1) + (i-1)(j)
    }
  }
}
print() { 
  for( i in triangle.length ) { 
    for( j in traingle[i].length ) {
      println( triangle[i][j] )
    }
  }
}

Section 7.6: Benford's Law

7.6 Material

Background:

• Properties of exponential vs linear series,
• Frequency of coccurrences of 1s, 2s, higher in exp infinite series than in linear infinite series
• Example
• Program goal: read a file of digits, determine what the distribution of digits looks like

Tallying values:

• Count number of occurrences of a particular value
• Arrangement: A B C D E F G
• Vector: [0,0,0,0,0,0,0]

Tally class:

• Main method:
• Input file scanner
• New array
• While nextInt() from scanner:
• nextInt()
• count[next]++
• Value occurrences: System.out.println

Completing program:

• Assume: INPUT FILE OF INTEGERS
• Deal with negative numbers
• Identical code to prior section

count[ firstDigit(n) ]++;

Only tallying first digits of numbers

Chapter 7 Summary

Deliverables

Array basics:

• Syntax, how arrays work, calling arrays, declaring arrays, allocating space, initializing
• Initialization methods: for loop, empty, or brackets {} and the diff. between them
• Accessing arrays and index algebra - how to reference middle element? second-to-last element?
• Random access (arrays) vs sequential access (files)
• Arrays as method arguments, modification of memory drectly
• References (with object concept) - bank analogy (debit card versus actual numbers)

Traversal algorithms:

• For each pattern/notation (weird)
• Traversal: for( i=0; i<list.length() i++)
• Printing arrays (requires traversing; CSU requires fencepost algorithm)
• Array out of bounds exception
• Finding and replacing
• Defining equality checks (2 lamps)
• Reversing arrays, temp var, shift
• Board game analogy: have to place each piece back on the board before moving next one
• Applications to strings: string traversal, string reversal, string char-counting, string shuffling, etc.

Reference semantics:

• Value vs reference
• How objects are stored in memory
• How arrays of objects are stored in memory (versus primitive data)
• Shallow vs deep copy
• Equality and references == or .equals()? always .equals()
• Passing arrays to methods
• Null objects

Advanced array techniques:

• Beyond simple traversal
• Shifting array by 1 (left/right, front/back) shifts
• Arrays of objects and initialization and reference
• String[] args and command line arguments
• Nested loop lgorithms and mulitple traversals

Multidimensional arrays:

• Rectangular 2D arrays (notation)
• Printing 2D array
• Jagged 2D arrays (notation) (initialization)
• Pascal's Triangle example

Case study: Bedford's Law, examining entropy in 1st digit in a file of integers

Chapter 7 Code

Lecture Code

Rectangular arrays:

• Find gcd of random integers, 1 < x <= 100
• Generate 5 pairs of integers, using Random(1,100)
• Find the gcd of the two numbers, store in third column

Jagged arrays

• Finding all common factors
• Use gcd as starting point, work your way down

Worksheet Code

Arrays worksheet: ???

Challenge problem:

Assume you have a method isSubstring which checks if one word is a substring of another.

Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only ONE call to isSubstring.

Example: "waterbottle" is a rotation of "erbottlewat"

Chapter 7 Homework

HW Questions

(Recommended) Self-check problems:

(Required) Exercises:

(Required) Projects:

HW Details

Self-check:

Exercises:

Projects:

Chapter 7 Goodies

Puzzle 7

OTP - modular arithmetic, chunks of data, first line of novels as OTP keys.