title: Introductory Programming in Java Notes author: Haroon

Ghori output: pdf_document: default geometry: margin=1in

urlcolor: blue

How Does a Computer Work?

In broad terms, a computer is an extremely complex circuit that is driven by "binary inputs". A user feeds in input as either 0 (no power) or 1 (power), which when done correctly,
cause the computer to perform specific actions. These combinations of 0s and 1s are often called binary code or machine language and are the only language a computer truly
understands.
A computer processes a single machine instruction in one "cycle" - computer speed is measured in Hz or cycles per second. Modern personal computers run at speeds of around \(3
GHz\) or \(3 \times 10^9\) cycles per second. It's this extraordinary speed that makes computers so valuable.

What is a Programming Language?

A major problem with computers is that machine language is extremely difficult for a human to read and write. So over the years we have developed programming languages which,
for the most part, are designed to bridge the gap between natural human language and machine language. A programming language is something that a human can easily read and
write, and that can be efficiently converted into machine code.
There are thousands of different programming languages in existence - most are not in common use. This website ([Link] has a list of over 500
programming languages with a program in each language that prints the song "99 bottles of beer". All of these languages have different properties and use cases - and there are
entire classes and books on programming language theory. Here we'll just discuss the basics.

High Level vs Low Level

A high level language is a language that's closer to natural language than machine code. High level languages are easier to read by humans, have more layers and safeguards
between the programmer and the processor, and are relatively slow. High level languages are very popular for developing user level software software - websites and apps, research
and quick prototyping, and for tasks that don't require exceptionally fast performance.
A low level language is a language that's closer to machine code than natural language. Low level languages are more difficult for humans to read and have less layers and
safeguards between the programmer and the processor - this means it's easier for a programmer to break the processor using a low level language. Low level languages are also
relatively fast compared to high level languages. Low level languages are popular for designing systems level software - device drivers, operating systems, embedded systems, etc -
and for tasks that require exceptionally fast performance.

High level (C) vs low level (x86

assembly and machine code)

Compiled vs Interpreted
A compiled language is a language that is converted directly to machine code then run by the processor. This conversion step is handled by a compiler and is initially slow.
However, the machine code runs relatively quickly. Additionally, compiled programs are less portable - they have to be recompiled for different architectures and more secure since
reconstructing the source code from the binary files is difficult.
An interpreted language is a language that's converted to machine code and run line by line during run time. That is, when I run an interpreted language, the first line is converted to
machine code and run by the interpreter then the second line is compiled and run and so on. These languages don't have a slow compilation step, but the overall program runtime is
slower (since the conversions happened during runtime). Additionally, interpreted programs are more portable since the interpreters are built to convert the source code based on
architecture, and they are less secure since the source code is shipped out as part of the software.

Java
Java is a multi-purpose programming language developed by Sun Microsystems (bought by Oracle) in 1995. It is the most used programming language in the world. Java is a high
level language and is a hybrid compiled / interpreted language. Java source code is compiled into Java byte code which is then run on top of a Java Virtual Machine (JVM). The JVMs
are architecture specific, but the byte code is not which means Java can be shipped out in its compiled state. This means that Java source code can run on any platform and is faster
than a standard interpreted language. However, Java is still slower than pure compiled languages like C and C++.
 Configuring Your System
Before you can start programming in Java you need to have the Java Developer Kit (JDK) installed on your computer. For this class we use Java 8, but for general use you should
install the most up to date version.
Once you've installed the JDK, you need to install an IDE to write, compile, and run your Java programs. In this class we use JGrasp which is a really bare bones and (quite honestly)
low quality IDE. We use JGrasp because it gets the job done without any added complexity that come with other IDES. Feel free to use another IDE like IntelliJ or Eclipse (which are
more commonly used by professionals) if you so choose.

JDK download ([Link]

JGrasp download ([Link]

When you open JGrasp, create a new Java file by clicking File -> new -> Java. You should see a screen that looks like the figure below.

You can write code in the main editor. Click the green plus button in the upper toolbar to compile your code and click the red "running man" button to run your code. The output of your
code should appear in the console at the bottom of the screen.

Basics of Java Syntax

The Hello World Program
public class Hello {

public static void main(String[] args) {

[Link]("Hello World");
}
}

The first line defines a Java class named "Hello". The entire class is contained in the first set of curly brackets. All java programs must be self contained in a class.
The second line is the header for the main method. The main method is the place where the computer begins running the program. For the first few sections, we will write all of our
code in the main method. The entire method is contained within the second set of curly brackets. The third line is a print command.\

Printing
There are three major ways to print output to the screen in Java.

[Link]("Hello World");
Prints the argument (in this case the string Hello World, but could be an integer, character, float, double, etc) and moves the cursor to a new line.
[Link]("Hello World");
Prints the argument and doesn't move the cursor to a new line.
[Link]("%s", "Hello World");
Prints a string containing format commands (the first argument) and doesn't move the cursor to a new line. A formatted command has the structure: %[flags][width]
[.precision]conversion-character. See the below cheat sheet for a quick reference to the different printf commands.
[Link]
([Link]

Data Types
Java technically has an infinite number of data types since Java programmers can create their own data types. However, all Java data types are build around a set of basic, primitive
data types.

boolean: represents true or false. Example: boolean b1 = true; boolean b2 = false;.

 byte: represents a single 8 bit value (any integer between \(-2^7\) and \(2^7\))
Example: byte b1 = 8; byte b2 = 127;.
char: a single Unicode character - in non-programming speak, this is a data type that holds a single letter or symbol found in text. Example: char c1 = 'a'; char c2 =
'1'; char c3 = '\n';.
short: a 16 bit integer value (any integer between \(-2^15\) and \(2^15\)). Example: short s1 = 8; short s2 = 32767; short s3 = -5;
int: a 32 bit integer value (any integer between \(-2^31\) and \(2^31\)). Example: int i1 = 8; int i2 = 2147483647; int i3 = -20;
long: a 64 bit integer value (any integer between \(-2^63\) and \(2^63\)). Example: long l1 = 8; l2 = 2147483647; long l3 = -10;
float: a 32 bit floating point value. Example float f1 = 10.0; float f2 = 100.323423; flaot f3 = -2132.343;
double: a 64 bit floating point value. Example double d1 = 1.0; double d2 = 1123.3432432; d3 = -4234.324;

Java - and most other programming language - have a more complex data type used to hold text. These are called Strings. Strings are "strings' of characters - essentially the
representation of text in a computer program. Strings are an example of a non-primitive data type. A non-primitive data type is a data type that is made up of primitive (and other
non-primitive data types). Non-primitive data types are more complex than primitives and are named with their first letter capitalized. We define a string useing quotation marks:
String s = "Hello world.";.

Variables
A variable is a container or storage location for a value. These variables only exist while the program is running. A variable has three components, a type, name and value.

public class VarExample {

public static void main(String[] args) {

int luckyNumber = 13;
[Link]("the lucky number is " + luckyNumber);
[Link]("and twice that is " + 2*luckyNumber);
}
}

In line 1 we define a variable (luckyNumber) as an integer (int) which we can call later in the program.
We can define a constant or final variable as a variable that cannot be changed throughout the program. This can be useful for mathematical constants or specific numbers that aren't
changeable. For example, if we want to create a named constant integer set to the value \(1\) we say final int one = 1;

Keyboard Input
Taking in user input is a crucial part of a computer program since we usually want our programs to make computations and decisions based on user input.

import [Link];

public class Variable {

public static void main(String[] args) {

Scanner keyboard = new Scanner([Link]);
[Link] ("Please enter your lucky number ");
int luckyNumber = [Link]();
[Link] ("the lucky number is " + luckyNumber);
[Link] ("And twice that is " + 2*luckyNumber);
}
}

Line 1 imports the Scanner class from the java library.

Line 4 defines a new variable "keyboard" which is a variable of type Scanner.
Line 6 defines a new integer as the next integer entered by the user. This vari able can be called later on in the program.
You can think of a Scanner as a pipe that we can use to read input and files from different sources. When we set up a Scanner as we did above, the pipe is connected to the
Computer's "standard input" (aka the keyboard) and will read input at that location. The Scanner object has a few built in methods that can be used to take in specific types of input. If
we declare Scanner keyboard = new Scanner([Link]);:

[Link]();
Returns the next word (String up until the next whitespace or newline) entered at the console. The next() method strps any whitespace preceeding the next word but does
not include the whitespace after the word.
[Link]();
Returns the next line (String up until the next newline including any other whitespace) entered at the console. The nextLine() method does not strip any whitespace
preceeding the words in the line, but does strip the new line character (\n) at the end of the line.
 [Link]();
Returns the next integer entered at the console ignoring whitespace.
[Link]();
Returns the next double entered at the console ignoring whitespace.
[Link]();
Returns whether or not there is an unprocessed word entered at the console.
[Link]();
Returns whether or not there is an unprocessed line entered at the console.

Here is a more complex example of how a scanner works

import [Link];

public class AdvancedScannerExample {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
[Link]([Link]());
[Link]([Link]());
[Link]([Link]());
[Link]([Link]());
}
}

If we input

hello my name is George.

10 !

The program will print

hello
my name is George.
10
!

For more Scanner commands see [Link] ([Link]

Basic Value Manipulation

One of the main purposes of computers is to perform calculations more quickly than humans. Java has many operations which can be used to perform arithmetic, manipulate data,
etc.

Arithmetic Operations

The arithmetic operations in Java are

+ addition
- subtraction
* multiplication
/ division
% modulus (remainder)

Integer Division

When a value or variable is stored a certain ammount of memory is allocated based on the type. Thus integers, doubles, floats, strings, etc cannot be simply interchanged. This
doesn't present as a problem when undergoing addition, subtraction, or multiplication since adding, subtracting, and multiplying two integers will yield an integer. However when
dividing integers we encounter a problem. Dividing two integers can yield a decimal number which does not "fit" in the memory allocated for the integers. Thus the computer truncates
the number at the decimal point to ensure that the new number will be stored.
Thus if we have two integers 3 and 7. According to the compiler 7/3 = 2 However if we want to obtain the "real" answer we can say 7/ (double) 3 = 2.33333

The Math Library

 Java also has a built in Math package for more complicated mathematical operations. You're not expected to know the entirity of the Math package, but there are a few methods
which you should know off the top of your head. Note that while I'm writing these functions with a very specific set of input arguments, there are equivalent functions for variables of
different data types. For example there is a [Link](int a), a [Link](double a), a [Link](long a), etc all of which return the absolute value of the argument /
parameter (a).

[Link](int a, int b);

Returns \(a^b\).
[Link](int a);
Returns \(\sqrt(a)\).
[Link](double a);
Returns \(\log_{e}(a)\).
Math.log10(double a);
Returns \(\log_{10}(a)\).
[Link](int a, int b);
Returns the larger of the two parameters.
[Link](int a, int b);
Returns the smaller of the two parameters.
[Link](double a);
Returns the absolute value of the parameter.
[Link](double a);
Returns the largest integer less than the parameter. For example if double a = 4.5, [Link](a) returns 4.0.
[Link](double a);
Returns the smallest integer greater than the parameter. For example if double a = 4.5, [Link](a) returns 5.0.

A full list of Math methods can be found at [Link] ([Link]

String Manipulation
Java maintains a list of String manipulation methods on their website. If we have a String myString = "This is my string!";:

[Link](2);
Returns the character at index 2 (3rd character) in myString.
[Link](5);
Returns the string from index 5 till the end.
[Link](1, 5);
Returns the string from index 1 (inclusive) to index 5 (exclusive).
[Link]();
Converts the string to lower case.
[Link]();
Converts the string to upper case.
[Link](str);
Returns true if myString contains str, false if not.
[Link](str);
Returns the index of the first incidence of the string str in myString or -1 if str is not in myString. Can also be called on a character.
[Link]();
Returns the length of the string.

A full list of String methods can be found at [Link]

([Link]

Random Numbers
Sometimes we may want to generate a random number as part of our program (we could be writing a board game that uses a dice, simulating a biological process, or testing another
program). Java has a specific module designed to handle random number generation.
To use this module we must import the Random class and declare a new Random object - keep in mind you only need to declare one random object even if you want to generate
multiple random variables. If we have Random gen = new Random();

[Link]();
Returns a random integer.
[Link](x);
Returns a random integer between 0 and x (not including x).
[Link]();
Returns a random double between 0 and 1.
[Link]();
Returns a random boolean value (true or false).
 [Link]();
Returns a random double from the Gaussian (Normal) distribution with mean 0 and standard deviation 1.

We can use these methods to generate random integers and floats between L (inclusive) and H (exclusive).

[Link](H-L+1) + L
Returns a random integer between L and H (inclusive).
[Link]()*(H-L) + L
Returns a random double between L and H (inclusive).

The complete list of random number generation methods can be found at [Link]
([Link]

Example

The following program takes two doubles as inputs (high and low) and prints two random numbers - the first is a random integer between high and low (inclusive) and the ssecond a
random double between high and low (inclusive).

import [Link];
import [Link];

public class RandomExample {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
Random gen = new Random();
[Link]("High: ");
double high = [Link]();
[Link]("Low: ");
double low = [Link]();
// note that (int) high casts the double variable "high" to an integer
int randInt = [Link]((int) high - (int) low + 1) + (int) low;
double randDouble = [Link]() * (high-low) + low;
[Link]("A random number between %d and %d is %d\n", (int)low, (int)high, randInt);
[Link]("A random double between %f and %f is %f\n", low, high, randDouble);
}

Control Flow
Boolean Statements
Boolean is one of the primitive data types in Java. A boolean variable can take on two values, true or false and can be created using combinations of relational statements and
boolean variables chained together by logical operators.

Relational Operators

< less tha

> greater than
<= less than or equal to

= greater than or equal to

== check for equality

!= not equal

Logical Operators

&& and
|| or
! not

A && B is true if A and B both evaluate to true. Otherwise A && B is false.

A || B is true if either A or B or both A and B are true. Otherwise A || B is false.

 !A is true if A is false. Otherwise !A is false.

AND
True && True = True
True && False = False
False && True = False
False && False = False

OR
True || True = True
True || False = True
False || True = True
False || False = False

NOT
!True = False
!False = True

For example

bool x = 5 < 10; // true

bool y = 5 > 10; // false
bool z = x && y; // false
bool z = x || y; // true

The not (!) operator can be distributed using De Morgan's Laws:

!(A && B) = !A || !B
!(A || B) = !A && !B

If, Else If, and Else

If/Else if/Else blocks are used to execute specific lines of code based on a set of conditions. There are several ways to use these blocks.
If I want to execute a block of code only if a condition is true I would use an if statement. An if statement is paired with a specific boolean expression (condition). If that boolean
expression evaluates to true, the code inside the if block is executed. Otherwise, the code is not executed.

int val = [Link]();

if (val > 5) {
// inside the if block
[Link]("val was greater than 5");
}

If I want to execute a block of code if a condition is true and a completely different block if the condition is false I would use an if block paired with an else block. An else block comes
after an if (or else if, see below) and is executed if the if statement's boolean condition evaluates to false. In the example below, we want to print one statement if the user entered a
value greater than 5 and a completely different statement otherwise.

int val = [Link]();

if (val > 5) {
// inside the if block
[Link]("val was greater than 5");
}
else {
// inside the else block
[Link]("val was less than or equal to 5");
}

If I want to execute a different block of code based on more than two possible outcomes (ie one block if condition_1 is true, another if condition_2 is true, another if condition_3 is true,
etc) I would use an if block paired with else if blocks and optionally a final else block. A set of else if block comes after an if block. Each individual else if is paired with a boolean
conditions - if none of the conditions above were true and the else if's condition is true, that block of code gets executed. If none of the if or else if blocks get executed, the else block
is executed.
 double grade = [Link]();
if (grade > 90) {
[Link]("A");
}
else if (grade > 80) {
[Link]("B");
}
else if (grade > 70) {
[Link]("C");
}
else if (grade > 60) {
[Link]("D");
}
else {
[Link]("F");
}

Switch
A switch statements is used when we want to perform a specific action if a primitive variable or String is equal to a specific value. Instead of writing:

if (x == value1) {
// statements
}
else if (x == value2) {
// statements
}
else {
// statements
}

We can write:

switch (x) {
case value1:
// statements
break;
case value2:
// statements
break;
default:
// statements
break;
}

Note that the default case corresponds to the "else" block in an if / else if / else structure. The break keyword breaks out of the switch structure. If you don't end a case with a break,
the program will simply move on through to the next case. This behaviour gives us a bit more flexibility than if/else if statements when it comes to "or" behaviors. If you want to have
an "or" type statements with mutliple variables (ie if x == X or x == Y) we can exclude the break statement and let the cases merge.

switch (x) {
case value1:
case value2:
// statements
break;
default:
// statements
break;
}

Is the same as
 if (x == value1 || x == value2) {
// statements
}
else {
// statements
}

Or say we have three possible actions A, B, and C. If the user enters 'a' we want to perform 'Action A', if the user enters 'b' we want to perform 'Action B' and then 'Action A', and if the
user enters anything else we want to perform 'C'. Below are examples of how you could do this with a switch and an if/else if/else structure. Notice how the switch statement is
syntactically cleaner than the if/else if/else (though both are technically right).

// switch example
char choice = [Link]().charAt(0);
switch (choice) {
case 'b':
// do B
case 'a':
// do A
break;
default:
// do C
}

// if / else if / else example

char choice = [Link]().charAt(0);
if (x == 'a') {
// do A
}
else if (x == 'b')
// do A
// do B
}
eles {
// do C
}

Loops
One of the major benefits of a computer is its ability to quickly complete repetitive tasks. Programming languages like Java have built in structures called loops which we can use to
condense repetitive statements.

For Loops
For loops are the most straight forward and intuitive type of loop. A for loop is defined in three stages:

1. initialization: define a variable (var) to a specific value.

2. ending condition: define a condition (typically based on the value of var) for which you want the loop to continue.
3. assignment: define how var changes for each iteration of the loop.

This is best seen illustrated by an example.

for (int i = 0; i < 10; i++) {

[Link](i + " ");
}

In this example,

1. the variable i is initialized to 0,

2. the for loop will continue so long as i < 10,
3. at the end of each iteration of the loop i will be incrimented by one.
Every iteration of this loop prints the value of i. So the output will look like
 1 2 3 4 5 6 7 8 9

For loops can have a variety of variables, conditions, and assignments. For example, this loop uses a multiplicative assignment statement:

for (int j = 1; j <= 2048; j*=2) {

[Link]("%d ", j);
}

Outputs:

1 2 4 8 16 32 64 128 256 512 1024 2048

We typically use a for loop when we know exactly how many times a loop should run or we know the exact range over which we need to loop. For example, we can use a for loop to
check if a two Strings are equal by iterating over the number of characters in the string.

String s1 = [Link]();
String s2 = [Link]();
boolean areEqual = True;
if ([Link]() == [Link]()) {
int len = [Link]();
for (int i = 0; i < len; i++) {
if ([Link](i) != [Link](i)) {
areEqual = False;
}
}
}
else {
areEqual = False;
}
if (areEqual) {
[Link]("The Strings are the same");
}
else {
[Link]("The Strings are not the same");
}

While Loops
The while loop is the most general type of loop. A while loop keeps executing the loop body so long as a boolean condition is True.

Random gen = new Random();

[Link]("\nWhile loop - continues until di rolls a 3.");
int roll = -1; // simulate rolling a 6 sided di
while (roll != 3) {
roll = [Link](6) + 1;
[Link]("%d ", roll);
}

In this example, [Link](6) + 1 simulates rolling a 6 sided di. The while loop is set to continue while the di roll is not equal to 3. Since this is a random process (we cannot
know when roll will equal 3), this behavior can't can't be easily replicated by iterating over some range of values (ie we can't easily adapt a for loop to this situation).
In general we use a while loop when we don't know exactly how many times the loop will run.

Do-While Loops
A do-while loop is almost exactly like a while loop except the loop body is executed before the condition is checked. This means that the body will always be executed at least once.
 [Link]("Welcome to my do-while example");
do {
[Link]("Press q to quit")
String choice = [Link]();
[Link](choice);
} while (![Link]("q"));

The loop above will continue until the user inputs the string "q". Note that we always want the user to see the "Press q to print" prompt at least once - this is accomplished by the do-
while loop. (You may be thinking "I can do that with a while loop too", and you would be right. This syntax lets us write this behavior a more cleanly, but as we'll see below you can
accomplish the same thing with a while loop). In general we use a while loop when we don't know exactly how many times the loop will run but we always want the loop to run at least
once.

Loop Equivalence
For and do-whlie loops are convenient syntax for a special case of a while loop. That means that any for or do-while loop can be written as a while loop. However, not every while
loop can be rewritten as a for or do-while loop.

[Link]("\nEquivalent for and while loops.");

for (int i = 0; i < 10; i++) {
[Link]("%d ", i);
}
[Link]();
int count = 0;
while (count < 10) {
[Link]("%d ", count);
count++;
}

// do-while to while
[Link]("\nEquivalent do-while and while loops.");
int rollThree = 0;
do {
rollThree = [Link](6) + 1;
[Link]("%d ", rollThree);
} while (rollThree != 3);
[Link]();
int rollFour = 0;
while (rollFour != 3) {
rollFour = [Link](6) + 1;
[Link]("%d ", rollFour);
}

Nested Loops
Loops can be nested within each other to create some complex and more useful behaviors.

This example prints a Triangle out of * characters:

for (int i = 0; i < 10; i++) {

for (int j = 0; j < i; j++) {
[Link]("*");
}
[Link]();
}

This example rolls a di ten times until the average of the ten rolls is less than 3:
 double avgRoll = 6;
final int numRolls = 10;
while (avgRoll >= 3) {
int acumRoll = 0;
for (int i = 0; i < numRolls; i++) {
acumRoll += [Link](6) + 1;
}
avgRoll = acumRoll / (float) numRolls;
[Link]("%.2f ", avgRoll);
}

Scope
When a variable is declared in Java it is given a certain scope. A variables scope is the region in which it is visible (or accessible). A variable is accessible in the block in which it is
declared (including any sub-blocks), but nowhere else.

public class Scope {

public static void main(String[] args) {

int varOne; // varOne is declared in the main method scope
varOne = 10; // varOne is defined (different from begin declared)
if varOne > 1 {
[Link](varOne); // varOne is still in scope
varOne = 20;
int varTwo = 1;
}
[Link](varOne); // varOne is still in scope and its value has changed
[Link](varTwo); // throws a compiler error because varTwo is out of scope.
}
}

File IO
We often want to read data from a file and / or write data to a file. To read data from a file we use the Scanner and FileReader classes. We declare the Scanner similarly to how we
declare a Scanner to read from the keyboard.

import [Link];
import [Link];
impor [Link];

public class IOExampleInFile {

public static void main(String[] args) throws IOException {

Scanner inFile = new Scanner(new FileReader("[Link]"));
// read from the file using next(), nextLine(), nextDouble(), nextInt(), etc.
[Link](); // not strictly necessary when reading from the file
}
}

In this case [Link] is the name of the file we want to open. We can now treat inFile the same way as we treated the Scanners that were reading input from the keyboard. We
can call [Link](), [Link](), [Link](), and [Link]() and expect the same kind of behavior as if we were reading input from the
keyboard.
There are also a couple of methods that we can use to determine how long to read a file:

[Link]() : returns true if there is a next word in the file

[Link]() : returns true if there is a next line in the file
[Link]() : returns true if the next element in the file is an int
[Link]() : returns true if the next element in the file is a double

Using these methods I can read from a file line by line, word by word, etc.

For example to read a file line by line and print each line to the screen:
Scanner infile = new Scanner(new FileReader("[Link]"));
while ([Link]()) {
String line = [Link]();
[Link](line);
}

To write data to a file we use PrintWriter and FileWriter objects which are declared as follows.

import [Link]:
import [Link];
import [Link];

public class IOExampleOutFile {

public static void main(String[] arge) throws IOException {

PrintWriter outFile = new PrintWriter (newFileWriter("[Link]"));
// write to the file
[Link]();
}
}

Writing to a PrintWriter is very similar to printing to the screen - in fact PrintWriter has the same methods as [Link] so you can call [Link](),
[Link](), or [Link]() the same way you'd call [Link](), [Link](), or [Link](). When you're done
writing to an output file you have to call close() on the PrintWriter - otherwise the file may not save.

For example if I wanted to write a bunch of integers to a file:

PrintWriter outFile = new PrintWriter(new FileWriter("[Link]"));

for (int i = 1; i < 2048; i*=2) {
[Link]("%d\n", i);
}
[Link]();

Putting these together - here is an example of copying a file line by line to some output file.

import [Link];
import [Link];
import [Link];
import [Link];
import [Link];

public class IOExample {

public static void main(String[] args) throws IOException {

Scanner inFile = new Scanner(new FileReader("[Link]"));
PrintWriter outFile = new PrintWriter (newFileWriter("[Link]"));
// to find all integers in the file
while ([Link]()) {
[Link]([Link]());
}
/*
for the while loop we can also use [Link] for strings, [Link] for and entire file, [Link] f
*/
[Link]() // closes the output file
}
}

Helper Methods
In java a method is a self contained piece of code that performs a specific task. For example, say we're writing a program that inputs a time and increment and outputs the ending
time. We could write everything in the main method:
 import [Link];

public class TimeAdditionOne {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
String time = [Link]();
String inc = [Link]();
int timeHrs = [Link]([Link](0, 2));
int timeMns = [Link]([Link](3));
int incHrs = [Link]([Link](0, 2));
int incMns = [Link]([Link](3));
int finalMins = (timeMns + incMns) % 60;
int overflowHrs = (timeMins + incMins) / 60;
int finalHrs = (timeHrs + incHrs + overflowHrs) % 24;
[Link]("The final time is %d:%d", finalHrs, finalMins);
}
}

But this can be a bit hard to read. And if we're writing a program that uses this kind of calculation a lot - for example, a calendar app or a stopwatch - copying and pasting this code
everywhere can be tedious. Furthermore, if we wanted to alter this method (say to output time in 12hr format instead of 24hr format), we'd have to change every instance of this code
in the main method.
Instead, we can write a helper method that performs this calculation and call that method wherever we want to add a time increment to a current time.

So our time addition program could be rewritten:

import [Link];

public class TimeAdditionTwo {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
String userTime = [Link]();
String userInc = [Link]();
String finalTime = computeTimeAddition(userTime, userInc); // method call
[Link](finalTime);
}

public static String computeTimeAddition(String time, String inc) {

int timeHrs = [Link]([Link](0, 2));
int timeMns = [Link]([Link](3));
int incHrs = [Link]([Link](0, 2));
int incMns = [Link]([Link](3));
int finalMins = (timeMns + incMns) % 60;
int overflowHrs = (timeMins + incMins) / 60;
int finalHrs = (timeHrs + incHrs + overflowHrs) % 24;
return [Link]("%d:%d", finalHrs, finalMins);
}
}

This is a lot easier to read than the first piece of code. It's a lot easier to follow what the main method is trying to accomplish (especially if we use descriptive method names). Any
methods defined in the same class automatically recognize each other. Notice how in the main method I can just call computeTimeAddition. This is not true when a method is
described in a different class. We can now reuse computeTimeAddition anywhere else in this program. And if we want to modify the functionality we just need to modify one code
block instead of many.

Any method in Java is defined in the following way:

<public / private / protected> <static (optional)> <return type> <method name>(<parameters>) {

// statements
return <value>;
}

<public / private / protected> : Defines which external classes can see this method. Use public for now.
<static> : Don't worry about this for a bit. All your methods will be static for the next few weeks.
 <return type> : The type (int, double, String, etc) of value this method will return to the caller when the method finishes its task. If the method doesn't return anything (ie it
just prints or reads file input or something like that) its return type is void.
<method name> : The name of the method. This should be a reasonably descriptive name and should be formatted in camel-case.
<parameters> : Declarations of variables that this method will take as input. Note that these should be reasonably descriptive names. The names of the variables don't need
to match the names of the variables being passed to the method by the caller. If the method takes no parameters this can be left blank.

For example:

public static double findMin(double x, double y, double z) {

double minXandY = [Link](x, y);
return [Link](z, minXandY);
}

This method:

is public and static.

returns a value of type double to the caller.
is named findMin.
takes three doubles as arguments / parameters.

If I want to find the minimum of three doubles in the main method then I can use:

import [Link];

public class Example {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
double valOne = [Link]();
double valTwo = [Link]();
double valThree = [Link]();
double min = findMin(valOne, valTwo, valThree);
[Link]("The minimum is " + min);
}

public static double findMin(double x, double y, double z) {

double minXandY = [Link](x, y);
return [Link](z, minXandY);
}
}

Methods don't need to take in parameters:

public static int rollDi() {

Random rand = new Random();
return [Link](6) + 1;
}

And methods don't need to return anything (in this case they return void):

public static void flipCoin() {

Random rand = new Random();
flip = [Link](2);
if (flip == 1) {
[Link]("Heads!");
}
else {
[Link]("Tails!");
}
}

When the return keyword is called, the method ends and returns the value after the return. We can use this in behavior to eliminate some else statements.
public static void flipCoin() {
Random rand = new Random();
flip = [Link](2);
if (flip == 1) {
[Link]("Heads!");
return;
}
[Link]("Tails!");
}

These two methods are equivalent, but the second is a bit cleaner and less verbose.

Passing primitives to methods

When I pass a primitive or String variable to a method in Java, the variable itself isn't sent to the method. The value in the variable is copied into a new variable which has scope of
the method. So if I change a primitive or String variable in an external method it doesn't affect the value of the corresponding variable in the caller method.

public static void main(String[] args) {

int x = 10;
int inc = 5;
[Link]("x: %d, inc: %d", x, inc\n);
add(x, inc);
[Link]("x: %d, inc: %d", x, inc\n);
}

public static void add(int x, int inc) {

x += inc
}

In this example, the program should output

x: 10, inc: 5
x: 10, inc: 5

This is because:

1. Two variables, x and inc were declared and defined in the main method. We will refer to these as x_main and inc_main.
2. We print the values of x_main and inc_main.
3. We call add on x_main and inc_main.
1. The value in x_main is copied and sent to a new place in memory. A new variable (also called x) which we will refer to as x_add is declared and defined to be equal to
the value of x_main.
2. The value in \(inc_{main}\) is copied and sent to a new place in memory. A new variable (also called x) which we will refer to as inc_add is declared and defined to be
equal to the value of \(inc_{main}\).
3. x_add is set equal to x_ + inc_.
4. We call add on x_main and inc_main.

Observe how even though the main method AND the add method have variables called x and inc, those variables are not linked. Changing the x in add does not affect the value of
the x in main.

Note: There is another layer to this that we will discuss in a later section

Javadoc Comments
Javadoc comments are special comments that are used to auto-generate documentation for your code. Every class, method, and "member variable" (ignore that last one for now)
must have a javadoc comment - and they must be formatted in a very specific way. The javadoc comment for a method takes the form:
 /**
<First sentence giving a general description of what the method does - this must end with a period ".">
<Any number of more descriptive sentences>
@param <name of parameter 1> <description of parameter 1>
@param <name of parameter 2> <description of parameter 2>
<... do for all parameters>
@return <description of what the method returns. Don't do this for void methods>
*/

For example, our time addition method from above could have the javadoc comment:

/**
* Adds a time increment to a given 12hr clock time.
* @param time the string representing the user entered time
* @param inc the string representing the increment to be added to time
* @return A string representing time + inc in 12hr time
*/
public static String computeTimeAddition(String time, String inc) {
int timeHrs = [Link]([Link](0, 2));
int timeMns = [Link]([Link](3));
int incHrs = [Link]([Link](0, 2));
int incMns = [Link]([Link](3));
int finalMins = (timeMns + incMns) % 60;
int overflowHrs = (timeMins + incMins) / 60;
int finalHrs = (timeHrs + incHrs + overflowHrs) % 24;
return [Link]("%d:%d", finalHrs, finalMins);
}

Recursive Methods
Recursion is one of the more complicated / confusing topics in Intro Java. And while it may seem kind of unnecessary right now, it is a very useful technique to have under your built.

In math, a function is recursive if it calls itself during execution.

For example: the fibonacci sequence

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... $$

Can be represented by the equation \(Fib(0) = 0\) \(Fib(1) = 1\) \(Fib(n) = Fib(n-1) + Fib(n-2)\ \forall n \geq 2\)

In English, the nth fibbonacci number is equal to the n-1th fibonacci number plus the n-2th fibonacci number.

In the past we've computed these functions iteratively

public static int fibonacci(int n) {

int a = 0;
int b = 1;
for (int i = 1; i <= n; i++) {
int tmp = b;
b += a;
a = tmp;
}
return a;
}
int n = 10;
[Link]("The %dth fibonacci number is %d", n, fibonacci(n));

The 10th fibonacci number is 55

But Java allows us to write functions that are recursive - ie methods that call themselves. This can make it a lot easier to solve some problems (like fibonacci).

Most recursive methods are based on the divide and conquer mentality. That is "this problem is too big to easily solve, but if I break it up into smaller pieces (which oare easier to
solve), solve those pieces, and combine the results (in some specific way) I can solve the problem).
 All problems that can be solved iteratively (with loops) can be solved with recursion and oftentimes the recursive solution looks nicer than the iterative solution. Not all
recursive problems can be easily solved with loops - usually we want to go from iterative to recursive, not the other way around. Recursion vs iteration is often a tradeoff
between efficiency and simplicity / clarity.

When writing a recursive function we break the problem into two pieces

1. The base case This is the smallest instance of the problem - the point at which we know or are given the answer to the problem. For example, in the fibonacci sequence we
know Fib(0) = 0 and Fib(1) = 1 - so those are our base cases.
2. The recursive step This is how we want to structure our recursive calls. For example, in the fibonacci sequence we know that \(Fib(n) = Fib(n-1) + Fib(n-2)\) for all \(n \geq 2\).

public static int recursiveFibonacci(int n) {

if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
}
int n = 10;
[Link]("The %dth fibonacci number is %d", n, recursiveFibonacci(n));

The 10th fibonacci number is 55

How does this work?

When I call a function recursively in Java. The function is executed as expected until I reach a recursive method call. At that point, the current method execution is put on hold until
the recursive call completes.

public static int recursiveFibonacci(int n) {

[Link]("N = %d\n", n);
if (n == 0) {
[Link]("Fib(0) = 0");
return 0;
}
else if (n == 1) {
[Link]("Fib(1) = 1");
return 1;
}
else {
[Link]("Fib(%d) = Fib(%d) + Fib(%d)\n", n, n-1, n-2);
int n_1 = recursiveFibonacci(n-1);
[Link]("N = %d\n", n);
[Link]("Fib(%d) = %d + Fib(%d)\n", n, n_1, n-2);
int n_2 = recursiveFibonacci(n-2);
[Link]("N = %d\n", n);
[Link]("Fib(%d) = %d + %d\n", n, n_1, n_2);
return n_1 + n_2;
}
}

recursiveFibonacci(4);
 N = 4
Fib(4) = Fib(3) + Fib(2)
N = 3
Fib(3) = Fib(2) + Fib(1)
N = 2
Fib(2) = Fib(1) + Fib(0)
N = 1
Fib(1) = 1
N = 2
Fib(2) = 1 + Fib(0)
N = 0
Fib(0) = 0
N = 2
Fib(2) = 1 + 0
N = 3
Fib(3) = 1 + Fib(1)
N = 1
Fib(1) = 1
N = 3
Fib(3) = 1 + 1
N = 4
Fib(4) = 2 + Fib(2)
N = 2
Fib(2) = Fib(1) + Fib(0)
N = 1
Fib(1) = 1
N = 2
Fib(2) = 1 + Fib(0)
N = 0
Fib(0) = 0
N = 2
Fib(2) = 1 + 0
N = 4
Fib(4) = 2 + 1

Recursion as a Tree

Green "leaves" are the base cases

Blue "nodes" make recursive calls

Blue "edges" recurse "downwards"

Orange "edges" passes values back up the tree

Go down the leftmost arrow first

Wasted Work

We can fix these issues using techniques like dynamic programming or storing pre-computed results and passing them through the recursion. You'll learn about these techniques in
Data Structures or Algorithms.
 Exponential problem

The recursion will only end when every path down the tree has reached a base case. So the computer will have to expend effort proportional to the number base cases we eventually
reach (the number of leaves in the tree). For the fibonacci function we can see that the tree is reminiscent of a binary tree - each node has at least two descendants. So there are
approximately \(2^{n}\) base cases in the function.

\(Fib(4) \approx 2^4 = 16 \ effort\)

\(Fib(10) \approx 2^{10} = 1024 \ effort\)

\(Fib(1000) \approx 2^{1000} = 1.07 \times 10^{31} \ effort\)

We'll talk about this more in a few weeks.

Not all recursive methods are exponential work or recompute values as we'll see below - the fibonacci sequence is just a really good example of the power and pitfalls of recursion.

Recursion in the Real World

Disclaimer: in this course most useful recursive problems could be easily solved iteratively. That will not always be true - especially in Data Structures and Algorithms.

The fibonacci sequence is a cool, but not particularly useful application of recursion. Let's consider a more useful application - reversing a string.

Reversing a String

public static String reverse(String s) {

if ([Link]() < 2) {
return s;
}
return [Link]([Link]() - 1) + reverse([Link](0, [Link]() - 1));
}

String toReverse = "Hello World";

[Link]("\"%s\" reversed is \"%s\"", toReverse, reverse(toReverse));

"Hello World" reversed is "dlroW olleH"

Observe that this tree is linear and doesn't require any recalculation

Checking if a String is a Palindrome

 public static boolean recursiveIsPalindrome(String s) {
if ([Link]() < 2) {
return true;
}
return [Link](0) == [Link]([Link]() - 1)
&& recursiveIsPalindrome([Link](1, [Link]() - 1));
}

String s1 = "racecar";
String s2 = "hello";
[Link]("\"%s\" is a palindrome? " + recursiveIsPalindrome(s1) + "\n", s1);
[Link]("\"%s\" is a palindrome? " + recursiveIsPalindrome(s2) + "\n", s2);

"racecar" is a palindrome? true

"hello" is a palindrome? false

Guidelines for Recursion

Keep the divide and conquer philosophy in mind.

1. Start with the base case. What is the easiest version of this problem? When do i definitely know I can solve this problem?
2. What is a good way to divide this problem up?
3. How can I recombine sub-solutions to get the actual solution?

Common Errors in Recursion

StackOverflowExceptions

Remember when you learned about loops we said "your while loops need to terminate at some point otherwise your code will run forever"? Recursion works the same way. If you
don't have a base case (or if your function doesn't reach the base case after a reasonable amount of iterations, your computer will run out of "stack memory" (don't worry about what
that means) and will throw a StackOverflowException.

public static int badRecursiveFibonacci(int n) {

return badRecursiveFibonacci(n-1) + badRecursiveFibonacci(n-2);
}

int n = 10;
badRecursiveFibonacci(n);

---------------------------------------------------------------------------
[Link]:
at .badRecursiveFibonacci(#29:2)
at .badRecursiveFibonacci(#29:2)
at .badRecursiveFibonacci(#29:2)
at .badRecursiveFibonacci(#29:2)
at .badRecursiveFibonacci(#29:2)

Obviously the code above is bad. It doesn't make sense based on our understanding of the fibonacci function. But sometimes you may include a base case that is unreachable or not
easily reachable. When you're writing recursive functions always make sure your recursive methods have a reachable base case.
 /* Calculates the sume of the range 0, n */
public static int sumOfRange(int n) {
if (n == 0) {
return 0;
}
return n + sumOfRange(n - 1);
}

sumOfRange(-10);

---------------------------------------------------------------------------
[Link]:
at .sumOfRange(#33:6)
at .sumOfRange(#33:6)
at .sumOfRange(#33:6)
at .sumOfRange(#33:6)
at .sumOfRange(#33:6)

The proper way to do this would be to set the base case to catch the < 0 case and write documentation explaining what invalid input will return

/**
* Calculates the sum of the range 0, n where n is a posative integer
* @param n a positive integer
* @return the sum of all integers between 0 and n inclusive if n is posative.
* else 0.
*/
public static int sumOfRange(int n) {
if (n <= 0) {
return 0;
}
return n + sumOfRange(n - 1);
}

sumOfRange(10);
sumOfRange(-10);

55
0

Excessive Computation

As we said above, recursive methods can compute the same results a lot of times if you don't explicitly take steps to prevent that. So sometimes even if you have a base case, if you
give a recursive problem a really large input, it will either take a long time to run or throw a StackOverflowException.

public static int badRecursiveFibonacciTwo(int n) {

if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
return badRecursiveFibonacciTwo(n-1) + badRecursiveFibonacciTwo(n-2);
}
badRecursiveFibonacciTwo(1000);

Examples
From decimal to binary

Given an integer \(n\) in base 10, convert \(n\) to binary (base 2). [Link] ([Link]
 public static String toBinary(int n) {
if (n < 0) { // error case
return "";
}
else if (n < 2) { // base case
return "" + n;
}
return toBinary(n / 2) + n % 2;
}

toBinary(10);

"1010"

Convert to arbitrary base

So far we've only converted to bases lower than 10. But if we're converting to bases > 10 we need more digits to represent digit values > 10. We use the convention that 10 -> 'A', 11 -
> 'B', 12 -> 'C'...

/**
* Helper method that converts a single decimal digit to base newBase.
* @param val the integer digit in base 10. 0 <= val < newBase.
* @param newBase the base we are converting to. newBase > 2.
* @return the String newBase representation of val or "-1" if the
* input value is invalid.
*/
public static String getDigit(int val, int newBase) {
if (val < 0 || val > newBase || newBase < 2) {
return "-1";
}
if (val < 10) {
return "" + val;
}
return "" + (char)('A' + (val - 10));
}

public static String toBase(int n, int newBase) {

if (n <= 0) {
return "";
}
return toBase(n / newBase, newBase) + getDigit(n % newBase, newBase);
}

toBase(15, 16);
toBase(145, 16);

"F"
"91"

Sum of digits

Given an positive integer, return the sum of the digits of the integer.

public static int sumDigits(int n) {

if (n <= 0) {
return 0;
}
return n % 10 + sumDigits(n / 10);
}

sumDigits(44);
 8

Stair climbing

You are standing at the base of an n-step staircase. At each step you can either move forward by one step or two steps. How many unique ways can you climb the staircase?

public static int numSteps(int n) {

if (n <= 2) {
return n;
}
return numSteps(n - 1) + numSteps(n - 2);
}

numSteps(5);

Stair climbing pt 2

Given the same situation as above, how many unique ways can you climb the staircase if you can move forward by one, two, or three steps?

public static int numSteps(int n) {

if (n <= 2) {
return n;
}
else if (n == 3) {
return 4;
}
return numSteps(n - 1) + numSteps(n - 2) + numSteps(n-3);
}

numSteps(5);

13

Instantiable Classes
So far we've worked with data types that have been defined for us. However a lot of the time we want to be able to define our own data types - with their own associated variables
and methods. This is the basic principle behind Object Oriented Programming. Object oriented programming is a programming paradigm centered around user defined data types
(aka objects). An object oriented programming language (like Java) allows users to define their own data types and use them in programs. From here on out I'll say object instead of
data type.

We define our own objects by writing an instantiable class. An instantiable class is essentially a blueprint for an object - it defines what an object contains, how to create an object,
and the methods you can call on the object. A basic instantiable class can be broken down into three sections

1. The member variables - The member variables define what data the object stores.
2. The constuctor(s) - The constructors define how we create a new instance of the object.
3. The methods - These are methods we can call on the object.

The Problem

We're going to be using this problem for most of our discussion of OOP. The NBA playoffs are coming up and we want to write a program to keep track of the performance of our
favorite basketball teams as they advance through the postseason. We could write some really complicated code to keep track of each team and link their win / loss percentages
together, but instead we're going to use object oriented programming.
 public class Team {

public String name;

public int gamesWon;
public int gamesLost;
public double winPercentage;

public Team(String name) {

[Link] = name;
[Link] = 0;
[Link] = 0;
[Link] = 0;
}

public void updateWinPercentage() {

if ([Link] + [Link] == 0) {
[Link] = 0;
}
[Link] = 100 * (double)[Link]
/ ([Link] + [Link]);
}

public String toString() {

return [Link]("%s: %d won %d lost, %.2f%%",
[Link], [Link], [Link],
[Link]);
}
}

This is a very basic class. Note the three parts

1. The member variables are name, gamesWon, and gamesLost. These values are accessible anywhere within the entire class.
2. The constructor is a method with the same name as the class (in this case Team). It is used to set up the object. It is possible to have more than one constructor.
3. In this case we only have one method. This method uses the stored gamesWon and gamesLost to get the team's win percentage.

Also note that the this keyword refers to the current instance of the class. When I call [Link] inside a class definition I am referring to the gamesLost variable inside a
specific instance of Team.

You must save an instantiable class in a file with the same name as the class. So the Team class would be in a file called [Link]. The easiest way to access the Team class from
another program is to save [Link] in the same folder (directory) as the driver (program with the main method).

Now we can create variables that are "instances" of type Team whose behavior is defined by the blueprint above.

Team kings = new Team("Sacramento Kings");

Team lakers = new Team("LA Lakers");

Now that we've created some Teams we can access and modify their stored variables and call their methods.

[Link]([Link]());
[Link]([Link]());
// if the kings beat the lakers
[Link]++;
[Link]++;
[Link]();
[Link]();
[Link]([Link]());
[Link]([Link]());

There is a major problem with this construction. Anyone can change any of the variables at any time. This can be advantageous sometimes, but usually it leads to synchronization
problems between our variables.
 [Link] += 10;
[Link]([Link]());

[Link] -= 10;
[Link]();
[Link]([Link]());

To fix these inconsistencies, we define our variables with the private keyword instead of public. If a member variable or method is private it cannot be seen or accessed outside of the
class - the methods inside the class can access private variables and methods, but nothing outside can access a private variable or method. We then write methods to "get" and "set"
the member variables - we call these getter and setter methods.

For our Team class:

public class Team {

private String name;

private int gamesWon;
private int gamesLost;
private double winPercentage;

public Team(String name) {

[Link] = name;
[Link] = 0;
[Link] = 0;
[Link] = 0;
}

public String getName() { return [Link]; }

public int getGamesWon() { return [Link]; }
public int getGamesLost() { return [Link]; }
public double getWinPercentage() { return [Link]; }

public void wonGame() {

[Link]++;
[Link]();
}

public void lostGame() {

[Link]++;
[Link]();
}

private void updateWinPercentage() {

if ([Link] + [Link] == 0) {
[Link] = 0;
}
[Link] = 100 * (double)[Link]
/ ([Link] + [Link]);
}

public String toString() {

return [Link]("%s: %d won %d lost, %.2f%%",
[Link], [Link], [Link],
[Link]);
}
}

Like member variables, class methods can be public or private. Public methods can be called from an external class and private methods can obly be called from within the class. We
use private methods to execute "helper" functions that we don't want the user to explicitly do. For example, we set the updateWinPercentage method to private because we want
that to be done intenally, without external user input.
Team kings = new Team("Sacramento Kings");
Team lakers = new Team("LA Lakers");

[Link]([Link]());
[Link]([Link]());
// if the kings beat the lakers
[Link]();
[Link]();
[Link]([Link]());
[Link]([Link]());

for (int i = 0; i < 10; i++) {

[Link]();
}
[Link]([Link]());

Setting variables and methods to private forces users and other programmers to interact with your class in ways that you have defined. This makes it a lot easier to write error-free
code.

For example, in the above example I can no longer just set a team to lose or win a bunch of games. They can only lose or win one game at a time.

When programming (in the real world) you should operate under the assumption that the user will try to break your programs - you should write and test your code accordingly.

Common Methods
Most classes you write will have some methods in common

1. toString() - this method returns a string representation of the object

2. equals(Object o) - this method compares the object with another object
3. compareTwo(Object o) - this method checks if two objects are equal to each other.
public class Team {

private String name;

private int gamesWon;
private int gamesLost;
private double winPercentage;

public Team(String name) {

[Link] = name;
[Link] = 0;
[Link] = 0;
[Link] = 0;
}

public String getName() { return [Link]; }

public int getGamesWon() { return [Link]; }
public int getGamesLost() { return [Link]; }
public double getWinPercentage() { return [Link]; }

public void wonGame() {

[Link]++;
[Link]();
}

public void lostGame() {

[Link]++;
[Link]();
}

private void updateWinPercentage() {

if ([Link] + [Link] == 0) {
[Link] = 0;
}
[Link] = 100 * (double)[Link]
/ ([Link] + [Link]);
}

public boolean equals(Object o) {

if (o instanceof Team) {
Team other = (Team) o;
return [Link] == [Link]()
&& [Link] == [Link]()
&& [Link]([Link]());
}
return false;
}

public int compareTo(Object o) {

if (o instanceof Team) {
Team other = (Team) o;
return (int)([Link] - [Link]());
}
return -1;
}

public String toString() {

return [Link]("%s: %d won %d lost, %.2f%%",
[Link], [Link], [Link],
[Link]);
}
}
 Team kings = new Team("Sacramento Kings");
Team lakers = new Team("LA Lakers");
[Link]("Comparing kings and lakers " + [Link](lakers));
[Link]();
[Link]();
[Link]("Comparing kings and lakers " + [Link](lakers));
Team otherKings = new Team("Sacramento Kings");
[Link]("Are two kings equal? " + [Link](otherKings));
[Link]();
[Link]("Are two kings equal? " + [Link](otherKings));

The keyword instanceof checks to see if some object is an instance of the given type. So o instanceof Team evaluates to true if o can be viewed as a Team and false if not.

Defining Static
In Java, a static member is a member of a class that isn’t associated with an instance of a class. Instead, the member belongs to the class itself. As a result, you can access the
static member without first creating a class instance.

Consider the Math class. You can use [Link] and [Link] without doing Math m = new Math();. abs and pow are thus static members of the Math class because they
don't depend on a specific instantiation of Math.

Your main method is also always static because it is irrespective of any potential instantiation of the class.
public class Team {

private String name;

private int gamesWon;
private int gamesLost;
private double winPercentage;
private static final int numPlayers = 5;

public Team(String name) {

[Link] = name;
[Link] = 0;
[Link] = 0;
[Link] = 0;
}

public static void playGame(Team won, Team lost) {

[Link]();
[Link]();
}

public String getName() { return [Link]; }

public int getGamesWon() { return [Link]; }
public int getVamesLost() { return [Link]; }

public void wonGame() {

[Link]++;
[Link]();
}

public void lostGame() {

[Link]++;
[Link]();
}

private void updateWinPercentage() {

if ([Link] == 0 && [Link] == 0) {
[Link] = 0;
}
[Link] = 100 * (double)[Link]
/ ([Link] + [Link]);
}

public boolean equals(Object o) {

if (o instanceof Team) {
Team other = (Team) o;
return [Link] == [Link]()
&& [Link] == [Link]()
&& [Link]([Link]());
}
return false;
}

public int compareTo(Object o) {

if (o instanceof Team) {
Team other = (Team) o;
return (int)([Link] - [Link]());
}
return -1;
}

public String toString() {

return [Link]("%s: %d won %d lost, %.2f%%",
[Link], [Link], [Link],
[Link]);
 }
}

Team kings = new Team("Sacramento Kings");

Team lakers = new Team("LA Lakers");

[Link]([Link]());
[Link]([Link]());
// if the kings beat the lakers
[Link](kings, lakers);
[Link]([Link]());
[Link]([Link]());

Pass by Reference Value

One of the major differences between primitive types and Objects is how they are represented in memory. We can visualize the computer memory as a array where the data at the
$i$th index corresponds to memory address \(i\):

When we define a primitive, for example int primitive = 1;, the variable primitive points to (aka references) some memory address \(i\) and the data at memory address \(i\)
is the value of primitive (ie 1).

However, when we define an Object, for example SomeClass nonPrimitive = new SomeClass();, the variable nonPrimitive references some memory address \(j\) but the
data at memory adress \(j\) is another memory address \(k\). The data at memory address \(k\) is the data corresponding to nonPrimitive.

This distinction comes into play when we pass variables into methods. Java "passes by reference value". That means that when if I have a variable x that references some memory
address \(A\), when I pass x into a method the computer will copy the data at \(A\) and save it at a new memory address \(B\).

If x is primitive, the data at \(A\) is the value of x. So when we pass x into a method, the computer copies the value of x to \(B\) and uses that memory address in when executing the
method - effectively we copy x into a new variable and use that new variable in the method. The effect of this is that if I pass a primitive variable into a method, changing the
variable inside the method will not effect the variable outside of the method.

However, if x is not primitive, the data at \(A\) is a reference to the data associated with x. So when we pass x into a method, the reference to the data is copied to \(B\) and that
memory address is used when executing the method. This effectively means that if we call any methods on x that change x inside the method, those changes will effect the
variable outside of the method. However if, inside the method, we set x to a new value, that changes the value of the reference at \(B\) rather than the data referenced by \
(B\) so the value of x will not change outside the method.
public class SimpleClass {

private int data;

public SimpleClass(int x) {
[Link] = x;
}

public int getData() { return [Link]; }

public void makeSimpleClass(SimpleClass y) {

[Link] = [Link]();
}

public String toString() {

return "SimpleClass: " + [Link];
}
}

public static void attemptSwap(int x, int y) {

int temp = x;
x = y;
y = temp;
}

int varOne = 10;

int varTwo = 20;
[Link]("varOne=%d, varTwo=%d\n", varOne, varTwo);
attemptSwap(varOne, varTwo);
[Link]("varOne=%d, varTwo=%d\n", varOne, varTwo);

varOne=10, varTwo=20
varOne=10, varTwo=20

public static void attemptSwap(SimpleClass x, SimpleClass y) {

SimpleClass temp = new SimpleClass([Link]());
[Link](y);
[Link](temp);
}

SimpleClass cOne = new SimpleClass(10);

SimpleClass cTwo = new SimpleClass(20);
[Link]("cOne=%s, cTwo=%s\n", [Link](), [Link]());
attemptSwap(cOne, cTwo);
[Link]("cOne=%s, cTwo=%s\n", [Link](), [Link]());

cOne=SimpleClass: 10, cTwo=SimpleClass: 20

cOne=SimpleClass: 20, cTwo=SimpleClass: 10

public static void attemptSwap(SimpleClass x, SimpleClass y) {

SimpleClass temp = x;
x = y;
y = temp;
}

SimpleClass cOne = new SimpleClass(10);

SimpleClass cTwo = new SimpleClass(20);
[Link]("cOne=%s, cTwo=%s\n", [Link](), [Link]());
attemptSwap(cOne, cTwo);
[Link]("cOne=%s, cTwo=%s\n", [Link](), [Link]());
 cOne=SimpleClass: 10, cTwo=SimpleClass: 20
cOne=SimpleClass: 10, cTwo=SimpleClass: 20

Arrays
Arrays are the most fundamental data structure in Java (and most mainstream programming languages). An array is, essentially a fixed length list of values of a specific type.

Array Basics
Creating and Printing Arrays
We can create an array in two ways:

int[] arrOne = new int[10];

The code above creates a new, empty array. In this array each element is of type int and the array is of size 10.

int[] arrTwo = {1, 2, 3, 4, 5};

The code above creates a new prefilled array. (this is called the list initializer method).

In Java, arrays are non-primitive data types (objects). Therefore the variable arrOne technically is a "reference" which points to the memory location where the array data is being
stored. So we can't print an array directly using [Link].

[Link](arrOne);

[I@7f416310

Instead we need to use a for loop to access each element individually.

/**
* Prints an array of integers. The same idea can be used to print any
* array - just change the data type of the array and add a call to
* toString if you're dealing with non-primitives.
* @param arr the array to print
*/
public static String printIntegerArray(int[] arr) {
String toPrint = "[";
for (int i = 0; i < [Link]; i++) {
toPrint += arr[i] + ", ";
}
toPrint = [Link](0, [Link]() - 2) + "]";
return toPrint;
}

public static String printObjectArray(Object[] arr) {

String toPrint = "[";
for (int i = 0; i < [Link]; i++) {
toPrint += arr[i] + ", ";
}
toPrint = [Link](0, [Link]() - 2) + "]";
return toPrint;
}

Observe in the for loops above we called [Link] instead of [Link](). That is because the length field in the Array class is a variable, not a method (as it is in the String
class).

Accessing array elements

 We can access each element in an array using bracket notation. arrOne[2] refers to the 2nd index in arrOne. Recall that Java indexes at 0, so the 2nd index is actually the 3rd
position.

for (int i = 0; i < [Link]; i++) {

arrOne[i] = (int)[Link](i, 2);
}

[Link](printIntegerArray(arrOne));

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

for (int i = 1; i < [Link]; i+=2) {

arrOne[i] = -1*arrOne[i];
}

[Link](printIntegerArray(arrOne));

[0, -1, 4, -9, 16, -25, 36, -49, 64, -81]

The For-Each Loop

The for-each loop is a special way to write a for loop to make accessing array elements a bit less wordy.

Instead of

for (int i = 0; i < [Link]; i++) {

[Link]("%d ", arrOne[i]);
}

0 -1 4 -9 16 -25 36 -49 64 -81

I can write

for (int e : arrOne) {

[Link]("%d ", e);
}

0 -1 4 -9 16 -25 36 -49 64 -81

The syntax of this loop is

for (<data_type> <var_name> : <array>) {

// do something with var_name
}

The loop sets var_name to each element in <array> (in order) and executes the body of the loop. It's the exact same idea as the traditional for loop above. The one caveat with this
type of loop is that you can't use it to change the value of the array elements - you can see, use, and copy, but not change the values.

for (int x : arrTwo) {

x = 10;
}
[Link](printIntegerArray(arrTwo));

for (int i = 0; i < [Link]; i++) {

arrTwo[i] = 10;
}
[Link](printIntegerArray(arrTwo));
 [1, 2, 3, 4, 5]
[10, 10, 10, 10, 10]

Instantiating Arrays

When we first instantiate an array, the array is filled with "empty values" of the specific type. If the array type is a primitive, every element in the array will be set to 0. If the array type
is non-primitive, every element in the array will be set to Null. Null is a special value which means that a variable has been declared but not defined - you can think of it as 0 for
non-primitives. You may see None used instead of Null in other languages - they mean the same thing.

public class Square {

private double length;

public Square(double len) {

if (len < 0) {
[Link] = 1;
return;
}
[Link] = len;
}

public double getSideLength() { return [Link]; }

public double getArea() { return [Link]([Link], 2); }

public void setSideLength(double len) {

if (len <= 0) {
[Link]("Invalid length");
}
[Link] = len;
}

public String toString() {

return [Link]("Square with side length = %.2f", [Link]);
}
}

int[] emptyArray = new int[10];

[Link]("Empty array of ints (primitive)");
[Link](printIntegerArray(emptyArray) + "\n");

[Link]("Empty array of Circles (non-primitive)");

Square[] emptyArray = new Square[10];
[Link](printObjectArray(emptyArray));

Empty array of ints (primitive)

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Empty array of Circles (non-primitive)

[null, null, null, null, null, null, null, null, null, null]

Common Array Errors

NullPointerException

A NullPointerException occurs when you attempt to do something to a Null object. Recall that a Null object has not been defined (initialized) so trying to do anything to it
makes no sense. You will often see NullPointerExceptions when you haven't initialized the elements in your array yet.

Square[] squares = new Square[5];

for (int i = 0; i < [Link]; i++) {
squares[i].setSideLength(2*(i+1));
}
 ---------------------------------------------------------------------------

[Link]:

at .(#114:1)

Square[] squares = new Square[5];

for (int i = 0; i < [Link]; i++) {
squares[i] = new Square(1);
squares[i].setSideLength(2*(i+1));
}
printObjectArray(squares);

[Square with side length = 2.00, Square with side length = 4.00, Square with side length = 6.00, Square with side length = 8.00, Squa

The examples above are pretty simple - usually you'll see a NullPointerException because you've only filled an array part of the way or you moved elements around or
something like that.

ArrayindexOutOfBounds

An ArrayIndexOutOfBounds exception is the same idea as a StringIndexOutOfBoundsException. Essentially you are trying to access an index that doesn't exist.

Square sq = squares[10];

---------------------------------------------------------------------------

[Link]: 10

at .(#60:1)

Square sq = squares[-1];

---------------------------------------------------------------------------

[Link]: -1

at .(#60:1)

N-Dimensional Arrays
The arrays we've talked above have all been one dimensional - if you're a math person you can think of them as vectors (or if you're a non-math person just a list of values). However,
arrays can be N-dimensional. Here we'll show 2D arrays, but the syntax can be generalized to N-dimensions.

We can create a 2D array as follows:

int[][] twoDArray = new int[5][10];

This creates a 2D integer array with 5 rows and 10 columns. A 2D array is an "array of arrays". So twoDArray[1] refers to the length 10 integer array at index 1 (position 2).

The semantics of using a 2D array are the same as those of a 1D array.

 for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < twoDArray[i].length; j++) {
twoDArray[i][j] = i*j;
}
}

[Link]("[");
for (int i = 0; i < [Link]; i++) {
[Link](printIntegerArray(twoDArray[i]));
}
[Link]("]");

[
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
[0, 3, 6, 9, 12, 15, 18, 21, 24, 27]
[0, 4, 8, 12, 16, 20, 24, 28, 32, 36]
]

Given some 2D array arr we can use the length field to find the number of rows and columns in arr.

int[][] arr = new int[5][6];

[Link]("arr has %d rows\n", [Link]);
[Link]("arr has %d columns\n", arr[0].length);

arr has 5 rowsarr has 6 columns

We can also create "jagged" arrays using the list initializer method. A jagged 2D array is a 2D array where the rows have different numbers of columns.

int[][] jagged = {
{0, 1, 2, 3},
{4, 5},
{6, 7, 8},
{9, 10, 11, 12}
};

This is pretty uncommon operation.

Arrays are Objects

Arrays are non-primitive types (Objects) so an array variable technically stores a "reference" to the actual data being stored by the array. See the Instantiable classes notes for more
in depth information on this. This means that we can pass an array into a method, alter the composition of the array, and those changes will propagate back to the calling method.

public void attempt_swap(int[] arr) {

int temp = arr[1];
arr[1] = arr[0];
arr[0] = temp;
}

int[] a = {1, 2};

[Link]("Before swap a[0]=%d, a[1]=%d\n", a[0], a[1]);
attempt_swap(a);
[Link]("After swap a[0]=%d, a[1]=%d\n", a[0], a[1]);

Before swap a[0]=1, a[1]=2

After swap a[0]=2, a[1]=1

However, if we set arr to a new array, that change won't propagate to the calling method, because invoking new changes the reference that arr points to.
 public static void changeArray(int[] arr) {
arr = new int[10];
arr[0] = 1;
for (int i = 1; i < [Link]; i++) {
arr[i] = i*arr[i-1];
}
[Link]("During changeArray: arr=%s\n", printIntegerArray(arr));
}

int[] b = {1, 2, 3};

[Link]("Before changeArray: b=%s\n", printIntegerArray(b));
changeArray(b);
[Link]("After changeArray: b=%s\n", printIntegerArray(b));

Before changeArray: b=[1, 2, 3]

During changeArray: arr=[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
After changeArray: b=[1, 2, 3]

Inheritance and Polymorphism

Extending Classes (Inheritance)
Creating our own Objects can be very useful - but what if we want to create related Objects? For example, what if we've written a Cake object and now we want to create a
BrithdayCake object. The BirthdayCake should be very similar to the Cake but with slight alterations. Java allows us to take advantage of these relationships by "extending" classes. If
ClassB "extends" or "inherits from" ClassA, ClassB is said to be a child class of ClassA. ClassB has all of the member variables and methods of ClassA and ClassB can define
additional member variables and methods.

public class Cake {

private boolean isBaked;

public Cake() {
[Link] = false;
}

public boolean isBaked() {

return [Link];
}

public void bake() {

[Link] = true;
[Link]("The cake is baking");
}

public void frost() {

if (![Link]) {
[Link]("You can't frost a raw cake.");
}
else {
[Link]("The cake now has frosting.");
}
}

public String toString() { return "This is a Cake!"; }

}

A BirthdayCake should be able to do evrything a Cake can do (a BirthdayCake should also be able to bake and frost), but we should also be able to put candles on a BirthdayCake.
We can thus make BirthdayCake a child of Cake and add a new method which adds candles to the BirthdayCake.
 public class BirthdayCake extends Cake {

private int candles;

public BirthdayCake() {
super(); // this calls the constructor for Cake
[Link] = 0;
}

public void putCandlesOnCake(int numberOfCandles) {

[Link] += numberOfCandles;
[Link]("Putting " + numberOfCandles + " candles on the birthday cake.");
}

public String toString() { return "This is a Birthday Cake!"; }

}

Now we can create Cake object on which we can call bake and frost and a BirthdayCake object on which we can call bake, frost, and putCandlesOnCake. Note that we cannot
call putCandlesOnCake on a Cake object since that method is only defined for BirthdayCake.

Cake cake = new Cake();

BirthdayCake bCake = new BirthdayCake();

[Link]();
[Link]();

[Link]();
[Link]();

[Link](1);

The cake is baking

The cake is baking
The cake now has frosting.
The cake now has frosting.
Putting 1 candles on the birthday cake.

[Link]();

| [Link]();

cannot find symbol

symbol: method putCandlesOnCake()

Properties of Inheritance
In this example we would say that Cake is the base class and BirthdayCake is a subclass of Cake.

A variable of type BirthdayCake is also of type Cake. So we can create an array Cake[] cakes; and add BirthdayCake objects to it. Additionally bCake instanceof
Cake returns true.
A variable of type BirthdayCake can be cast to Cake. You cannot cast a Cake to a BirthdayCake.
A variable of type BirthdayCake cannot use any private variables or methods in Cake.

[Link]("birthday cake instance of Cake? " + (bCake instanceof Cake));

[Link]("cake instance of BirthdayCake? " + (cake instanceof BirthdayCake));

birthday cake instance of Cake? true

cake instance of BirthdayCake? false
 Cake c = new BirthdayCake();
[Link]("c instanceof BirthdayCake? " + (c instanceof BirthdayCake));

c instanceof BirthdayCake? true

This cell evaluates to true because the object c "knows" it's a BirthdayCake.

[Link](10);

| [Link](10);

cannot find symbol

symbol: method putCandlesOnCake(int)

public static void tenthBirthday(BirthdayCake b) {

[Link](10);
}

tenthBirthday(c);

| tenthBirthday(c);

incompatible types: Cake cannot be converted to BirthdayCake

tenthBirthday((BirthdayCake) c);

Putting 10 candles on the birthday cake.

Method Resolution
In Java there the object AND the compiler "know" the objects type, but sometimes the object and the compiler will disagree.

Cake fraudCake = new BirthdayCake();

Here fraudCake "knows" that it's a BirthdayCake (because its been defined as a BirthdayCake), However, the compiler thinks that fraudCake is a Cake (because its been declared
as a Cake).

This leads to some interesting behavior...

public static String asString(BirthdayCake b) {

return "This is a Birthday Cake!";
}

public static String asString(Cake c) {

return "This is a Cake!";
}

Cake cake = new Cake();

Cake bCake = new BirthdayCake();

[Link]([Link]());
[Link]([Link]());

This is a Cake!
This is a Birthday Cake!
 [Link](asString(cake));
[Link](asString(bCake));

This is a Cake!
This is a Cake!

This behavior is due to Java's binding property.

As mentioned earlier, the compiler and object may disagree on the object's type

Cake fraudCake = new BirthdayCake();

fraudCake knows it's a BirthdayCake but the compiler think's fraudCake is a cake.

So the line:

[Link](10);

won't compile because the compiler sees fraudCake as a Cake which doesn't have a putCandlesOnCake() method.

But the line:

[Link]();

prints This is a BirthdayCake because fraudCake knows it's a BirthdayCake and calls the BirthdayCake version of toString() instead of the Cake version. This is a
decision made at runtime. This means if there's an option as to which instance method can be called on a class, that choice is made as the program is running based on the object's
knowledge of its type.

Furthermore, if we have two methods

public static void doSomething(Cake c) {

[Link]("Cake");
}

public static void doSomething(BirthdayCake b) {

[Link]("BirthdayCake");
}

and we call

doSomething(fraudCake);

the output will be Cake (the cake version will be used) because the compiler sees FraudCake as a Cake. This is a decision made at compile time. This means that the method to
pass an object into is decided by the compiler (as the program is being compiled).

Overriding Methods
So far our subclasses are essentially copies of their base classes with added features. But sometimes we want our subclass to implement the base classes methods in different ways.
We call this overriding the method. \ For example, suppose we're writing an IceCreamCake class that extends Cake. We need to add ice cream to the cake before we can frost it - so
we override the frost method.
public class IceCreamCake extends Cake {

public IceCreamCake() {
super();
}

@Override
public void frost() {
if (![Link]()) {
[Link]("You can't frost a raw cake.");
}
else {
[Link]("Adding ice cream");
[Link]("Adding frosting");
}
}
}

Cake cake = new Cake();

BirthdayCake bCake = new BirthdayCake();
IceCreamCake iCake = new IceCreamCake();

[Link]();
[Link]();
[Link]();

[Link]();
[Link]();

[Link](5);

The cake is baking

The cake is baking
The cake is baking
The cake now has frosting.
The cake now has frosting.
Putting 5 candles on the birthday cake.

[Link]();

Adding ice cream

Adding frosting

[Link](5);

| [Link](5); // FAILS because we can't put candles on a generic cake

cannot find symbol

symbol: method putCandlesOnCake(int)

[Link](5);

| [Link](5);

cannot find symbol

symbol: method putCandlesOnCake(int)

 The @Override keyword is a flag that tells the compiler that the method below overrides a method of the same name, parameters, and return type in the base class. This is not
strictly necessary - you do not need to include the override flag to override a method. However, including the flag allows the compiler to do a simple check to make sure you're doing
what you think you're doing - you may have misspelled a method name, set an incorrect parameter type, etc.

Implementing Interfaces
Extending classes is a very powerful tool, but sometimes we want to create classes that accomplish similar tasks in different ways. For this we use interfaces. An interface is
essentially a blueprint for a class. It defines the methods that we need for our class to be of a specific type.

For example, if I was creating a Car, Truck, Motorcycle, and Bicycle class I may create an interface called Vehicle. Car, Truck, Motorcycle, and Bicycle would all impliment vehicle and
thus would have some methods in common. However, we can choose how we define the methods for each class.

If we define our Vehicle interface:

public interface Shape {

public double getArea();

public double getPerimeter();

public String toString();

}

public class Square implements Shape {

double sideLen;

public Square(double len) {

[Link] = len;
}

public double getArea() {

return [Link]([Link], 2);
}

public double getPerimeter() {

return 4 * [Link];
}

public String toString() {

return "Square";
}

}
public class Circle implements Shape {

double radius;

public Circle(double radius) {

[Link] = radius;
}

public double getArea() {

return [Link] * [Link]([Link], 2);
}

public double getPerimeter() {

return 2 * [Link] * [Link];
}

public String toString() {

return "Circle";
}
}

We can see that Car and Bicycle have the same methods, but they're executed differently. Some notes:

We cannot instantiate a pure interface. However, we can instantiate objects that implement an interface as the interface type. So Shape s = new Shape(); is invalid but
Shape s = new Circle(4); is valid.
We can add any class that implements Shape to an array of Shapes.

Square s = new Square(4);

Circle c = new Circle(3);
Shape shapeS = new Square(2);
Shape shapeC = new Circle(1);

Shape shapeV = new Shape();

| Shape shapeV = new Shape();

Shape is abstract; cannot be instantiated

Shape[] shapes = new Shape[10];

for (int i = 0; i < [Link]; i++) {
if (i % 2 == 0) {
shapes[i] = new Square(i);
}
else {
shapes[i] = new Circle(i);
}
}
for (Shape s : shapes) {
[Link](s);
[Link]([Link]());
[Link]([Link]());
[Link]();
}
 Square
0.0
0.0

Circle
6.283185307179586
3.141592653589793

Square
8.0
4.0

Circle
18.84955592153876
28.274333882308138

Square
16.0
16.0

Circle
31.41592653589793
78.53981633974483

Square
24.0
36.0

Circle
43.982297150257104
153.93804002589985

Square
32.0
64.0

Circle
56.548667764616276
254.46900494077323

Algorithmic Complexity and the Sorting

Problem
Algorithmic Complexity
An algorithm is a self contained set of instructions that accomplishes a task - essentially a method. One of the main problems in Computer Science is determining the efficiency of an
algorithm. If we can develop efficient algorithms to solve common problems, we can greatly speed up common tasks in computing. This could have drastic consequences everything
from software development and encryption to theoretical computer science. In fact - if you've heard of the P vs NP problem - the whole point of the P vs NP problem is to try to find
fast algorithms for problems that we only know how to solve in a slow way. A solution to this problem has wide spreading implications, especially in cryptography / information security
and a successful proof is worth at least \(\$1,000,000\).

Algorithm analysis is pretty complicated and there are whole classes on the subject - here we'll cover the basics. In algorithm analysis we want to know, given the worst possible
input, approximately how long does the algorithm take as a function of the input size. Another way to say this is: "how does the running time of the algorithm grow with the size of the
input?". Consider this algorithm for calculating the sum of an array of integers.
 public static int sum(int[] arr) {
int sum = 0;
for (int i = 0; i < [Link]; i++) {
sum += arr[i];
}
return sum;
}

The first line takes \(1\) step. The for loop iterates \(N\) times where \(N\) is the length of the array. Iterating takes \(1\) step per iteration and the addition takes \(1\) step. Returning
also takes \(1\) step. So we can say that this algorithm takes approximately \(2N + 2\) steps.

Being able to count the exact number of steps of an algorithm is great, but this calculation is tedious (and sometimes impossible) for more complicated algorithms. So generally we
don't care about the exact number of steps, but rather the general form of the fastest growing term in the function representing the number of steps of the algorithm. For example, in
the sum algorithm, the function is \(g(N) = 2N + 2\). The fastest growing term is \(2N\) which increases linearly as \(N\) increases. We can concisely say that this algorithm is \(O(N)\).
This means that the algorithm's growth is upper bounded by a linear function.

This notation is also called Big-O notation. \(f(N) \in O(g(n))\) if there exists some constant \(c\) such that \(f(N) \leq cg(N) \forall N \geq N_0\) where \(N_0\) is small. We would
then say that \(f(N)\) is \(O(g(N))\). If the number of steps taken by an algorithm is of the form \(f(N)\) then we say that the algorithm's time complexity is \(O(g(N))\).

In our sum example, \(f(N) = 2N + 2 \leq 3 * (g(N) = N) \forall \ N > 2\). So \(f(N)\) is \(O(N)\).\\ When examining algorithms we care about which algorithms have the fastest time
complexity. So it's helpful to know the relative efficiency of the common time complexities

\(O(1)\) : Also called constant time - Fastest possible time complexity

\(O(log_2(N))\) : Also called log time
\(O(N)\) : Also called linear time
\(O(N log_2(N))\)
\(O(N^2)\) : Also called quadratic time
\(O(2^N)\) : Also called exponential time - This is the beginning of the "slow algorithms"
\(O(N!)\)

P vs NP
The P vs NP problem is one of the more famous math problems. You may have heard about it in TV shows or movies. You actually know enough about algorithmic complexity now to
understand what the problem is about.

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified (technically, verified in
polynomial time) can also be solved quickly (again, in polynomial time).
Wikipedia

Broken down: There exists a set of problems that we already know how to solve using an algorithm whose time complexity is a polynomial function - this set of problems is called \
(P\). There also exists a set of problems that we know how to verify using an algorithm whose complexity is a polynomial function - this set of problems is called \(NP\). By verify I
mean that, given a proposed solution to the problem I can determine if that solution is correct. If you think about it, any problem that is in \(P\) is also in \(NP\) since if I can solve a
problem quickly I should be able to verify a solution by just solving the problem again. The P vs NP problem asks if we can go the other way - that is, if I have a problem that I can
verify quickly, can I also solve it quickly.
 This problem remains unsolved. A valid solution is worth at least $1 million and has several applications in computer science.

Sorting Algorithms
The sorting problem is very simple to understand. Given a list of values, return a permutation of that list that is sorted. In this case we'll use ascending order, but you can use
descending too.

There are several solutions to this problem with varying time complexities. Here we will consider a few common sorting algorithms.

Note that all of these algorithms are written in Python (as opposed to Java) for simplicity. It would be a good exercise for you to implement them in Java yourself.

I have included some print statements so you can keep track of what the algorithms are doing.

Insertion Sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. Insertion sort assumes that the front of the array is already sorted - it then
selects the first unsorted element and inserts it in its proper position in the sorted section.

def insertion_sort(arr):
n = len(arr)
for i in range(0, n):
print arr
j = i
while j > 0 and arr[j-1] > arr[j]:
# swap arr[j] and arr[j-1]
temp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = temp
j = j - 1
i = i + 1
return arr

insertion_sort([19, 37, 94, 61, 83, 83, 91, 47, 26, 68])

[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 61, 94, 83, 83, 91, 47, 26, 68]
[19, 37, 61, 83, 94, 83, 91, 47, 26, 68]
[19, 37, 61, 83, 83, 94, 91, 47, 26, 68]
[19, 37, 61, 83, 83, 91, 94, 47, 26, 68]
[19, 37, 47, 61, 83, 83, 91, 94, 26, 68]
[19, 26, 37, 47, 61, 83, 83, 91, 94, 68]

[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

The worst case for this algorithm is that the list is initially in reverse order. If we trace through the pseudocode in the worst case we see that insertion sort is \(O(N^2)\) where \(N =
len(A)\).

Selection Sort
Selection sort is very similar to selection sort. It assumes the front of the array is already sorted - it then selects the first unsorted element and swaps it with the smallest element in
the unsorted part of the array.
def selection_sort(arr):
for j in range(len(arr)):
smallest = j
print arr
for i in range(j + 1, len(arr)):
if arr[i] < arr[smallest]:
smallest = i
temp = arr[j]
arr[j] = arr[smallest]
arr[smallest] = temp
return arr

selection_sort([19, 37, 94, 61, 83, 83, 91, 47, 26, 68])

[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 26, 94, 61, 83, 83, 91, 47, 37, 68]
[19, 26, 37, 61, 83, 83, 91, 47, 94, 68]
[19, 26, 37, 47, 83, 83, 91, 61, 94, 68]
[19, 26, 37, 47, 61, 83, 91, 83, 94, 68]
[19, 26, 37, 47, 61, 68, 91, 83, 94, 83]
[19, 26, 37, 47, 61, 68, 83, 91, 94, 83]
[19, 26, 37, 47, 61, 68, 83, 83, 94, 91]
[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

The worst case for this algorithm is that the list is initially in reverse order. If we trace through the pseudocode in the worst case we see that insertion sort is \(O(N^2)\) where \(N =
len(A)\).

Bubble Sort
Bubble sort is a sorting algorithm that takes a slightly different approach than insertion and selection sort. It repeatedly steps through the list to be sorted, compares each pair of
adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
 def bubble_sort(arr):
n = len(arr)
swapped = True
while swapped:
swapped = False
print arr
for i in range(1, len(arr)):
if arr[i-1] > arr[i]:
temp = arr[i-1]
arr[i-1] = arr[i]
arr[i] = temp
swapped = True
return arr

bubble_sort([19, 37, 94, 61, 83, 83, 91, 47, 26, 68])

[19, 37, 94, 61, 83, 83, 91, 47, 26, 68]
[19, 37, 61, 83, 83, 91, 47, 26, 68, 94]
[19, 37, 61, 83, 83, 47, 26, 68, 91, 94]
[19, 37, 61, 83, 47, 26, 68, 83, 91, 94]
[19, 37, 61, 47, 26, 68, 83, 83, 91, 94]
[19, 37, 47, 26, 61, 68, 83, 83, 91, 94]
[19, 37, 26, 47, 61, 68, 83, 83, 91, 94]
[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

The worst case for this algorithm is that the list is initially in reverse order. If we trace through the pseudocode in the worst case we see that insertion sort is \(O(N^2)\) where \(N =
len(A)\).

Merge Sort
So far our sorting algorithms have been sorting in the most naive way - that is, we're sorting in a conceptually easy, but inefficient way. But since sorting is a pretty important
procedure, we want to be able to sort faster than \(O(N^2)\).

Merge Sort is a sorting algorithm that takes advantage of recursion to efficiently sort an array. Merge sort splits the array in half and recursively sorts each unsorted half of the array.
The base case is when the array is of length 1 where the array itself is returned.
 def merge(arr_a, arr_b):
'''
Merges two sorted arrays into one large sort
'''
N = max(len(arr_a), len(arr_b))
ret = list()
a, b = 0, 0
while a < len(arr_a) and b < len(arr_b):
if arr_a[a] <= arr_b[b]:
[Link](arr_a[a])
a+=1
else:
[Link](arr_b[b])
b+=1
while a < len(arr_a):
[Link](arr_a[a])
a+=1
while b < len(arr_b):
[Link](arr_b[b])
b+=1
return ret

def merge_sort(arr):
if len(arr) == 1:
return arr
mid = len(arr) // 2
print arr[:mid], arr[mid:]
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
print left, right
return merge(left, right)

merge_sort([19, 37, 94, 61, 83, 83, 91, 47, 26, 68])

[19, 37, 94, 61, 83] [83, 91, 47, 26, 68]
[19, 37] [94, 61, 83]
[19] [37]
[19] [37]
[94] [61, 83]
[61] [83]
[61] [83]
[94] [61, 83]
[19, 37] [61, 83, 94]
[83, 91] [47, 26, 68]
[83] [91]
[83] [91]
[47] [26, 68]
[26] [68]
[26] [68]
[47] [26, 68]
[83, 91] [26, 47, 68]
[19, 37, 61, 83, 94] [26, 47, 68, 83, 91]

[19, 26, 37, 47, 61, 68, 83, 83, 91, 94]

In an algorithms class you prove that the time complexity of merge sort is \(O(N log_2(N))\). This is significantly better than the previous algorithms which are \(O(N^2)\). We can also
reason this out ourselves. By inspecting the pseudocode for merge we see that it is \(O(N)\). Then each level of merge sort splits the array in half (divides N by 2) and calls merge.
There are \(log_2(N)\) levels of merge sort since it takes that many divisions to get an array of length \(1\) and each level calls an \(O(N)\) operations. Therefore the time complexity is
\(O(N log_2(N))\).

Advanced Sorting Algorithms

It can be proven that the fastest general purpose sorting algorithm is \(O(N log_2(N))\). However, if we know some basic properties of the data (ie if we can assume that they're small
integers) we can reduce the time complexity even further. We don't go over these algorithms in this class, but if you're interested some more advanced sorting algorithms include:
 Quicksort : A more complicated general purpose sorting algorithm. Used as an alternative to merge sort because it requires less extra space.
Counting Sort : A sorting algorithm that can efficiently sort arrays of relatively small integers.
Radix Sort : A sorting algorithm that can efficiently sort data with mixed types (ie sorting alphanumeric sequences).

Searching Algorithms
Sorting algorithms are important because searching through a sorted list is easier than searching through an unsorted array. We can search any array using the Linear Search
algorithm:

public static boolean find(int[] arr, int val) {

for (int i = 0; i < [Link]; i++) {
if (arr[i] == val) {
return i;
}
}
return -1;
}

Since this algorithm uses a single for loop, we can easily see that this is an \(O(N)\) algorithm. However, if the array is very big searching one element at a time can be tedious.
Imagine searching a database of hones in New York for a specific house using this method - that would take a long time even for a computer. If the array was sorted we could be a bit
smarter about this:

public static boolean findSorted(int[] arr, int val) {

for (int i = 0; i < [Link]; i++) {
if (arr[i] == val) {
return i;
}
else if (arr[i] > val) {
return -1;
}
}
return -1;
}

In the above method we assume the array is sorted in ascending order. So as soon as we see a value in arr that's bigger than val, we can exit the method. This method is better
than the more naive approach above since it allows us to stop early if we know we're not going to find the element in the array. However, if we're searching for big values, this
algorithm will still take a long time. In fact, this algorithm is still considered to be \(O(N)\) because in the worst case, this algorithm will still run through the entire for loop. This
algorithm is called Linear Sorted Search.

However, we can use sorting to greatly improve the efficiency of searching arrays. The basic algorithm is as follows:

1. Input arr and val

2. Select some arbitrary index i in arr
3. If arr is empty: return -1
4. Else if arr[i] == val: return i
5. Else if arr[i] < val: we know that val has to be in the section above i. So recursively search the array above index i.
6. Else (if arr[i] > val): we know that val has to be in the section below i. So recursively search the array below index i.

This algorithm is called binary search.

public static int binarySearch(int[] arr, int val) {
return binarySearchHelper(arr, val, 0, [Link])
}

public static int binarySearchHelper(int[] arr, int val, int low, int high) {
if (low >= high) {
return -1;
}
int mid = (high + low) / 2;
if (arr[mid] == val) {
return mid;
}
else if (arr[mid] < val) {
return binarySearchHelper(mid + 1, high);
}
return binarySearchHelper(low, mid);
}

This algorithm has a much better efficiency than Linear Search. Consider searching the array [2, 4, 6, 8, 10, 12, 14, 16] for 1. This algorithm would search

binarySearchHelper(arr, 1, low = 0, high = 8)

mid = 4 -> arr[4] = 8
1 < 8 -> binarySearchHelper(arr, 1, low = 0, high = 4)
mid = 1 -> arr[1] = 4
1 < 4 -> binarySearchHelper(arr, 1, low = 0, high = 1)
mid = 0 -> arr[0] = 2
1 < 2 -> binarySearchHelper(arr, 1, low = 0, high = 0)
low == high -> return -1;

We can see that for an array of length 8, this algorithm took exactly 3 steps. You could prove (and you probably will prove this in an Algorithms class) that this algorithm has a time
complexity of \(O(log_2(N))\). This is much more efficient than the Linear Search algorithms above.

Exceptions
We've learned a lot about programming principles, but so far we've assumed that our users are smart - ie users will always enter the correct input. This is not a reasonable
assumption. When writing programs in the real world we need to be able to handle user error - or at least indicate that an error has occurred. In Java we represent errors using
exceptions. An exception is an object that represents some kind of error.

Exception Handling
An exception is thrown when an error occurs. For example, when you try to call a method on a Null object a NullPointerException is thrown.

We can throw exceptions within our programs buy "throwing" an object of type Throwable.

throw new NullPointerException();

---------------------------------------------------------------------------

[Link]:

at .(#53:1)

If left to it's own devices, a Java program will quit when an exception is thrown. However, usually we don't want that to happen - we don't want our entire program to catch because
the user entered bad input or because we forgot to account for nulls in or array. Thankfully, Java provides control flow structures that allow us to "catch" exceptions at runtime and
recover from them without quitting the program.

We handle exceptions using try/catch/finally blocks.

A try block encases the code that may cause an exception.

A catch block must be associated with a try block and is triggered when an exception of the indicated type is thrown. A catch block encases the code that should be run if an
exception is thrown (usually this would correct the error or print a detailed output). There may be multiple catch blocks for one try block - ie if you run the risk of throwing
multiple exceptions that must be handled differently.
 A finally block is optional and encases code that must be executed whether or not an exception was thrown in the try catch block.

try {
// some code that may throw an exception
}
catch(/* some specific exception */) {
// code to handle the exception
}
catch(/* some other exception */) {

}
// ... as many catch blocks as required
finally { // optional
// code to execute whether or not exception occurs
}

The argument to the catch block should be of the form <exception type> var name. When an exception of the correct type is thrown, the object representing the exception is set
to the variable defined in the catch block argument and can be used inside the catch block for debugging.

String[] arr = new String[10];

try {
String s = arr[0].substring(1);
} catch(NullPointerException e) {
[Link]("We've caught the NullPointerException");
}

We've caught the NullPointerException

All Exceptions extends the Throwable class - the Throwable class impliments a few methods that make debugging easier:

getMessage() : returns the error message from the Throwable.

printStackTrace() : prints the trace of where the error occurred.
toString() : returns a short description of the Throwable.

String[] arr = new String[10];

try {
String s = arr[0].substring(1);
} catch(NullPointerException e) {
[Link]("We've caught the NullPointerException");
[Link]("Message:");
[Link]([Link]());
[Link]("StackTrace:");
[Link]();
[Link](e);
}
 We've caught the NullPointerException
Message:
null
StackTrace:

[Link]
at REPL.$JShell$17.do_it$($JShell$[Link])
at [Link]/[Link].invoke0(Native Method)
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])
at [Link]/[Link]([Link])

[Link]

We can have multiple consecutive catch blocks to catch different types of exceptions. When an exception is thrown, the catch blocks are queried in order to determine which one will
be run - the first matching catch block will be executed.

import [Link];

String arr[] = {"Last", "week", "of", "classes", null};

Scanner kb = new Scanner("1 2 3 4 hello");
try {
for (int i = 0; i < [Link]; i++) {
String s = arr[i].substring(1);
int j = [Link]();
}
}
catch (NullPointerException e) {
[Link](e);
}
catch (InputMismatchException e) {
[Link](e);
}
catch (Exception e) {
[Link](e);
}

[Link]
 import [Link];

String arr[] = {"Last", "week", "of", "classes", null};

Scanner kb = new Scanner("1 2 3 4 hello");
try {
for (int i = 0; i < [Link]; i++) {
int j = [Link]();
String s = arr[i].substring(1);
}
}
catch (NullPointerException e) {
[Link](e);
}
catch (InputMismatchException e) {
[Link](e);
}
catch (Exception e) {
[Link](e);
}

[Link]

Exceptions are just objects and have the same inheritance properties - so exceptions can extend other exceptions. For example, the NullPointerException extends the
RuntimeException. So we have to be careful about how we structure our catch blocks. You want your caught exceptions to decrease in order of specificity so that we can properly
respond to the right exception.

String[] arr = new String[10];

try {
String s = arr[0].substring(1);
}
catch(RuntimeException e) {
[Link]("IDK what happened but it ain't good :(");
}
catch(NullPointerException e) {
[Link]("You didn't fill the array!");
}

| catch(NullPointerException e) {

| [Link]("You didn't fill the array!");

| }

exception [Link] has already been caught

The finally block is run after a try / catch sequence (whether or not the catch block was executed). The point of a finally block is to clean up any problems that may have come up
when handling exceptions.
 String[] arr = new String[10];
try {
String s = arr[0].substring(1);
}
catch(NullPointerException e) {
[Link]("You didn't fill the array!");
}
finally {
[Link]("Executed after the catch: Here we'll clean stuff up");
}

[Link]();

arr[0] = "Hello";
try {
String s = arr[0].substring(1);
}
catch(NullPointerException e) {
[Link]("You didn't fill the array!");
}
finally {
[Link]("Executed even though catch wasn't executed: Here we'll clean stuff up");
}

You didn't fill the array!

Executed after the catch: Here we'll clean stuff up

Executed even though catch wasn't executed: Here we'll clean stuff up

Types of Exceptions
Exception come in two flavors:

Checked exceptions
Unchecked exceptions

Checked Exceptions
Checked exceptions are exceptions that the compiler knows about before hand. Some functions have behaviors that are easy to predict and likely to throw an exceptions. The
compiler forces us to either explicitly handle these exceptions or acknowledge that, even though the xception may occur, we're not going to handle it.

An example of a checked exception is the FileNotFoundException. This exception occurs when we're trying to open a file that doesn't exist - this is a predictable outcome and we
must explicitly catch it or acknowledge its existence and pass the responsibility of handling the exception to the calling method.

import [Link];
import [Link];

public void openFile() {

FileReader fr = new FileReader("[Link]");
}

openFile();

| FileReader fr = new FileReader("[Link]");

unreported exception [Link]; must be caught or declared to be thrown

Explicitly catching the exception

import [Link];
import [Link];
import [Link];

public static void openFile() {

try {
FileReader fr = new FileReader("[Link]");
}
catch (FileNotFoundException e) {
[Link](e);
}
}

openFile();

[Link]: [Link] (No such file or directory)

Acknowledging the exception

import [Link];
import [Link];
import [Link];

public static void openFile() throws FileNotFoundException {

FileReader fr = new FileReader("[Link]");
}

public void main() {

try {
openFile();
}
catch(FileNotFoundException e) {
[Link]("Caught in main");
[Link](e);
}
}

main();

Caught in main
[Link]: [Link] (No such file or directory)

import [Link];
import [Link];
import [Link];

public static void openFile() throws FileNotFoundException {

FileReader fr = new FileReader("[Link]");
}

public void main() throws FileNotFoundException {

openFile();
}

main();
 ---------------------------------------------------------------------------
[Link]: [Link] (No such file or directory)
at [Link]/[Link].open0(Native Method)
at [Link]/[Link]([Link])
at [Link]/[Link].<init>([Link])
at [Link]/[Link].<init>([Link])
at [Link]/[Link].<init>([Link])
at .openFile(#46:1)
at .main(#50:1)
at .(#52:1)

Unchecked Exceptions
Unchecked exceptions are errors that are impossible to predict at compile time. These exceptions don't need to be explicitly caught, but it's important to recognize when they may pop
up and how to handle them because they can wreak havoc on your programs.

ArrayIndexOutOfBoundsException, NullPointerExceptions, and inputMismatchExceptions are examples of unchecked exceptions.

Custom Exceptions
Java has a wide range of built in exceptions that you can use in your programs. But sometimes you'll want to write your own exceptions to fit errors unique to your program. Writing
custom exceptions is just as easy as extending a class - literally all you have to do is write a class that extends an Exception (or a subclass or Exception).

public class MyCustomException extends Exception {

int code;

public MyCustomException(int statusCode) {

[Link] = statusCode;
}

@Override
public String toString() {
return "MyCustomException " + "error code = " + code;
}
}

try {
throw new MyCustomException(10);
}
catch (MyCustomException e) {
[Link](e);
}

MyCustomException error code = 10

Where to go from here

At the end of the year I tend to get questions like "where can I go from here?", "what courses should I take after this?", or "what projects should I work on after this class?". I've
compiled a list of resources for y'all to use to learn more about Computer Science and / or programming.

Degree Programs at Hopkins

BS / BA in Computer Science: CS Major Requirements ([Link]

Minor in Computer Science: CS Minor Requirements ([Link]
BS / BA in Computer Engineering: CE Major Requirements ([Link]
Minor in Robotics: Robotics Minor Requirements ([Link]
Minor in Computer Integrated Surgery: CIS Minor Requirements ([Link]
Minor in Computational Medicine: Comp Medicine Minor Requirements ([Link]

Courses at Hopkins
CS 120 : Intermediate Programming
This course is a programming class in C and C++ that goes more in depth into the fundamentals of procedural and Object Oriented programming. You will cover more
advanced programming concepts like pointers, virtual classes / methods, multiple inheritance, and liked lists.
CS 220 : Data Structures
So far you've used arrays to store and manage data - however that's not always the best way to deal with data. CS 220 teaches you about efficient techniques for storing data
pragmatically. This is one of the classes you must have under your belt if you want to go into software engineering.
CS 271 : Automata and Computation Theory
This course is a basic computer science theory class that teaches you about the mathematical / idealized conception of a computer. It is a proof based class and has Discrete
Mathematics as a pre-requisite.
CS 250 : User Interfaces and Mobile Applications
This is a design based class centered around android application programming (if you're an iPhone user they'll give you an android tablet to play with). In class, you'll learn
about the fundamentals of android application development and you'll work in a team to build your own application from scratch.
Previous course projects have included: a campus wide carpool organization app, a mobile game of assassins, a roommate chores app, and a service app where users can
broadcasts jobs for others to complete.

Note: Most upper level CS classes at Hopkins require CS 120 and CS 220 as prerequisites.

Languages

Java
You've already learned a lot about the Java programming language. However, there's still a lot you can learn about the Java and the cool applications of the language.
Learn advanced Java here! ([Link]
Python
Python is one of the most popular languages in use today. It is used by software developers and scientists, among others to quickly build higher level applications. Python has
a wealth of 3rd party libraries that can be easily integrated into your programs and used for everything from network programming and communicating with hardware over
USB to building a web server, machine learning, game development, and UI design.
Python is slower than other languages like Java, C, and C++, but it's designed to be easy to read and write. Python's readability and flexibility makes it very popular with
newer companies, researchers, educators, and hobbyists alike.
Learn Python here! ([Link]
Javascript
Javascript is the most popular language for frontend web UI/UX development. Javascript is a very polarizing language (some developers love it and others hate it), but if you
want to go into software engineering you should definitely know the basics of Javascript.
Learn Javascript here! ([Link]
C / C++
C (and the object oriented version, C++) transformed computer science. They were the first mainstream "high level" languages and a lot of more modern languages (like Java
and C#) are built based on the syntax of C and C++. These languages are faster than most other high level languages and provide a lot of lower level constructs like pointers
and dynamic memory allocation which make them very useful for lower level applications like device firmwares and network applications. Older companies like Bloomberg LP
wrote a lot of their base code in C++ so knowing these two languages is still important if you're looking at the software industry.
Learn C++ here! ([Link]

Applications

Full Stack Web Development

Web Development (webdev) is a pretty hot field right now. A "full stack" web developer is a developer who can build a web application from the ground up - they can manage
the front end user interface and the back end data storage and algorithms that power the application. A full stack developer needs to know some frontend languages and
frameworks like HTML/CSS and a Javascript framework (JQuerry, AngularJS...) as well as backend server programming languages like Python, Java, or C/C++. There are a
lot of courses out there that will teach you the requisite tools to build your own web applications:
CodeAcademy Web Development ([Link]
Udacity Web Development ([Link]
Mobile Application Development
Like webdev, mobile app development is a pretty in-demand field. A good mobile app developer needs to understand the specific system they're working with (Android vs iOS)
and needs to work with a wide range of technologies to build successful applications:
Udacity Android Development ([Link]
Udacity Advanced Android Development ([Link]
Udacity iOS Development ([Link]
Udacity Advanced iOS Development ([Link]
Machine Learning and Artificial Intelligence
Artificial intelligence is a very popular application of computer science that is used to power everything from social networking apps to disease diagnosis tools. Skilled AI and
ML engineers are hard to come by and are highly sought after by universities and tech companies.
Understanding ML and AI on a deep level requires a very solid background in probability, statistics, and multivariable calculus.
Udacity Intro Machine Learning ([Link]
CodeAcademy Data Science ([Link]
Coursera Deep Learning ([Link]
utm_source=gg&utm_medium=sem&campaignid=904733485&adgroupid=54215108588&device=c&keyword=andrew%20ng&matchtype=p&network=g&devicemodel=&
ZUIHuLxWohXn-QTzytBwdK5xd55byr7Uei34sNrzmJ4GllOAnpxiEMOhoCJyAQAvD_BwE#courses)
UC Berkeley AI Course ([Link]
 Review Problems
Part 1 - Basic Syntax, Printing, Keyboard IO, Control Flow and
Loops, File IO, Helper Methods
1. What is printed? Where is the cursor?

1. [Link]("Hello");
2. [Link](1 + 2 + "abc");
3. [Link]("abc" + 1 + 2);
4. [Link]("abc" + " def\n")
5. [Link]("%d - %d - %s\n", 1, 2, "abc");
6. [Link]("%.2f 03.1f", .1, 9.816);

2. What is the value of z after the following code executes?

1. int z = (20 + 30) * 10 / 3;

2. int x = 5; int y = 10; int z = ++x * y--;

3. Evaluate the following boolean expressions

1. true && (('a' > 'Z') || (10 < -15 + 8)) && !true || !(false || !!true) && false
2. ([Link](2, 3) > [Link](3, 2)) || (10 / 3 > 1000)
3. (10 == 10) && (new String("foo") == new String("foo"))

4. Write a Java program that generates a random integer n in the inclusive range \(-10...30\) and perform the following conditional actions:

If n is odd, print Weird

If n is even and in the inclusive range of 2 to 5, print Not Weird
If n is even and in the inclusive range of 6 to 20, print Weird
If n is even and greater than 20, print Not Weird

5. Write a Java program to detect key presses. If the user pressed number keys( from 0 to 9), the program will print the number that is pressed, otherwise, program will print Not
allowed.

6. Implement division with resolution .1 without using the \(/\) operator.

7. In the decimal number system) an n-digit integer can be written as $10^ * val_ + 10^ * val_ + … + 10^{1} * val_{1} + 10^{0} * val_{0}$ (note that we index digits starting at 0)
where $0 \leq val_ < 10$. So, the number \(1234 = 10^3 * 1 + 10^2 * 2 + 10^1 * 3 + 10^0 * 4\). The binary number system uses 2 instead of 10 as a base and the value of
each digit is either 0 or 1 (ie less than 2). Convert an integer from decimal to a string representing its equivalent in binary.
Examples:

// 10 = 1 * 10^1 + 0 * 10^0
// 10 -> "1010" = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0
[Link]( convertToBinary(10) );
// "1010"
[Link]( convertToBinary(2) );
// "10"
[Link]( convertToBinary(346) );
// "101011010"

8. A random walk is a particular kind of probabilistic simulation that models certain statistical systems such as Brownian motion of molecules. You can think of a one-dimensional
random walk in terms of coin flipping. If you flip a coin as heads \(x \geq .5\) you take a step forward. If you flip a coin as tails \(x < .5\) you take a step back. Write a program
that takes as input the number of steps for a random walk, and the number of times to simulate it "nsim". Calculate the average distance (in steps) from the origin.

9. Write a method called "compressString" which compresses a string such that any consecutive repeated characters are replaced with one of the character and the number of
times the character is repeated. This is also known as "Run length encoding".
Examples:
 [Link]( compressString("aaabbc") );
// "a3b2c"
[Link]( compressString("abc") );
// "abc"
[Link]( compressString("aaqakkaccc") );
// a2qak2a2c3

10. Given an input file [Link] where each line is of the form

<Sex> <Height> <Weight>

Where <Sex> is a string (Male or Female) and <Height> and <Weight> are doubles. Print to the average BMI of each sex to the screen. \(BMI = \frac{Weight * 703}
{Height^2}\)

11. Given the same file ([Link]) output one line per person of the form

<Sex> <BMI> <Z-score>

Note that: \(Zscore_{i} = \frac{(x_{i} - \mu)}{\sigma}\) \(\sigma = \sqrt{ \frac{ \sum_{i=0}^{N}{ (x_{i} - \mu)^2 } } { N-1 } }\) \(\mu = \frac{\sum_{i=0}^{N}{x_{i}}}{N}\)

Calculating the z-score may require reading the file more than once. In a few weeks you'll learn about arrays which will make this process more efficient.

Part 2 - Helper Methods, Recursion, Arrays, Instantiable

Classes
1. Write a Java class named Mirror which contains a main method that collects a line of input from the user and then determines and outputs the longest sequence of characters
at the start of the line which is a mirror image of the sequence of characters at the very end of the line. The mirror image sequences of characters are permitted to overlap.

2. Write a method int[] getTime() that prompts the user to enter the time in hours and then minutes separately, then returns and int array of length two, which holds the
number of hours in the 0th index and minutes in the first index.

3. Suppose you are standing at the base of a staircase and are heading to the top. A small stride will move up one stair, and a large stride advances two. You want to count the
number of ways to climb the entire staircase based on different combinations of large and small strides. For example, a staircase of three steps can be climbed in three
different ways: three small strides, one small stride followed by one large stride, or one large followed by one small.

4. Write a Java class called Stairs which contains a static void method named waysToClimb that takes only an integer value representing a number of stairs and using recursion
prints to the screen each unique way to climb a staircase of that height, taking strides of one or two stairs at a time. The use of loops is not Allowed.
For example, [Link](3) will produce

[1, 1, 1]
[1, 2]
[2, 1]

5. Consider the following incredibly simple methods:

/* Increment the given integer by one */

public static int inc(int a) {
return a + 1;
}
/* Decrement the given integer by one */
public static int dec(int a) {
return a - 1;
}

Using these methods as helpers, implement the following methods recursively without any mathematical operators (+,-,/,%,++,--, etc.).
Comparison operators are allowed.
```Java
/* Compute a + b */
public static int add(int a, int b);
/* Compute a * b */
public static int mul(int a, int b);
/* Compute a ^ b */
public static int pow(int a, int b
```

6. Write a method to check if an array of positive integers is sorted (recursively).

7. Create a class from the following skeleton, and implement the methods:

public class Time {

public final int hours;
public final int minutes;

/* Construct a new time object. Throw an exception

* if hours or minutes are not within a valid range:
* (0-23 for hours, 0-59 for minutes)
* @param hours The number of hours
* @param minutes The number of minutes
*/
public Time(int hours, int minutes);

/* Make a string in `hhmm` format (military time)

public String toMilitaryString();

/* Make a string in `hh:mm (AM/PM)` format

public String toString();

/* Creates a new time which is the sum

* of this and the increment time.
* @param increment The time to add
* @return A new time, which is this + increment.
*/
public Time add(Time increment);

/* Create a new time which represents how much

* time remains until a deadline starting at the current time.
* @param deadline The target time
* @return The duration of time between this time and the deadline
*/
public Time until(Time deadline);

/* Compare two Times.

* @param other The time to compare to this time
* @return An integer representing the relationship:
* -1 if this < other
* 0 if this == other
* 1 if this > other
*/
public int compareTo(Time other);

8. Write a class Dog to represent a dog. You will need to include the following specifications: name, age, and breed. The constructor for the class Dog should take in a String
parameters for the name and breed. It should also set the age to 0. Write a void method called aged that increments age.

9. The class Movie is started below. An instance of class Movie represents a film. This class has the following three class variables:

title , which is a String representing the title of the movie

studio , which is a String representing the studio that made the movie?
rating , which is a String representing the rating of the movie ([Link], PG 13, R, etc)
 public class Movie {

private String title;

private String studio;

private String rating;

// your code goes here
}

Write a constructor for the class Movie , which takes a String representing the title of the movie, a String representing the studio, and a String representing the rating
as its arguments, and sets the respective class variables to these values.
Write a second constructor for the class Movie , which takes a String representing the title of the movie and a String representing the studio as its arguments, and sets
the respective instance variables to these values, but sets the instance variable rating to "PG".
Write a code segment that creates an instance of the class Movie with the title “Black Pantherâ€, the studio “Marvel Studiosâ€, and the rating “PG
13â€. This segment might appear in a main method, for example .
Write a Movie class instance method getPG , which takes an array of base type Movie as its argument, and modifies the array so that at the end of the method, only
those movies in the input array with a rating of "PG" remain. You may assume the input array is full of Movie instances. The returned array need not be full, so the
method will return to the calling method an int representing the number of movies remaining in the array.

10. Write java methods double[] addVectors(double[] a, double[] b) , double[] subtractVectors(double[] a, double[] b) , and double
dotProduct(double[] a, double[] b) to compute the pairwise sum, difference, and dot product of two arrays a and b.

Given arrays a and b, the pairwise sum of a and b is an array c such that \(c[i] = a[i] + b[i]\).
Given arrays a and b, the pairwise difference of a and b is an array c such that \(c[i] = a[i] - b[i]\).
Given arrays a and b, the dot product of a and b is a double c such that \(c = \sum_{i=1}^{n}{a[i]* b[i]}\).

11. Two vectors are linearly dependent if one is a scalar multiple of the other. That is, vectors V and w are linearly dependent if there exists a scalar c such that v = cw . Write a
method boolean areDependent(int[] v, int[] w) that determines if v and w are linearly dependent.

12. Conway’s Game of Life is a cellular automaton game devised by the British Mathematician John Horton Conway. The original game is a zero player game. The evolution
of it depends entirely on its input. Game of life takes place on a 2D grid. Each cell in the grid will be in one of the two possible states, ALIVE (1) or DEAD (0). The birth or
death of the cells is based on the following rules.

A cell switches from DEAD to ALIVE if its surrounded exactly by 3 living cells.
A cell remains alive if its surrounded by 2 or 3 living cells.
A cell switches from being ALIVE to DEAD if its surrounded by more than 3 living cells because of overpopulation.
A cell switches from being ALIVE to DEAD if its surrounded by less than 2 cells because of under population. Assume that the array “wraps aroundâ€ so that each cell is
surrounded by 8 cells, 4 on its sides and 4 on its corners. For example, ie in a 4x4 grid the neighbors of cell 0, 0 are (3, 3), (3, 0), (3, 1), (0, 3), (0, 1), (1, 3), (1, 0), and (1, 1).
Write a function boolean[][] conwaysGame(boolean[][] grid, int numIters); that returns the state of the grid after numIters iterations of Conway’s Game
of Life.

13. Suppose a company represents their employees’ offices as a String[][], where each String represents who occupies a certain cubicle (and empty string means an empty
cubicle). This company wants to rearrange their office to fit a new building. Write a static method String[][] reshape(String[][] offices, int rows, int
cols) which reorganizes the values into a new array with type String[rows][cols] representing the position of each employee in the new building. To save space,
employees should be placed as closely in the new building as possible, so empty cubicles should be skipped over when moving to the new office. If the new office is too small,
the remaining employees can be forgotten (laid off). If the new office is too big, any extra cubicles should have the empty string.
EXAMPLE 1:

reshape(
{
{“Aâ€, “Bâ€, “â€, “Câ€, “Dâ€ },
{“Eâ€, “â€, “â€, “Fâ€, “Gâ€, “Hâ€},
{“â€, “â€, “Iâ€, “Jâ€ },
{“Kâ€}
},
5, 3)
OUT >>
{
{ “Aâ€, “Bâ€, “Câ€ },
{ “Dâ€, “Eâ€, “Fâ€ },
{ “Gâ€, “Hâ€, “Iâ€ },
{ “Jâ€, “Kâ€, “â€ },
{ “â€, “â€, “â€ }
}

EXAMPLE 2:
 reshape(
{
{“Aâ€, “Bâ€, “â€, “Câ€, “Dâ€ },
{“Eâ€, “â€, “â€, “Fâ€, “Gâ€, “Hâ€},
{“â€, “â€, “Iâ€, “Jâ€ },
{“Kâ€}
},
2, 4)
OUT >>
{
{ “Aâ€, “Bâ€, “Câ€, “Dâ€},
{ “Eâ€, “Fâ€, “Gâ€, “Hâ€}
}

14. A rectangular grid is column-magic if each column of grid has the same sum. Write a method boolean isColumnMagid(int[][] grid) that returns true if grid is column-
magic and false otherwise.

Part 3 - Sorting / Searching, Inheritance / Polymorphism, and

Exceptions
15. The Parrot class represents a parrot with an age in years and the ability to learn sounds which it can repeat back when asked to speak. The declaration of the Parrot class is
shown below.

public class Parrot {

/** Constructs a new Parrot object */

public Parrot(String name) {
/* implementation not shown */
}

/** @return the age of the parrot in years */

public int getAge() {
/* implementation not shown */
}

/** Adds sound to the list of sounds the parrot can make
* @param sound the sound to add */
public void train(String sound) {
/* implementation not shown */
}

/** @return a random sound that the parrot can make */

public String speak() {
/* implementation not shown */
}

// There may be instance variables, constructors, and methods that are not shown.
}

A pirate parrot is a type of parrot. A pirate parrot knows how to make the sound “Polly want a crackerâ€ immediately upon birth. A pirate parrot can also steal souls whose age
becomes part of the pirate parrot’s age. A pirate parrot is represented by the PirateParrot class, which you will write.

Assume that the following code segment appears in a class other than PirateParrot. The code segment shows an example of using the PirateParrot class.
PirateParrot polly = new PirateParrot("Polly");

[Link]([Link]()); // prints 0
/* code to increase Polly's age by 5 years */
[Link]([Link]()); // prints 5

[Link](5);
[Link](10);
[Link]([Link]()); // prints 20

[Link]("Walk the plank");

[Link]("Off with his head");

// Polly retires from his life as a pirate to a cushy life as a pet

Parrot myPetPolly = polly;

[Link]([Link]()); // prints 20
[Link]("Time for bed");
[Link]([Link]());
/* prints one of the following, chosen at random:
* Polly want a cracker
* Walk the plank
* Off with his head
* Time for bed
*/

Write the PirateParrot class. Your code must produce the indicated results when invoked by the code given above.

16. What will be the output of the following program?

class A { }

class B extends A { }

class C extends B { }

public class MainClass {

static void overloadedMethod(A a) {

[Link]("ONE");
}

static void overloadedMethod(B b) {

[Link]("TWO");
}

static void overloadedMethod(Object obj) {

[Link]("THREE");
}

public static void main(String[] args) {

C c = new C();
overloadedMethod(c);
}
}

17. Write a program to keep track of the inventory of a vehicle dealership. The dealership can have Cars, Trucks, Motorcycles, and Sports Cars in its Inventory. Use the following
interface and UML diagram to design your class. Cars, Trucks, Motorcycles, and Sports Cars should have a constructor that takes in the brand, cost, and status (for lease or
for sale) of the vehicle. You have some freedom as to how to define these classes, but use object oriented principles in your design. \The Inventory should maintain a list of
Vehicles and should be able to add, remove, list, and printed a list filtered by type of vehicle, status (lease or for sale), or cost.
public interface Vehicle {

public int getNumPassengers();

public double getCost();

public String toString();

}

18. Implement the following methods:

insertionSort(int[] arr)
selectionSort(int[] arr)
bubbleSort(int[] arr)
mergeSort(int[] arr)
19. What is the algorithmic complexity (\(O(...)\)) for:
Searching a 1D array for a specific value?
Searching a 1D sorted array for a specific value?
Multiplying two Y by Y square matrices.
20. Modify the following code to handle incorrect input at the Scanners. The user should be repeatedly prompted to enter input until they enter the correct type of input.

import [Link];

public class Problem19 {

public static void main(String[] args) {

Scanner kb = new Scanner([Link]);
int inputInt = [Link]();
}
}

20. You are writing a Rectangle class with a pubilc void setSideLengths(int h, int w) method. Write a custom exception called
InvalidSideLengthsException that is a subclass of IllegalArgumentException (see documentation
([Link] The InvalidSideLengthException is thrown when the user attempts to set a side
length to a non-positive (\(\leq 0\)) value.

/**
* Constructor for the invalid side length exception.
* @param invalidVal the value of the invalid side length
* @param side 'h' if the side was the "height" of the rectangle and 'c' if the side was the "width"
*/
public InvalidSideLengthException(int invalidVal, char side);

/**
* Returns a message of the form.
* "You entered a value of <val> for the <side-type> of a rectangle."
*/
public void message();