Array Assignmen (Java Programming)

betoglan2017

CS.3.Arrays.pdf

Home >Computer Science homework help >Array Assignmen (Java Programming)

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

h t t p : / / i n t r o c s . c s . p r i n c e t o n . e d u

R O B E R T S E D G E W I C K K E V I N W A Y N E

C om

pu ter Scien

Computer Science

An Interdisciplinary Approach

3. Arrays

1.4

3. Arrays

• Basic concepts • Typical array-processing code • Two-dimensional arrays

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

CS.3.A.Arrays.Basics

Basic building blocks for programming

any program you might want to write

objects

functions and modules

arrays

conditionals and loops

Math text I/O

assignment statementsprimitive data types

graphics, sound, and image I/O

Ability to store and process huge amounts of data

arrays

Your first data structure

Main purpose. Facilitate storage and manipulation of data.

Examples.

• 52 playing cards in a deck.

• 100 thousand students in an online class.

• 1 billion pixels in a digital image.

• 4 billion nucleotides in a DNA strand.

• 73 billion Google queries per year.

• 86 billion neurons in the brain.

• 50 trillion cells in the human body.

• 6.02 × 1023 particles in a mole.

A data structure is an arrangement of data that enables efficient processing by a program.

index value

0 2♥

1 6♠

2 A♦

3 A♥

...

49 3♣

50 K♣

51 4♠

An array is an indexed sequence of values of the same type.

Processing many values of the same type

double a0 = 0.0; double a1 = 0.0; double a2 = 0.0; double a3 = 0.0; double a4 = 0.0; double a5 = 0.0; double a6 = 0.0; double a7 = 0.0; double a8 = 0.0; double a9 = 0.0; ... a4 = 3.0; ... a8 = 8.0; ... double x = a4 + a8;

10 values, without arrays

tedious and error-prone code

double[] a; a = new double[10]; ... a[4] = 3.0; ... a[8] = 8.0; ... double x = a[4] + a[8];

10 values, with an array

an easy alternative

double[] a; a = new double[1000000]; ... a[234567] = 3.0; ... a[876543] = 8.0; ... double x = a[234567] + a[876543];

1 million values, with an array

scales to handle huge amounts of data

Memory representation of an array

A computer's memory is also an indexed sequence of memory locations.

• Each primitive type value occupies a fixed number of locations.

• Array values are stored in contiguous locations.

An array is an indexed sequence of values of the same type.

a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]

Critical concepts

• Indices start at 0.

• Given i, the operation of accessing the value a[i] is extremely efficient.

• The assignment b = a makes the names b and a refer to the same array.

stay tuned for many details

it does not copy the array, as with primitive types (stay tuned for details)

a for simplicity in this lecture, think of a as the memory address of the first location the actual implementation in Java is just slightly more complicated.

Java language support for arrays

operation typical code

Declare an array double[] a;

Create an array of a given length a = new double[1000];

Refer to an array entry by index a[i] = b[j] + c[k];

Refer to the length of an array a.length;

Basic support

operation typical code

Default initialization to 0 for numeric types a = new double[1000];

Declare, create and initialize in one statement double[] a = new double[1000];

Initialize to literal values double[] x = { 0.3, 0.6, 0.1 };

Initialization options

BUT cost of creating an array is proportional to

its length.

no need to use a loop like for (int i = 0; i < 1000; i++) a[i] = 0.0;

Copying an array

To copy an array, create a new array , then copy all the values.

0.3 0.6 0.99 0.01 0.5

double[] b = new double[a.length]; for (int i = 0; i < a.length; i++) b[i] = a[i];

i i

Important note: The code b = a does not copy an array (it makes b and a refer to the same array).

0.3 0.6 0.99 0.01 0.5

double[] b = new double[a.length]; b = a;

Programming with arrays: typical examples

double[] a = new double[N]; for (int i = 0; i < N; i++) a[i] = Math.random();

Create an array with N random values

for (int i = 0; i < N; i++) System.out.println(a[i]);

Print array values, one per line

double sum = 0.0; for (int i = 0; i < N; i++) sum += a[i]; double average = sum / N;

Compute the average of array values

double max = a[0]; for (int i = 1; i < N; i++) if (a[i] > max) max = a[i];

