Arrays and Algorithms
> Click or hit Control-Enter to run the code above
Review: Arrays
A Java array represents a series of zero or more values of the same type.
-
Arrays are our first example of a data structure.
-
Arrays put values in order, one after another.
-
Values in an array also have an index, their position in the array.
Review: Declaring Arrays
Just like other variables, arrays have a name and type.
But when we declare them we use brackets to declare an array instead of a single value.
// A single integer named single
int integer;
// An array of integers named multiple
int[] multiple;
// A single character named one
char one;
// An array of characters named all
char[] all;Review: Initializing Arrays
When it is declared an array is empty. To use it we have to tell Java how many elements it has.
The size cannot be changed once the array is initialized.
All arrays have a .length property that we can use to get their size.
// An array of 8 integers named multiple
int[] multiple = new int[8];
System.out.println(multiple.length); // Prints 8
// An array of characters named all
char[] all;
// Initialize all to hold 4 characters
all = new char[4];Review: Initializing Arrays With Values
We can also assign values to an array when it is initialized:
// An array of the 4 integers 1, 2, 5, 10
int[] multiple = { 1, 2, 5, 10 };
// An array of the characters c, s, !
char[] awesome = { 'c', 's', '!' };0 Indexing
You’re computer scientist now. You start counting at zero.
-
An array’s first value is
a[0] -
An array’s last value is
a[a.length - 1]
> Click or hit Control-Enter to run the code above
Out Of Bounds
> Click or hit Control-Enter to run the code above
Array Limitations
Java arrays are fixed size, meaning that we need to know how large they are during initialization.
-
This can complicate our programs.
-
(If your NetID is
janedoe2, now you know why.) -
Java has other array-like data structures that are more flexible—we’ll discuss them later.
Made For Each Other
Loops and arrays are frequently used together.
This is probably the most common for loop. It iterates over all members of the
array: from 0 to primes.length - 1.
int[] primes = { 2, 3, 5, 7, 11, 13 };
for (int i = 0; i < primes.length; i++) {
System.out.println(primes[i]);
}Enhanced for Loop
int[] primes = { 2, 3, 5, 7, 11, 13 };
for (int i = 0; i < primes.length; i++) {
System.out.println(primes[i]);
}This is so common that Java recently introduced a shortcut for it, the so-called "enhanced" for loop syntax:
int[] primes = { 2, 3, 5, 7, 11, 13 };
for (int prime : primes) {
System.out.println(prime);
}If you don’t care about the index, only the value, this is a useful loop.
> Click or hit Control-Enter to run the code above
> Click or hit Control-Enter to run the code above
> Click or hit Control-Enter to run the code above
> Click or hit Control-Enter to run the code above
> Click or hit Control-Enter to run the code above
What Are Computers Good At?
-
Basic math
-
Simple decision making
-
Doing things over and over again very, very fast
-
And storing data
Now we understand how to harness our computers innate abilities. But how do we get it to do what we want?
Algorithms
Algorithm: a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.
As computer scientists, we implement algorithms by having computers:
-
Perform simple calculations
-
Store the results
-
Make simple decisions
-
Do things over and over again as fast as possible
Algorithm Word Usage
Algorithms are not a new idea—but are heavily associated with a new technology.
All Algorithms All the Time
For the next few weeks we will focus on implementing simple algorithms.
This will allow us to practice our problem-solving abilities while we learn new strategies for structuring our programs.
Maximum Over An Array
Given an array of integers, find the maximum value.
First, what is our algorithm?
-
Declare a maximum value—but what do we initialize it to?
-
Examine each value in the array
-
Compare it with the maximum we’ve seen so far—but then do what?
> Click or hit Control-Enter to run the code above
> Click or hit Control-Enter to run the code above
Consecutive Identical Values
Given an array of chars, find all cases where consecutive elements are the same.
First, what is our algorithm?
-
Examine each value in the array
-
Compare it with the next value—but how do we get at that?
-
Print it out if they are the same
Next Time: Functions
Announcements
-
All homework problems for the first two weeks are due today at midnight.
-
MP0 is due Monday! Come in for help if you need it.
-
Office hours until 5PM today.