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
> 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 has a shortcut for it, the
enhanced for loop:
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.
Questions About Arrays?
You Can Do This
-
Fall 2018 Q1: 94%
-
Spring 2019 Q1: 92%
-
Fall 2019 Q1: 92%
> 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 of Three Values
Given three integers, find the maximum value.
First, what is our algorithm?
-
Determine if
firstis the largest—if it is, we’re done -
Otherwise we need to consider
secondandthird…
> Click or hit Control-Enter to run the code above
MP0
MP0 will be released today. It’s the first checkpoint of our semester-long Android machine project.
-
Some of you are going to sit down today with MP0 and freak out.
-
Please try to stay calm! Our MPs can be intimating at first, but with time and help from the course staff you’ll get your head around it.
-
You’ll have a chance to get started on MP0 in lab next week, and we encourage you to come to office hours as well.
-
MP0 does toss you into the deep end of Android app development. This is intentional. Working your way through large unfamiliar pieces of code is as much an important computer science skill as solving small problems like our homework.
Split Deadline Discussion
Half you have Sunday deadlines—the other half have Monday deadlines. Let’s talk about why.
Next Time: Functions
Announcements
-
Homework continues today and this weekend.
-
MP0 will be released… now!
-
We have office hours today and over the weekend. Come to get help with MP0!
-
Everything is on the calendar.
-
Please fill out the initial student survey. 1% extra credit for anyone who does by this Sunday 09/08/2019. I have tickets to "Data Not Found" by Kaki King tonight at the Krannert Colwell Playhouse. Meet me in the lobby if you want them.