Find the maximum of array values

double[] b = new double[N]; for (int i = 0; i < N; i++) b[i] = a[i];

Copy to another array

For brevity, N is a.length and b.length in all this code.

int stake = Integer.parseInt(args[0]); int goal = Integer.parseInt(args[1]); int trials = Integer.parseInt(args[2]);

Access command-line args in system array

Pop quiz 1 on arrays

Q. What does the following code print?

public class PQarray1 { public static void main(String[] args) { int[] a = new int[6]; int[] b = new int[a.length];

b = a; for (int i = 1; i < b.length; i++) b[i] = i;

for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println();

for (int i = 0; i < b.length; i++) System.out.print(b[i] + " "); System.out.println(); } }

Pop quiz 1 on arrays

Q. What does the following code print?

public class PQarray1 { public static void main(String[] args) { int[] a = new int[6]; int[] b = new int[a.length];

b = a; for (int i = 1; i < b.length; i++) b[i] = i;

for (int i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println();

for (int i = 0; i < b.length; i++) System.out.print(b[i] + " "); System.out.println(); } }

A. % java PQ4_1 0 1 2 3 4 5

0 1 2 3 4 5

After this, b and a refer to the same array

Programming with arrays: typical bugs

a = new double[10]; for (int i = 0; i < 10; i++) a[i] = Math.random();

What type of data does a refer to?

Undeclared variable

double[] a; for (int i = 0; i < 9; i++) a[i] = Math.random();

Never created the array

Uninitialized array

double[] a = new double[10]; for (int i = 1; i <= 10; i++) a[i] = Math.random();

No a[10] (and a[0] unused)

Array index out of bounds

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

Image sources

http://commons.wikimedia.org/wiki/File:CERN_Server_03.jpg

CS.3.A.Arrays.Basics

3. Arrays

• Basic concepts • Examples of array-processing code • Two-dimensional arrays

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

CS.3.B.Arrays.Examples

Example of array use: create a deck of cards

Define three arrays

• Ranks.

• Suits.

• Full deck.

Use nested for loops to put all the cards in the deck.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ...

2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ Q♣ K♣ A♣ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ ...

String[] deck = new String[52];

deck

String[] suit = { "♣", "♦", "♥", "♠" };

0 1 2 3

♣ ♦ ♥ ♠suit

String[] rank = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A" };

0 1 2 3 4 5 6 7 8 9 10 11 12

2 3 4 5 6 7 8 9 10 J Q K Arank

for (int j = 0; j < 4; j++) for (int i = 0; i < 13; i++) deck[i + 13*j] = rank[i] + suit[j];

better style to use rank.length and suit.length clearer in lecture to use 4 and 13

Example of array use: create a deck of cards

public class Deck { public static void main(String[] args) { String[] rank = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A" }; String[] suit = { "♣", "♦", "♥", "♠" };

String[] deck = new String[52]; for (int j = 0; j < 4; j++) for (int i = 0; i < 13; i++) deck[i + 13*j] = rank[i] + suit[j];

for (int i = 0; i < 52; i++) System.out.print(deck[i] + " "); System.out.println(); } }

% java Deck

2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣ Q♣ K♣ A♣ 2♦ 3♦ 4♦ 5♦ 6♦ 7♦ 8♦ 9♦ 10♦ J♦ Q♦ K♦ A♦ 2♥ 3♥ 4♥ 5♥ 6♥ 7♥ 8♥ 9♥ 10♥ J♥ Q♥ K♥ A♥ 2♠ 3♠ 4♠ 5♠ 6♠ 7♠ 8♠ 9♠ 10♠ J♠ Q♠ K♠ A♠ %

no color in Unicode; artistic license for lecture

Pop quiz 2 on arrays

Q. What happens if the order of the for loops in Deck is switched?

for (int j = 0; j < 4; j++) for (int i = 0; i < 13; i++) deck[i + 13*j] = rank[i] + suit[j];

for (int i = 0; i < 13; i++) for (int j = 0; j < 4; j++) deck[i + 13*j] = rank[i] + suit[j];

Pop quiz 2 on arrays

Q. What happens if the order of the for loops in Deck is switched?

for (int j = 0; j < 4; j++) for (int i = 0; i < 13; i++) deck[i + 13*j] = rank[i] + suit[j];

for (int i = 0; i < 13; i++) for (int j = 0; j < 4; j++) deck[i + 13*j] = rank[i] + suit[j];

A. The array is filled in a different order, but the output is the same.

NOTE: Error on page 92 in 3rd printing of text (see errata list on booksite).

0 1 2 ... 12 13 14 15 ... 25 26 27 28 ... 38 39 40 41 ... 51

0 1 2 3

♣ ♦ ♥ ♠suit

0 1 2 3 4 5 6 7 8 9 10 11 12

2 3 4 5 6 7 8 9 10 J Q K Arank

deck 2♣ 3♣ 4♣ ... A♣ 2♦ 3♦ 4♦ ... A♦ 2♥ 3♥ 4♥ ... A♥ 2♠ 3♠ 4♠ ... A♠

Pop quiz 3 on arrays

Q. Change Deck to put the cards in rank order in the array.

% java Deck

2♣ 2♦ 2♥ 2♠ 3♣ 3♦ 3♥ 3♠ 4♣ 4♦ 4♥ 4♠ 5♣ 5♦ 5♥ 5♠ 6♣ 6♦ 6♥ 6♠ 7♣ 7♦ 7♥ 7♠ 8♣ 8♦ 8♥ 8♠ 9♣ 9♦ 9♥ 9♠ 10♣ 10♦ 10♥ 10♠ J♣ J♦ J♥ J♠ Q♣ Q♦ Q♥ Q♠ K♣ K♦ K♥ K♠ A♣ A♦ A♥ A♠ %

Pop quiz 3 on arrays

Q. Change Deck to put the cards in rank order in the array.

for (int i = 0; i < 13; i++) for (int j = 0; j < 4; j++) deck[4*i + j] = rank[i] + suit[j];

% java Deck

0 1 2 3 4 5 6 7 8 9 10 11 12 ...

2♣ 2♦ 2♥ 2♠ 3♣ 3♦ 3♥ 3♠ 4♣ 4♦ 4♥ 4♠ 5♣ ...

0 1 2 3

♣ ♦ ♥ ♠suit

0 1 2 3 4 5 6 7 8 9 10 11 12

2 3 4 5 6 7 8 9 10 J Q K Arank

deck

Array application: take a card, any card

Problem: Print a random sequence of N cards.

for (int i = 0; i < N; i++) { int r = (int) (Math.random() * 52); System.out.println(deck[r]); }

Algorithm Take N from the command line and do the following N times

• Calculate a random index r between 0 and 51.

• Print deck[r].

Implementation: Add this code instead of printing deck in Deck.

Note: Same method is effective for printing a random sequence from any data collection.

each value between 0 and 51 equally likely

Array application: random sequence of cards

public class DrawCards { public static void main(String[] args) { int N = Integer.parseInt(args[0]);

String[] rank = {"2", "3", "4", "5", "6", "7", "8", "9","10", "J", "Q", "K", "A" }; String[] suit = { "♣", "♦", "♥", "♠" };

String[] deck = new String[52]; for (int i = 0; i < 13; i++) for (int j = 0; j < 4; j++) deck[i + 13*j] = rank[i] + suit[j];

for (int i = 0; i < N; i++) { int r = (int) (Math.random() * 52); System.out.print(deck[r] + " "); } System.out.println(); } }

% java DrawCards 10

6♥ K♦ 10♠ 8♦ 9♦ 9♥ 6♦ 10♠ 3♣ 5♦

% java DrawCards 10

2♦ A♠ 5♣ A♣ 10♣ Q♦ K♣ K♠ A♣ A♦

% java DrawCards 10

6♠ 10♦ 4♥ A♣ K♥ Q♠ K♠ 7♣ 5♦ Q♠

% java DrawCards 10

A♣ J♣ 5♥ K♥ Q♣ 5♥ 9♦ 9♣ 6♠ K♥

Note: Sample is with replacement (same card can appear multiple times). appears twice

Array application: shuffle and deal from a deck of cards

Problem: Print N random cards from a deck.

Algorithm: Shuffle the deck, then deal.

• Consider each card index i from 0 to 51.

• Calculate a random index r between i and 51.

• Exchange deck[i] with deck[r] • Print the first N cards in the deck.

for (int i = 0; i < 52; i++) { int r = i + (int) (Math.random() * (52-i)); String t = deck[r]; deck[r] = deck[i]; deck[i] = t; } for (int i = 0; i < N; i++) System.out.print(deck[i]); System.out.println();

Implementation each value

between i and 51 equally likely

Array application: shuffle a deck of 10 cards (trace)

for (int i = 0; i < 10; i++) { int r = i + (int) (Math.random() * (10-i)); String t = deck[r]; deck[r] = deck[i]; deck[i] = t; }

i r deck

0 1 2 3 4 5 6 7 8 9

2♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 9♣ 10♣ J♣

0 7 9♣ 3♣ 4♣ 5♣ 6♣ 7♣ 8♣ 2♣ 10♣ J♣

1 3 9♣ 5♣ 4♣ 3♣ 6♣ 7♣ 8♣ 2♣ 10♣ J♣

2 9 9♣ 5♣ J♣ 3♣ 6♣ 7♣ 8♣ 2♣ 10♣ 4♣

3 9 9♣ 5♣ J♣ 4♣ 6♣ 7♣ 8♣ 2♣ 10♣ 3♣

4 6 9♣ 5♣ J♣ 4♣ 8♣ 7♣ 6♣ 2♣ 10♣ 3♣

5 9 9♣ 5♣ J♣ 4♣ 8♣ 3♣ 6♣ 2♣ 10♣ 7♣

6 8 9♣ 5♣ J♣ 4♣ 8♣ 3♣ 10♣ 2♣ 6♣ 7♣

7 9 9♣ 5♣ J♣ 4♣ 8♣ 3♣ 10♣ 7♣ 6♣ 2♣

8 8 9♣ 5♣ J♣ 4♣ 8♣ 3♣ 10♣ 7♣ 6♣ 2♣

9 9 9♣ 5♣ J♣ 4♣ 8♣ 3♣ 10♣ 7♣ 6♣ 2♣

Q. Why does this method work?

• Uses only exchanges, so the deck after  the shuffle has the same cards as before.

• N −i equally likely values for deck[i].

• Therefore N ×(N −1)×(N −1)... ×2×1 = N !  equally likely values for deck[].

Initial order is immaterial.

Note: Same method is effective for randomly rearranging any type of data.

Array application: shuffle and deal from a deck of cards

public class DealCards { public static void main(String[] args) { int N = Integer.parseInt(args[0]);

String[] rank = {"2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A" }; String[] suit = { "♣", "♦", "♥", "♠" };

String[] deck = new String[52]; for (int i = 0; i < 13; i++) for (int j = 0; j < 4; j++) deck[i + 13*j] = rank[i] + suit[j];

for (int i = 0; i < 52; i++) { int r = i + (int) (Math.random() * (52-i)); String t = deck[r]; deck[r] = deck[i]; deck[i] = t; }

for (int i = 0; i < N; i++) System.out.print(deck[i]); System.out.println(); } }

% java DealCards 5 9♣ Q♥ 6♥ 4♦ 2♠

random poker hand

% java DealCards 13 3♠ 4♥ 10♦ 6♥ 6♦ 2♠ 9♣ 8♠ A♠ 3♥ 9♠ 5♠ Q♥

random bridge hand

Coupon collector

9♣ 5♠ 8♥ 10♦ 2♠ A♠ 10♥ Q♦ 3♠ 9♥ 5♦ 9♣ 7♦ 2♦ 8♣ 6♣ Q♥ K♣ 10♥ A♦ 4♦ J♥

2♠ 3♠ 4♦ 5♠ 6♣ 7♦ 8♥ 9♣ 10♦ J♥ Q♦ K♣ A♠

10♥9♥5♦

9♣

2♦ 8♣ Q♥

10♥

A♦

2 3 4 5 6 7 8 9 10 J Q K A

Example: Collect all ranks in a random sequence of cards (M =

Collection

Sequence

22 cards needed to complete collection

Coupon collector problem

• M different types of coupons.

• Collector acquires random coupons, one at a time, each type equally likely. Q. What is the expected number of coupons needed to acquire a full collection?

Array application: coupon collector

public class Coupon { public static void main(String[] args) { int M = Integer.parseInt(args[0]); int cards = 0; // number of cards collected int distinct = 0; // number of distinct cards boolean[] found = new boolean[M]; while (distinct < M) { int r = (int) (Math.random() * M); cards++; if (!found[r]) { distinct++; found[r] = true; } }

System.out.println(cards); } }

Key to the implementation

• Create a boolean array of length M. (Initially all false by default.)

• When r generated, check the r th value in the array.

• If true, ignore it (not new).

• If false, count it as new distinct  value (and set r th entry to true)

% java Coupon 13 46

% java Coupon 13 22

% java Coupon 13 54

% java Coupon 13 27

Coupon collector simulation

• Generate random int values between 0 and M −1.

• Count number used to generate each value at least once.

Array application: coupon collector (trace for M = 6)

boolean[] found = new boolean[M]; while (distinct < M) { int r = (int) (Math.random() * M); cards++; if (!found[r]) { distinct++; found[r] = true; } }

r found

distinct cards 0 1 2 3 4 5

F F F F F F 0 0

2 F F T F F F 1 1

0 T F T F F F 2 2

4 T F T F T F 3 3

0 T F T F T F 3 4

1 T T T F T F 4 5

2 T T T F T F 4 6

5 T T T F T T 5 7

0 T T T F T T 5 8

1 T T T F T T 5 9

3 T T T T T T 6 10

Simulation, randomness, and analysis (revisited)

Pierre-Simon Laplace 1749-1827

Remarks

• Computer simulation can help validate mathematical analysis.

• Computer simulation can also validate software behavior.

Coupon collector problem

• M different types of coupons.

• Collector acquires random coupons, one at a time, each type equally likely. Q. What is the expected number of coupons needed to acquire a full collection?

% java Coupon 4 11

% java Coupon 13 38

% java Coupon 1200 8789

% java Coupon 12534 125671

type M expected wait

playing card suits 4 8

playing card ranks 13 41

baseball cards 1200 9201

Magic™ cards 12534 125508

Example: Is Math.random() simulating randomness?

A. (known via mathematical analysis for centuries) About M ln M + .57721M .

Simulation, randomness, and analysis (revisited)

public class Gambler { public static void main(String[] args) { int stake = Integer.parseInt(args[0]); int goal = Integer.parseInt(args[1]); int trials = Integer.parseInt(args[2]); int wins = 0; for (int i = 0; i < trials; i++) { int t = stake; while (t > 0 && t < goal) { if (Math.random() < 0.5) t++; else t--; } if (t == goal) wins++; } System.out.println(wins + " wins of " + trials); } }

Gambler's ruin simulation, previous lecture public class CouponCollector { public static void main(String[] args) { int M = Integer.parseInt(args[0]); int trials = Integer.parseInt(args[1]); int cards = 0; boolean[] found;

for (int i = 0; i < trials; i++) { int distinct = 0; found = new boolean[M]; while (distinct < M) { int r = (int) (Math.random() * M); cards++; if (!found[r]) { distinct++; found[r] = true; } } } System.out.println(cards/trials); } }

Analogous code for coupon collector, this lecture

Once simulation is debugged, experimental evidence is easy to obtain.

Simulation, randomness, and analysis (revisited)

% java CouponCollector 4 1000000 8

% java CouponCollector 13 1000000 41

% java CouponCollector 52 100000 236

% java CouponCollector 1200 10000 9176

% java CouponCollector 12534 1000 125920

type M M ln M + .57721M

playing card suits 4 8

playing card ranks 13 41

playing cards 52 236

baseball cards 1200 9201

magic cards 12534 125508

Predicted by mathematical analysis Observed by computer simulation

and Math.random() simulates randomness.Hypothesis. Centuries-old analysis is correct

Coupon collector problem

• M different types of coupons.

• Collector acquires random coupons, one at a time, each type equally likely. Q. What is the expected number of coupons needed to acquire a full collection?

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

Image sources

http://www.vis.gr.jp/~nazoya/cgi-bin/catalog/img/CARDSBIC809_red.jpg

http://www.alegriphotos.com/Shuffling_cards_in_casino-photo-deae1081e5ebc6631d6871f8b320b808.html

http://iveypoker.com/wp-content/uploads/2013/09/Dealing.jpg

http://upload.wikimedia.org/wikipedia/commons/b/bf/Pierre-Simon,_marquis_de_Laplace_(1745-1827)_-_Guérin.jpg

CS.3.B.Arrays.Examples

3. Arrays

• Basic concepts • Examples of array-processing code • Two-dimensional arrays

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

CS.3.C.Arrays.2D

Two-dimensional arrays

Main purpose. Facilitate storage and manipulation of data.

Examples

• Matrices in math calculations.

• Grades for students in an online class.

• Outcomes of scientific experiments.

• Transactions for bank customers.

• Pixels in a digital image.

• Geographic data

• ...

0 1 2 3 4 5 ...

0 A A C B A C

1 B B B B A A

2 C D D B C A

3 A A A A A A

4 C C B C B B

5 A A A B A A

...

grade

st u d en

t ID

x-coordinate

y- co

o rd

in a te

A two-dimensional array is a doubly-indexed sequence of values of the same type.

Java language support for two-dimensional arrays (basic support)

operation typical code

Declare a two-dimensional array double[][] a;

Create a two-dimensional array of a given length a = new double[1000][1000];

Refer to an array entry by index a[i][j] = b[i][j] * c[j][k];

Refer to the number of rows a.length;

Refer to the number of columns a[i].length;

Refer to row i a[i]

can be different for each row

a[][]

a[1]

a[0][0] a[0][1] a[0][2] a[0][3] a[0][4] a[0][5] a[0][6] a[0][7] a[0][8] a[0][9]

a[1][0] a[1][1] a[1][2] a[1][3] a[1][4] a[1][5] a[1][6] a[1][7] a[1][8] a[1][9]

a[2][0] a[2][1] a[2][2] a[2][3] a[2][4] a[2][5] a[2][6] a[2][7] a[2][8] a[2][9]

no way to refer to column j

a 3-by-10 array

Java language support for two-dimensional arrays (initialization)

operation typical code

Default initialization to 0  for numeric types

a = new double[1000][1000];

Declare, create and initialize   in a single statement

double[][] a = new double[1000][1000];

Initialize to literal values

double[][] p = { { .92, .02, .02, .02, .02 }, { .02, .92, .32, .32, .32 }, { .02, .02, .02, .92, .02 }, { .92, .02, .02, .02, .02 }, { .47, .02, .47, .02, .02 }, };

BUT cost of creating an array is proportional to

its size.

no need to use nested loops like for (int i = 0; i < 1000; i++) for (int j = 0; j < 1000; j++) a[i][j] = 0.0;

Application of arrays: vector and matrix calculations

Mathematical abstraction: matrix Java implementation: 2D array

Vector addition

double[] c = new double[N]; for (int i = 0; i < N; i++) c[i] = a[i] + b[i];

Matrix addition

double[][] c = new double[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) c[i][j] = a[i][j] + b[i][j];

.70 .20 .10

.30 .60 .10

.50 .10 .40

.80 .30 .50

.10 .40 .10

.10 .30 .40

1.5 .50 .60

.40 1.0 .20

.60 .40 .80

+ =.30 .60 .10 + =.50 .10 .40 .80 .70 .50

Mathematical abstraction: vector Java implementation: 1D array

Application of arrays: vector and matrix calculations

Mathematical abstraction: matrix Java implementation: 2D array

.70 .20 .10

.30 .60 .10

.50 .10 .40

.80 .30 .50

.10 .40 .10

.10 .30 .40

.59 .32 .41

.31 .36 .25

.45 .31 .42 * =

.30 .60 .10 .25· =.50 .10 .40

Vector dot product

double sum = 0.0; for (int i = 0; i < N; i++) sum += a[i]*b[i];

Matrix multiplication

double[][] c = new double[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) c[i][j] += a[i][k] * b[k][j];

i x[i] y[i] x[i]*y[i] sum

0 0.3 0.5 0.15 0.15

1 0.6 0.1 0.06 0.21

2 0.1 0.4 0.04 0.25

end-of-loop trace

Mathematical abstraction: vector Java implementation: 1D array

Pop quiz 4 on arrays

Q. How many multiplications to multiply two N-by-N matrices?

1. N

2. N 2

3. N 3

4. N 4

double[][] c = new double[N][N];

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

for (int k = 0; k < N; k++)

c[i][j] += a[i][k] * b[k][j];

1. N

2. N 2

3. N 3

4. N 4

Pop quiz 4 on arrays

Q. How many multiplications to multiply two N-by-N matrices?

double[][] c = new double[N][N];

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++)

for (int k = 0; k < N; k++)

c[i][j] += a[i][k] * b[k][j];

Nested for loops: N × N × N

Self-avoiding random walks

Approach: Use Monte Carlo simulation, recording visited positions in an N-by-N array.

Q. What are the chances of reaching a dead end? dead end

escape Model: a random process in an N-by-N lattice • Start in the middle. • Move to a random neighboring intersection  

but do not revisit any intersection. • Outcome 1 (escape): reach edge of lattice. • Outcome 2 (dead end): no unvisited neighbors.

A dog walks around at random in a city, never revisiting any intersection.

Q. Does the dog escape?

Self-avoiding random walks

Application of 2D arrays: self-avoiding random walks

public class SelfAvoidingWalker { public static void main(String[] args) { int N = Integer.parseInt(args[0]); int trials = Integer.parseInt(args[1]); int deadEnds = 0; for (int t = 0; t < trials; t++) { boolean[][] a = new boolean[N][N]; int x = N/2, y = N/2;

while (x > 0 && x < N-1 && y > 0 && y < N-1) { if (a[x-1][y] && a[x+1][y] && a[x][y-1] && a[x][y+1]) { deadEnds++; break; }

a[x][y] = true; double r = Math.random(); if (r < 0.25) { if (!a[x+1][y]) x++; } else if (r < 0.50) { if (!a[x-1][y]) x--; } else if (r < 0.75) { if (!a[x][y+1]) y++; } else if (r < 1.00) { if (!a[x][y-1]) y--; } } } System.out.println(100*deadEnds/trials + "% dead ends"); } }

% java SelfAvoidingWalker 10 100000  5% dead ends

% java SelfAvoidingWalker 20 100000  32% dead ends

% java SelfAvoidingWalker 30 100000  58% dead ends

% java SelfAvoidingWalker 40 100000  77% dead ends

% java SelfAvoidingWalker 50 100000  87% dead ends

% java SelfAvoidingWalker 60 100000  93% dead ends

% java SelfAvoidingWalker 70 100000  96% dead ends

% java SelfAvoidingWalker 80 100000  98% dead ends

% java SelfAvoidingWalker 90 100000  99% dead ends

% java SelfAvoidingWalker 100 100000  99% dead ends

25%

50%

75%

100%

10 20 30 40 50 60 70 80 90 100

Simulation, randomness, and analysis (revisited again)

Remark: Computer simulation is often the only effective way to study a scientific phenomenon.

Self-avoiding walk in an N-by-N lattice

• Start in the middle.

• Move to a random neighboring intersection (do not revisit any intersection).

A. 99+% for N >100 (clear from simulations). YOU can!

Applications

• Model the behavior of solvents and polymers.

• Model the physics of magnetic materials.

• (many other physical phenomena)

Computational models play an essential role in modern scientific research.

Paul Flory 1910-1985

Nobel Prize 1974Q. What is the probability of reaching a dead end?

A. Nobody knows (despite decades of study). Mathematicians and physics researchers cannot solve the problem.

Your first data structure

Some applications in this course:

LFSR

digital audio

digital images

Arrays: A basic building block in programming

• They enable storage of large amounts of data (values all of the same type).

• With an index, a program can instantly access a given value.

• Efficiency derives from low-level computer hardware organization (stay tuned).

N-body simulation

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

Image sources

http://en.wikipedia.org/wiki/Airedale_Terrier#mediaviewer/File:Airedale_Terrier.jpg

http://www.nobelprize.org/nobel_prizes/chemistry/laureates/1974/flory_postcard.jpg

CS.3.C.Arrays.2D

C O M P U T E R S C I E N C E S E D G E W I C K / W A Y N E

P A R T I : P R O G R A M M I N G I N J AVA

h t t p : / / i n t r o c s . c s . p r i n c e t o n . e d u

R O B E R T S E D G E W I C K K E V I N W A Y N E

C om

pu ter Scien

Computer Science

An Interdisciplinary Approach

3. Arrays

1.4