Course Pack
Course Pack
Unit 8: Sequences
8-1: Linked Lists ........................................................................................ 394
8-2: Lists, Stacks, and Queues................................................................... 427
Intensive Introduction to
Computer Science
Course Overview
Programming in Scratch
Welcome to CS S-111!
Computer science is not so much the science of computers
as it is the science of solving problems using computers.
Eric Roberts
A Rigorous Introduction
• Intended for:
• future concentrators who plan to take more
advanced courses
• others who want a rigorous introduction
• no programming background required,
but can also benefit people with prior background
Textbooks
• Required: The CSCI S-111 Coursepack
• contains all of the lecture notes
• print it and mark it up during lecture
• See the course website for contact info. and office hours
• Policies:
• 10% penalty for submissions that are one day late
• please don't request an extension unless it's an emergency!
• grading
• Please read the syllabus carefully and make sure that you
understand the policies and follow them carefully.
Programming
• Programming involves expressing an algorithm in a form that
a computer can interpret.
Scratch
• A simple but powerful graphical programming language
• developed at the MIT Media Lab
• makes it easy to create animations, games, etc.
• Sprites perform actions and interact with each other on the stage.
the stage
building
blocks
for
programs/
scripts
forms
• To create a variable:
note: you must drag a variable into place, not type its name
• Boolean operators:
• They have an input area with pointed edges for the condition.
Programming in Java
• For now:
• we'll limit ourselves to writing a single class
• you can just think of a class as a container for your program
• Notes:
• the class begins with a header:
public class name
• the code inside the class is enclosed in curly braces
({ and })
Methods
• A method is a collection of instructions that perform
some action or computation.
• Notes:
• the main method always begins with the same header:
public static void main(String[] args)
• the code inside the method is enclosed in curly braces
• each statement typically ends with a semi-colon
• the statements are executed sequentially
Identifiers
• Used to name the components of a Java program like
classes and methods.
• Rules:
• must begin with a letter (a-z, A-Z), $, or _
• can be followed by any number of letters, numbers, $, or _
• spaces are not allowed
• cannot be the same as a keyword – a word like class
that is part of the language itself (see the Resources page)
Printing Text
public class HelloWorld {
public static void main(String[] args) {
System.out.println("hello, world");
}
}
The next text to be printed will begin just after this text –
on the same line.
• For example:
System.out.print("I ");
System.out.print("program ");
System.out.println("with class!");
is equivalent to
System.out.println("I program with class!");
Escape Sequences
• Problem: what if we want to print a string that includes
double quotes?
• example: System.out.println("Jim said, "hi!"");
• this won’t compile. why?
• Other examples:
• \n a newline character (goes to the next line)
• \t a tab
• \\ a backslash
Procedural Decomposition
(How to Use Methods to Write Better Programs)
+-----
|
+----
|
+-----
+-----
|
+----
|
+-----
Code Duplication
public class BlockLetters {
public static void main(String[] args) {
System.out.println(" -----");
System.out.println(" | \\");
System.out.println(" | |");
System.out.println(" | /");
System.out.println(" -----");
System.out.println();
System.out.println(" +-----");
System.out.println(" |");
System.out.println(" +----");
System.out.println(" |");
System.out.println(" +-----");
System.out.println();
System.out.println(" +-----");
System.out.println(" |");
System.out.println(" +----");
System.out.println(" |");
System.out.println(" +-----");
}
}
Calling a Method
• The statement
writeE();
is known as a method call.
System.out.println("hello");
System.out.println("world");
System.out.println();
System.out.println(" +-----");
System.out.println();
System.out.println(" |");
writeE(); .
.
.
System.out.println();
System.out.println(" +-----");
.
.
.
write DEE
write D write E
printSong
printHalfRefrain
Code Reuse
• Once we have a set of methods, we can use them to solve
other problems.
Comments
• Comments are text that is ignored by the compiler.
• Two types:
1. line comments: begin with //
• compiler ignores from // to the end of the line
• examples:
// this is a comment
System.out.println(); // so is this
Comments (cont.)
• Put comments:
• at the top of each file, naming the author and explaining
what the program does
• at the start of every method other than main,
describing its behavior
• inside methods, to explain complex pieces of code
(this will be more useful later in the course)
Analysis/Specification
Design
Implementation
Testing/Debugging
Step 3: Implementation
• Translate your design into the programming language.
pseudocode code
• We need to learn more Java before we can do this!
Analysis/Specification
Design
Implementation
Testing/Debugging
• They include:
• string literals: "Your total in cents is:"
• are surrounded by double quotes
• numeric literals: 25 3.1416
• commas are not allowed!
quarters 10
• They include:
• literals, which evaluate to themselves
• variables, which evaluate to the value that they represent
• combinations of literals, variables, and operators:
25*quarters + 10*dimes + 5*nickels + pennies
operands
of the * operator operands
of the + operator
Evaluating Expressions
• With expressions that involve more than one mathematical
operator, the usual order of operations applies.
• example:
3 + 4 * 3 / 2 – 7
=
=
=
=
System.out.println(4); // output: 4
System.out.println(cents);
System.out.println("cents");
System.out.println(10*3 + 5*7);
System.out.println(65);
Data Types
• A data type is a set of related data values.
• examples:
• integers
• strings
• characters
• double
• used for real numbers (ones with a fractional part)
• examples: 3.1416 -15.2
• used for any numeric literal with a decimal point,
even if it's an integer:
5.0
• also used for any numeric literal written in scientific notation
3e8 -1.60e-19
more generally:
p
n x 10 is written n e p
• examples:
int count; // will hold an integer
double area; // will hold a real number
Assignment Statements
• Used to give a value to a variable.
• Syntax:
variable = expression;
= is known as the assignment operator.
• Examples:
int quarters = 10; // declaration plus assignment
• Examples:
int quarters = 10;
• Examples: undefined
int num1;
int num2 = 120; num1 ? num2 120
after the assignment at left, we get:
String Concatenation
• The meaning of the + operator depends on the types of
the operands.
• Note that the type cast occurs after the variable is replaced
by its value.
• It does not change the value that is actually stored in the variable.
• in the example above, pointsEarned is still 13
Type Conversions
• Java will automatically convert values from one type
to another provided there is no potential loss of information.
variable of value of
type double type int
variable of value of
type int type double
• Example:
double d = 1 / 3;
= 0; // uses integer division. why?
= 0.0;
• Examples:
• each class is a block
• each method is a block
Variable Scope
• The scope of a variable is the portion of a program
in which the variable can be used.
== equal to sum == 10
(don't confuse with = ) firstChar == 'P'
System.out.print(dollars);
if (dollars == 1) {
System.out.print(" dollar, ");
} else {
System.out.print(" dollars, ");
}
}
}
Classifying Bugs
• Syntax errors
• found by the compiler
• occur when code doesn't follow the rules of the
programming language
• examples?
• Logic errors
• the code compiles, but it doesn’t do what you intended
it to do
• may or may not cause the program to crash
• called runtime errors if the program crashes
• often harder to find!
if (cents % 100 == 0) {
int dollars = cents / 100;
System.out.println(dollars + " dollars");
} else {
int dollars = cents / 100;
cents = dollars % 100;
System.out.println(dollars + " dollars and "
+ cents + " cents");
}
}
}
Binary to Decimal
• Number the bits from right to left
• example: 0 1 0 1 1 1 0 1
b7 b6 b5 b4 b3 b2 b1 b0
• For each bit that is 1, add 2n, where n = the bit number
• example: 0 1 0 1 1 1 0 1
b7 b6 b5 b4 b3 b2 b1 b0
decimal value = 26 + 24 + 23 + 22 + 20
64 + 16 + 8 + 4 + 1 = 93
Review
• Consider the following code fragments
1) 1000
2) 10 * 5
3) System.out.println("Hello");
4) hello
5) num1 = 5;
6) 2*width + 2*length
7) main
Definite Loops
int i = 0; i 0
for Loops
• Syntax:
for ( initialization ; continuation test ; update ) {
one or more statements
}
initialization:
int i = 0; i i < 7 action
0 true print 1st "|"
is i < 7 no 1 true print 2nd "|"
true?
2 true print 3rd "|"
yes
3 true print 4th "|"
execute body: 4 true print 5th "|"
System.out.println("|");
5 true print 6th "|"
perform update: 6 true print 7th "|"
i++
7 false execute stmt.
execute statement after the loop
after the loop
Practice
• Fill in the blanks below to print the integers from 1 to 10:
• Instead of writing
i = i + 2;
we can use a shortcut and just write
i += 2;
• In general
variable += expression;
is equivalent to
variable = variable + (expression);
Java Shortcuts
• Java offers other shortcut operators as well.
• Example:
public static void myMethod() {
for (int i = 0; i < 5; i++) {
int j = i * 3;
scope of i
System.out.println(j);
}
// the following line won't compile
System.out.print(i);
System.out.println(" values were printed.");
}
• Example:
public static void myMethod() {
int i;
for (i = 0; i < 5; i++) {
int j = i * 3;
System.out.println(j);
} scope
of i
// now this will compile
System.out.print(i);
System.out.println(" values were printed.");
}
• Example:
public static void myMethod() {
for (int i = 0; i < 5; i++) {
int j = i * 3;
scope of
System.out.println(j);
first i
}
• Then we'll modify our code so that the size of the figure
can easily be changed.
• we'll use for loops to allow for this
|::|
|::|
|::| handle of torch
|::|
+--+ bottom of torch
System.out.println();
}
}
System.out.println();
}
}
for ( ; ; ) {
Incremental Development
• We take similar steps to implement methods for the
remaining subtasks.
• The main method just calls the methods for the subtasks:
public static void main(String[] args) {
drawFlame();
drawRim();
drawTop();
drawHandle();
drawBottom();
}
• General syntax:
public static final type name = expression;
• conventions:
• capitalize all letters in the name
• put an underscore ('_') between multiple words
• Use a table!
SCALE_FACTOR width of rim
1 4
2 8
3 12
width of rim = ?
• Scaleable version:
public static void drawRim() {
for (int i = 0; i < 4*SCALE_FACTOR; i++) {
System.out.print("=");
}
System.out.println();
}
System.out.println();
}
}
• However, despite the fact that all of these loops print spaces,
we can't replace them with a method that looks like this:
public static void printSpaces() {
…
Why not?
Parameters
• In order for a method that prints spaces to be useful,
we need one that can print an arbitrary number of spaces.
Parameters (cont.)
public static void printSpaces(int numSpaces) {
for (int i = 0; i < numSpaces; i++) {
System.out.print(" ");
}
}
printSpaces(10);
print5Spaces()
print10Spaces()
printSpaces(parameter)
print20Spaces()
print100Spaces()
…
• Notes:
• the parameters (both formal and actual) are separated
by commas
• each formal parameter must be preceded by its type
• the actual parameters are evaluated and assigned to
the corresponding formal parameters
int sum = a + b;
System.out.print("sum = ");
scope of sum
System.out.println(sum);
A Limitation of Parameters
• Parameters allow us to pass values into a method.
• Example:
int points = 10;
int penalty = opposite(points);
method instruction 1
int num = 10;
method instruction 2
int opp = opposite(num); .
.
.
after the method returns
System.out.println(opp);
return statement
method instruction 1
int num = 10;
method instruction 2
int opp = -10; .
.
.
after the method returns
System.out.println(opp);
return statement
• With such a method, you can still print the value by printing
what the method returns:
System.out.println(opposite(num));
• the return value replaces the method call and is printed
• method definition:
public static ________ coneVol(___________________________) {
• Examples:
round(double value) – returns the result of rounding
value to the nearest integer
abs(double value) – returns the absolute value of value
pow(double base, double expon) – returns the result
of raising base to the expon power
sqrt(double value) – returns the square root of value
• For other examples, use the Java API on the Resources page.
• Syntax:
ClassName.methodName(param1, param2, …)
• Example:
foo
More Practice x | y
public class Mystery {
public static int foo(int x, int y) {
y = y + 1;
x = x + y;
System.out.println(x + " " + y);
return x;
}
public static void main(String[] args) {
int x = 2; main
int y = 0; x | y
y = foo(y, x);
System.out.println(x + " " + y);
System.out.println(foo(x, y));
System.out.println(x + " " + y);
}
}
printTriangle(_________________________________);
printTriangle(_________________________________);
}
}
}
Classes as Blueprints
• We've been using classes as containers for our programs.
• Another analogy:
• class = cookie cutter
objects = cookies
• The API of all classes that come with Java is available here:
https://docs.oracle.com/javase/8/docs/api/
select
the
package
name
(optional)
String
is in
java.lang
select
the
class
name
method header
behavior
charAt Method
• Here's how we can fix this:
String name = "Perry Sullivan";
System.out.println(name.charAt(0) + "" +
name.charAt(6));
System.out.println('P' + "" +
'S');
System.out.println("PS");
• Example:
String warning = "Start the problem set ASAP!";
System.out.println(warning.toUpperCase());
indexOf Method
int indexOf(char ch)
• return type: int
• parameter list: (char ch)
• returns:
• the index of the first occurrence of ch in the string
• -1 if the ch does not appear in the string
• examples:
String name = "Perry Sullivan";
System.out.println(name.indexOf('r'));
System.out.println(name.indexOf('X'));
the signature
• You can also ask the user to enter a value in that window.
• known as console input
Packages
• Java groups related classes into packages.
• Syntax:
variable = new ClassName(parameters);
or
type variable = new ClassName(parameters);
• int nextInt()
• read in an integer and return it
• double nextDouble()
• read in a floating-point value and return it
• String nextLine()
• read in a "line" of input (could be multiple words)
and return it
• The second line causes the program to pause until the user
types in an integer followed by the [ENTER] key.
import java.util.*;
Breaking Up a Name
• Given a string of the form "firstName lastName", how can
we get the first and last names, without knowing how long it is?
• Code:
}
}
}
nextLine Method
• The nextLine() method does not just read a single token.
Conditional Execution
if (num % 2 == 0) {
System.out.println(num + " is even.");
} else {
System.out.println(num + " is odd.");
}
true false
condition
next statement
• If the first condition is true, it will skip the second and third.
true
condition1 true block 1
false
true
condition2 true block 2
false
...
false
false block
next statement
• One of the conditions must be true, so we can omit the last one:
if (num < 0) {
System.out.println("The number is negative.");
} else if (num > 0) {
System.out.println("The number is positive.");
} else {
System.out.println("The number is zero.");
}
String grade;
if (score >= 90) {
grade = "A";
}
if (score >= 80) {
grade = "B";
}
if (score >= 70) {
grade = "C";
}
if (score >= 60) {
grade = "D";
}
if (score < 60) {
grade = "F";
}
• Why?
• pattern 2:
for (int i = 1; i <= n; i++) {
statements to repeat
}
assuming that the user enters these grades: 80, 90, 84.
numGrades = 3
return 0;
}
• Example:
Scanner console = new Scanner(System.in);
...
System.out.print("Do you have another (y/n)? ");
char choice = console.next().charAt(0);
if (choice == 'y') { // this works just fine
processItem();
} else if (choice == 'n') {
return;
} else {
System.out.println("invalid input");
}
• Example:
Scanner console = new Scanner(System.in);
System.out.print("regular or diet? ");
String choice = console.next();
if (choice == "regular") { // doesn't work
processRegular();
} else {
...
}
equalsIgnoreCase()
• We often want to compare two strings without paying attention
to the case of the letters.
• example: we want to treat as equivalent:
"regular"
"Regular"
"REGULAR"
etc.
...
} else {
// handle people 25 and older
System.out.print("orchestra or balcony? ");
String choice = console.next();
int price;
if (choice.equalsIgnoreCase("orchestra")) {
price = 50;
} else {
price = 30;
}
System.out.println("The price is $" + price);
}
• Example:
double sum = 0.1 + 0.1 + 0.1 + 0.1 + 0.1;
sum = sum + 0.1 + 0.1 + 0.1 + 0.1 + 0.1;
System.out.println(sum);
// get 0.9999999999999999!
Indefinite Loops
and Boolean Expressions
Steps:
1. evaluate the test false
test
condition
2. if it's false, skip the
statements in the body
true
3. if it's true, execute the
statements in the body,
and go back to step 1 body of the loop
next statement
false false
condition
test condition
test
true true
• In our example:
int mult = num; // initialization
while (mult < 100) {
System.out.print(mult + " ");
mult = mult + num; // update
}
• for loop:
for (initialization; test; update) {
one or more statements
}
• It's generally better to use <, <=, >, >= in a loop condition,
rather than == or !=
do-while Loops
• In general, a do-while statement has the form
do {
one or more statements
} while (test);
Steps:
1. execute the statements
in the body
while
body block
of the loop
2. evaluate the test
3. if it's true, go back to
step 1
(if it's false, continue to the true
test
condition
next statement)
false
next statement
a > 2 a output
before loop
1st iteration
2nd iteration
3rd iteration
4th iteration
Truth Tables
• The logical operators operate on boolean expressions.
• let a and b represent two such expressions
a b a && b
false false false
false true false
true false false
true true true
if (numGrades > 0) {
System.out.print("The average is ");
System.out.println((double)total/numGrades);
}
while (!done) {
System.out.print("Enter grade (or -1 to quit): ");
int grade = console.nextInt();
if (grade == -1) {
done = true;
} else {
total += grade;
numGrades++;
}
}
if (numGrades > 0) {
...
while (true) {
System.out.print("Enter grade (or -1 to quit): ");
int grade = console.nextInt();
if (grade == -1) {
break;
}
total += grade;
numGrades++;
}
Arrays
Collections of Data
• Recall our program for averaging quiz grades:
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
int total = 0;
int numGrades = 0;
while (true) {
System.out.print("Enter a grade (or -1 to quit): ");
int grade = console.nextInt();
if (grade == -1) {
break;
}
total += grade;
numGrades++;
}
if (numGrades > 0) {
...
}
• General syntax:
type[] array = new type[length];
where
type is the type of the individual elements
array is the name of the variable used for the array
length is the number of elements in the array
• Examples:
grades[0] accesses the first element
grades[1] accesses the second element
grades[5] accesses the sixth element
0 1 2 3 4 5 6 7 8
no such
0 0 0 0 0 0 0 0
element!
• Other examples:
double[] heights = {65.2, 72.0, 70.6, 67.9};
boolean[] isPassing = {true, true, false, true};
• General pattern:
for (int i = 0; i < array.length; i++) {
do something with array[i];
}
grades array: 7 8 9 6 10 7 9 5
i grades[i] max
7
1 8 8
2 9 9
3 6 9
4 10 10
5 7 10
...
• Example:
int[] grades = new int[8];
might give the following picture:
memory location: 2000
grades 2000 0 0 0 0 0 0 0 0
grades 0 0 0 0 0 0 0 0
temps
first
output:
numTemps
last
s1
"hello, world"
s2
grades 7 8 9 6 10 7 9 5
other
• Given the lines of code above, what will the lines below print?
other[2] = 4;
System.out.println(grades[2] + " " + other[2]);
list2
list2
list2
list2 0 0 0
Copying an Array
• To actually create a copy of an array, we can:
• create a new array of the same length as the first
• traverse the arrays and copy the individual elements
• Example:
int[] grades = {7, 8, 9, 6, 10, 7, 9, 5};
int[] other = new int[grades.length];
for (int i = 0; i < grades.length; i++) {
other[i] = grades[i];
}
grades 7 8 9 6 10 7 9 5
other 7 8 9 6 10 7 9 5
_____________________;
}
public static void main(String[] args) {
...
int maxNumGrades = console.nextInt();
int[] grades = new int[maxNumGrades];
... // code to read in the values
System.out.println("max grade = " +
________________________________);
return max;
}
public static void main(String[] args) {
...
int maxNumGrades = console.nextInt();
int[] grades = new int[maxNumGrades];
... // code to read in the values
maxGrade(grades);
System.out.println("max grade = " + max);
return max;
}
public static void main(String[] args) {
...
int maxNumGrades = console.nextInt();
int[] grades = new int[maxNumGrades];
... // code to read in the values
int max = maxGrade(grades);
System.out.println("max grade = " + max);
0 1 2 3 4 5 6 7 8 9 10
counts 0 0 0 0 0 1 1 2 1 2 1
• The size of the counts array should be one more than the
maximum value being counted:
int max = maxGrade(grades);
int[] counts = new int[max + 1];
0 1 2 3 4 5 6 7 8 9 10
counts
• Let's trace through this code for the grades array shown above:
for (int i = 0; i < grades.length; i++) {
counts[grades[i]]++;
}
main main
a a
1 2 3 3 6 9
• Example: 0 1 2 3 4 5 6 7
arr 35 6 19 23 3 47 9 15
arr 35 6 47 23 3 19 9 15
• What's wrong with this code for swapping the two values?
arr[2] = arr[5];
arr[5] = arr[2];
• it gives this:
arr 35 6 47 23 3 47 9 15
0 1 2 3 4 5 6 7
arr 35 6 47 23 3 47 9 15
temp 19
0 1 2 3 4 5 6 7
arr 35 6 47 23 3 19 9 15
temp 19
numSold 15 8 19 2 5 8 11 18 7 16
numSold 15 8 19 2 5 8 11 18 7 16
numSold 0 15 8 19 2 5 8 11 18 7
numSold 15 8 19 2 5 8 11 18 7 16
numSold 15 15 19 2 5 8 11 18 7 16
numSold 15 15 15 2 5 8 11 18 7 16
for ( ; ; ) {
numSold 0 15 8 19 2 5 8 11 18 7
Arrays of Objects
• We can use an array to represent a collection of objects.
• Example:
String[] suitNames = {"clubs", "spades",
"hearts", "diamonds"};
suitNames
number number
of rows of columns
An Array of Arrays
• A 2-D array is really an array of arrays!
scores
15 8 3 16 12 7 9 5
6 11 9 4 1 5 8 13
17 3 5 18 10 6 7 21
8 14 13 6 13 12 8 4
1 9 5 16 20 2 3 9
foo
11 22 33
10 20 30 40
1 2
File Processing
• Scanner methods:
next()
nextInt()
nextDouble()
nextLine()
• Basic structure:
Scanner input = new Scanner(new File(filename));
while (input.hasNextLine()) {
String line = input.nextLine();
// code to process the line goes here…
}
• hasNextLine() returns:
• true if there's at least one more line of the file to be read
• false if we've reached the end of the file
• Basic approach:
• ask the user for the school of interest (the target school)
• read one line at a time from the file
• split the line into fields
• if the field corresponding to the school name matches
the target school, print out the other fields in that record
Splitting a String
• The String class includes a method named split().
• breaks a string into component strings
• takes a parameter indicating what delimiter should be
used when performing the split
• returns a String array containing the components
• Example:
> String sentence = "How now brown cow?";
> String[] words = sentence.split(" ");
> words[0]
"How"
> words[1]
"now"
> words[3]
"cow?"
> words.length
4
• Initial pseudocode:
while (there is another course in the file) {
read the line corresponding to the course
split it into an array of fields
average the fields for the enrollments
print the course name and average enrollment
}
• Example: 125
• the text representation of 125 stores the string "125" –
i.e., the characters for the individual digits in the number
'1' '2' '5' 49 50 53
Recursion
number otherNumber
• For each method call, a new frame is added to the top of the
stack.
public class Foo {
public static int y(int i) {
int j = i * 3;
return j; i 8
} y(8)
j 24
public static int x(int i) {
int j = i - 2;
return y(i + j); i 5
} x(5)
public static void j 3
main(String[] args) {
System.out.println(x(5));
args
}
}
Iteration
• Whenever we've encountered a problem that requires repetition,
we've used iteration - i.e., some type of loop.
Infinite Recursion
• We have to ensure that a recursive method will eventually
reach a base case, regardless of the initial input.
• expr1 || expr2
if expr1 evaluates to true, expr2 is not evaluated,
because we already know that expr1 || expr2 is true
• example from the last slide:
if (str == null || str.equals("")) {
return;
}
// if str is null, we won't check for empty string.
// This prevents a null pointer exception!
numOccur('r', "recurse")
numOccur('r', "recurse")
c = 'r', s = "recurse"
return ___________________;
} else {
return ___________________;
}
}
}
Common Mistake
• This version of the method does not work:
public static int numOccur(char c, String s) {
if (s == null || s.equals("")) {
return 0;
}
int count = 0;
if (s.charAt(0) == c) {
count++;
}
numOccur(c, s.substring(1));
return count;
}
• Rule of thumb:
• if it's easier to formulate a solution recursively, use recursion,
unless the cost of doing so is too high
• otherwise, use iteration
isPal("modem")
• what is its solution?
• what is the next smaller subproblem?
• what is the solution to that subproblem?
• how can we use the solution to the subproblem...?
What is our one step?
return __________;
} else if (_________________________________) {
return __________;
} else {
}
}
Classes as Blueprints:
How to Define New Types of Objects
Types of Decomposition
• When writing a program, it's important to decompose it into
manageable pieces.
Rectangle Objects
• Java comes with a built-in Rectangle class.
• in the java.awt package
width 50
height 30
• Non-static:
public void grow(int dWidth, int dHeight) {
this.width += dWidth;
this.height += dHeight;
}
• no explicit parameters
r2 x 50
are needed because
the necessary info. y 100
is in the objects' fields! width 20
height 80
• Examples of mutators:
• grow() in our Rectangle class
• Examples of accessors:
• area() in our Rectangle class
• String methods: length(), substring(), charAt()
Defining a Constructor
• Our current client program has to use several lines
to initialize each Rectangle object:
Rectangle r1 = new Rectangle();
r1.x = 10; r1.y = 20;
r1.width = 100; r1.height = 50;
r1 x 0 r1 x 10 r1 x 10
y 0 y 20 y 20
width 0 width 100 width 100
height 0 height 50 height 50
Encapsulation
• Encapsulation is one of the key principles of object-oriented
programming.
x 10
y 100
rect1 width 20
x 10
height 55
rect2 y 100
width 20
height 55
width 20
height 55
• Mutators:
• usually have one or more parameter
• usually have a void return type
• often have a name that begins with "set"
• examples: setLocation(), setWidth()
• but not always: grow(), scale()
r1
x 10
grow
this y 20
dHeight 10 height 50
• The method uses this to access the fields in the called object.
• even if the code doesn't explicitly use it
width += dWidth; this.width += dWidth;
height += dHeight; this.height += dHeight;
x 10
y 20
width 100
x 50
height 50
main y 100
r1 width 20
r2 height 80
grow x 10
this
y 20
dWidth 50
width 100
dHeight 10 x 50
height 50
main y 100
r1 width 20
r2 height 80
x 10
y 20
width 150
x 50
height 60
main y 100
r1 width 20
r2 height 80
grow x 10
this
y 20
dWidth 5
width 150
dHeight 30 x 50
height 60
main y 100
r1 width 20
r2 height 80
x 10
y 20
width 150
x 50
height 60
main y 100
r1 width 25
r2 height 110
grow x 10
this
y 20
dWidth 5
width 150
dHeight 30 x 50
height 60
main y 100
r1 width 25
r2 height 110
• Examples include:
• all of the grades on a given assignment/exam
• a simple database of song info (e.g., in a music player)
grades 7 8 9 6 10 7 9 5
suitNames
rawScore 26
latePenalty 0
GradeSet Constructor/Methods
• Constructor:
GradeSet(String name, int possPts, int numGrades)
• Accessor methods:
String getName()
int getPossiblePoints()
int getGradeCount()
Grade getGrade(int i) // get grade at position i
double averageGrade(boolean includePenalty)
• Mutator methods:
void setName(String name)
void setPossiblePoints(int possPoints)
void addGrade(Grade g)
Grade removeGrade(int i) // remove grade at posn i
• Let's review the code for these, and write some of them
together.
GradeSet Constructor/Methods
rawScore 95
latePenalty 0
rawScore 95
latePenalty 0
rawScore 80
latePenalty 10
• The Taxi class will have the same fields and methods
as the Automobile class.
Inheritance
• To avoid redefining all of the Automobile fields and methods,
we specify that the Taxi class extends the Automobile class:
public class Taxi extends Automobile {
• The Taxi class will inherit the fields and methods of the
Automobile class.
• it doesn't have to redefine them
• Example: our Taxi class can define its own toString method:
public String toString() {
return "Taxi (id = " + this.taxiID + ")";
}
• it overrides the toString method inherited from Automobile
• The classes for these other vehicles should not inherit from
Automobile. Why not?
Vehicle
Terminology
• When class C extends class D (directly or indirectly):
• class D is known as a superclass or base class of C
• super – comes above it in the hierarchy
• class C is known as a subclass or derived class of D
• sub – comes below it in the hierarchy
• Examples:
• Automobile is a superclass of Vehicle
Taxi and Limosine
• Taxi is a subclass of
Automobile and Vehicle Automobile
Limousine Taxi
Object
output:
System.out.println(sq); square with 40-cm sides
Object
Vehicle
has-a Relationships
• Another type of relationship is a has-a relationship.
• one type of object "owns" another type of object
• example: a driver has a vehicle
• Example:
• let's say that a company has a collection of vehicles
of different types
• we can store all of them in an array of type Vehicle:
Vehicle[] fleet = new Vehicle[5];
fleet[0] = new Automobile("Honda", "Civic", …);
fleet[1] = new Motorcycle("Harley", ...);
fleet[2] = new TractorTrailer("Mack", ...);
fleet[3] = new Taxi("Ford", …);
fleet[4] = new Truck("Dodge", …);
Vehicle
g1.method1();
E F
g1.method2(); method2 method2
method3
g1.method3();
g2.method1(); H
method1
g2.method2();
g2.method3();
• We will also:
• study algorithms related to these data structures
• learn how to compare data structures & algorithms
• Goals:
• learn to think more intelligently about programming problems
• acquire a set of useful tools and techniques
84 PORTLAND 49
CONCORD 74 PORTSMOUTH
83
63 54
134 44
ALBANY WORCESTER BOSTON
42
49
PROVIDENCE
NEW YORK 185
...
}
• For each method call, a new stack frame is added to the top
of the stack.
public class Foo {
public static int x(int i) {
int j = i - 2;
j 6
if (i >= 6) { i 8 x(8)
return i;
} return addr
return x(i + j); j 3
}
public static void i 5 x(5)
main(String[] args) {
return addr
System.out.println(x(5));
} args
}
public ArrayBag() {
this.items = new Object[DEFAULT_MAX_SIZE];
this.numItems = 0;
}
public ArrayBag(int maxSize) {
...
}
• The second one allows the client to specify the max # of items.
public ArrayBag() {
this.items = new Object[DEFAULT_MAX_SIZE];
this.numItems = 0;
}
public ArrayBag(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException(
"maxSize must be > 0");
}
this.items = new Object[maxSize];
this.numItems = 0;
}
...
}
maxSize 2
b2
b1
args
items null null
…
numItems 0
"hello, world"
b "hello, world"
message
args …
b "hello, world"
message
args …
b "hello, world"
message
args …
b "hello, world"
message
args …
A Type Mismatch
• Here are the headers of two ArrayBag methods:
public boolean add(Object item)
public Object grab()
Recursion Revisited;
Recursive Backtracking
• Examples:
• 210 = 2*2*2*2*2*2*2*2*2*2 = 1024
• 105 = 10*10*10*10*10 = 100000
Example: power1(5,3)
x5 n0
return 1
x5 n1 x5 n1 x5 n1
return 5*1
x5 n2 x5 n2 x5 n2 x5 n2 x5 n2
return 5*5
x5 n3 x5 n3 x5 n3 x5 n3 x5 n3 x5 n3 x5 n3
return 5*25
time
return __________;
} else { // recursive case
____________________________________
} else {
____________________________________
}
}
}
col 0: safe
• row 1: Q Q Q
Q Q Q
col 0: same col col 1: same diag col 2: same col/diag col 3: same diag
• row 3: Q Q Q Q
Q Q Q Q
Q Q Q Q
Q Q Q Q
col 0: same col/diag col 1: same col/diag col 2: same diag col 3: same col/diag
• Backtrack to row 2:
Q Q Q
Q Q Q
Q Q
• row 1: Q Q Q Q
Q Q Q Q
• row 2: Q
Q
Q
• row 3: Q Q Q
Q Q Q
Q Q Q
Q Q Q
A solution!
//other fields
false false false false
//other fields
false false false false
Recursive-Backtracking Method
private boolean findSolution(int row) {
if (row == this.board.length) {
this.displayBoard();
return true;
}
for (int col = 0; col < this.board.length; col++) {
if (this.isSafe(row, col)) {
this.placeQueen(row, col);
if (this.findSolution(row + 1)) {
return true;
}
this.removeQueen(row, col);
}
}
return false;
}
Q
Once we place a queen in the last row… Q
Q
…and hit the base case! Q
Q
...and all the earlier calls also return true! Q
0 0 1 2 3 0 3 2 1 0
1 1 2 3 4 1 4 3 2 1
2 2 3 4 5 2 5 4 3 2
3 3 4 5 6 3 6 5 4 3
not allowed!
A First Look at
Sorting and Algorithm Analysis
• Ground rules:
• sort the values in increasing order
• sort “in place,” using only a small amount of additional storage
• Terminology:
• position: one of the memory locations in the array
• element: one of the data items stored in the array
• element i: the element at position i
stack heap
arr
15 7 ...
0 1
1 2 3 4
2 6 15 12 44
0 1 2
2 3 4 0 1 2 3
3 4
2 4 15 12 66 2 4 6 12 15
Selecting an Element
• When we consider position i, the elements in positions
0 through i – 1 are already in their final positions.
0 1 2 3 4 5 6
example for i = 3: 2 4 7 21 25 10 17
Time Analysis
• Some algorithms are much more efficient than others.
(n - 1)((n - 1) 1)
=
2
(n - 1)n 2
= C(n) = n 2 - n 2
2
Big-O Notation
• We specify the largest term using big-O notation.
• e.g., we say that C(n) = n2/2 – n/2 is O(n2)
140
120
100 n^2
n log n
80
n
60 log n
40
20
0
0 1 2 3 4 5 6 7 8 9 10 11 12
n
• Moves: after each of the n-1 passes, the algorithm does one swap.
• n-1 swaps, 3 moves per swap
• M(n) = 3(n-1) = 3n-3
• selection sort performs O(n) moves.
g(n) = n2
n
• Big-O notation specifies an upper bound on a function f(n)
as n grows large.
• Example:
• 3n – 3 is O(n2) because 3n – 3 <= n2 for all n >= 1
• 3n – 3 is also O(2n) because 3n – 3 <= 2n for all n >= 1
Insertion Sort
• Basic idea:
• going from left to right, “insert” each element into its proper
place with respect to the elements to its left
• “slide over” other elements to make room
• Example:
0 1 2 3 4
15 4 2 12 6
4 15 2 12 6
2 4 15 12 6
2 4 12 15 66
2 4 6 12 15
• Sorting by selection:
• consider position 0: find the element (2) that belongs there
• consider position 1: find the element (9) that belongs there
• …
• Sorting by insertion:
• consider the 12: determine where to insert it
• consider the 15; determine where to insert it
• …
Inserting an Element
• When we consider element i, elements 0 through i – 1
are already sorted with respect to each other.
0 1 2 3 4
example for i = 3: 6 14 19 9 …
• To insert element i:
• make a copy of element i, storing it in the variable toInsert:
0 1 2 3
toInsert 9 6 14 19 9
int j = i;
do {
arr[j] = arr[j-1];
j = j - 1;
} while (j > 0 && toInsert < arr[j-1]);
arr[j] = toInsert;
}
}
}
}
Shell Sort
• Developed by Donald Shell
• Shell sort uses larger moves that allow elements to quickly get
close to where they belong in the sorted array.
• three subarrays:
1) elements 0, 3, 6 2) elements 1, 4, 7 3) elements 2 and 5
27 3 10 36 18 20 9 8
27 3 10 36 18 20 9 8
9 3 10 27 18 20 36 8
9 3 10 27 8 20 36 18
• Our version uses values that are one less than a power of two.
• 2k – 1 for some k
• … 63, 31, 15, 7, 3, 1
• can get to the next lower increment using integer division:
incr = incr/2;
int j = i;
do {
arr[j] = arr[j-incr];
j = j - incr;
} while (j > incr-1 &&
toInsert < arr[j-incr]);
Bubble Sort
• Perform a sequence of passes from left to right
• each pass swaps adjacent elements if they are out of order
• larger elements “bubble up” to the end of the array
• Example: 0 1 2 3 4
28 24 37 15 5
after the first pass: 24 28 15 5 37
after the second: 24 15 5 28 37
after the third: 15 5 24 28 37
after the fourth: 5 15 24 28 37
• Nested loops:
• the inner loop performs a single pass
• the outer loop governs:
• the number of passes (arr.length - 1)
• the ending point of each pass (the current value of i)
• M(n) =
• in the best case:
• Running time:
• C(n) is always O(n2), M(n) is never worse than O(n2)
• therefore, the largest term of C(n) + M(n) is O(n2)
Sorting II:
Divide-and-Conquer Algorithms,
Distributive Sorting
Quicksort
• Like bubble sort, quicksort uses an approach based on swapping
out-of-order elements, but it’s more efficient.
12 8 14 4 6 13 6 8 4 14 12 13
7 15 4 9 6 18 9 12
partition using a pivot of 9
7 9 4 6 9 18 15 12
all values <= 9 all values >= 9
4 8 14 12 6 18 4 8 14 12 6 18
pivot = 18
i j
• Find: 4 5 2 13 18 24 20 19
and now the indices are equal, so we return j.
i j
• Subarrays: 4 5 2 13 18 24 20 19
• Find: 4 14 7 5 2 19 26 6
• Find: 8 10 7 15 20 9 6 18
split
first (j) last
… 7 9 4 6 9 18 15 12 …
1 1 1 1 1 1 … 1 1 1 1 0
1 n-1 n-1
1 n-2 n-2
1 n-3 n-3
....... ...
1 2 2
1 1
n
• C(n) = i = O(n2). M(n) and run time are also O(n2).
i 2
Mergesort
• The algorithms we've seen so far have sorted the array in place.
• use only a small amount of additional memory
2 5 7 8 9 11 14 24
5 7 9 11
12 8 14 4 6 33 2 27
split 12 8 14 4 6 33 2 27
split 12 8 14 4 6 33 2 27
split 12 8 14 4 6 33 2 27
merge 8 12 4 14 6 33 2 27
merge 4 8 12 14 2 6 27 33
merge 2 4 6 8 12 14 27 33
12 8 14 4 6 33 2 27
split into two 4-element subarrays, and make a recursive call to sort the left subarray:
12 8 14 4 6 33 2 27
12 8 14 4
split into two 2-element subarrays, and make a recursive call to sort the left subarray:
12 8 14 4 6 33 2 27
12 8 14 4
12 8
12 8 14 4
12 8
12
base case, so return to the call for the subarray {12, 8}:
12 8 14 4 6 33 2 27
12 8 14 4
12 8
12 8 14 4
12 8
base case, so return to the call for the subarray {12, 8}:
12 8 14 4 6 33 2 27
12 8 14 4
12 8
12 8 14 4
12 8 8 12
end of the method, so return to the call for the 4-element subarray, which now has
a sorted left subarray:
12 8 14 4 6 33 2 27
8 12 14 4
8 12 14 4
14 4
split it into two 1-element subarrays, and make a recursive call to sort the left subarray:
12 8 14 4 6 33 2 27
8 12 14 4
14 4
14 base case…
8 12 14 4
14 4
12 8 14 4 6 33 2 27
8 12 14 4
14 4
4 base case…
8 12 14 4
14 4
12 8 14 4 6 33 2 27
8 12 14 4
14 4 4 14
12 8 14 4 6 33 2 27
8 12 4 14
12 8 14 4 6 33 2 27
8 12 4 14 4 8 12 14
4 8 12 14 6 33 2 27
perform a similar set of recursive calls to sort the right subarray. here's the result:
4 8 12 14 2 6 27 33
finally, merge the sorted 4-element subarrays to get a fully sorted 8-element array:
4 8 12 14 2 6 27 33
2 4 6 8 12 14 27 33
• Instead, we'll create a temp. array of the same size as the original.
• pass it to each call of the recursive mergesort method
• use it when merging subarrays of the original array:
arr 8 12 4 14 6 33 2 27
temp 4 8 12 14
• after each merge, copy the result back into the original array:
arr 4 8 12 14 6 33 2 27
temp 4 8 12 14
arr: … 4 8 12 14 2 6 27 33 …
temp: … …
start end
arr: … 12 8 14 4 6 33 2 27 …
temp: … …
1 1 1 1 1 1 … 1 1 1 1
• at all but the last level of the call tree, there are 2n moves
• how many levels are there?
• M(n) = ?
• C(n) = ?
• O(n2)-time
• O(n3)-time
• O(log2n)-time
• O(2n)-time
• sample computations:
• when n = 10, an n2 algorithm performs 102 operations.
102 * (1 x 10-6 sec) = .0001 sec
• when n = 30, a 2n algorithm performs 230 operations.
230 * (1 x 10-6 sec) = 1073 sec = 17.9 min
• sample computations:
• 1 hour = 3600 sec
that's enough time for 3600/(1 x 10-6) = 3.6 x 109 operations
• n2 algorithm:
n2 = 3.6 x 109 n = (3.6 x 109)1/2 = 60,000
• 2 algorithm:
n
Linked Lists
item
items 31 52 72 ...
• The last node in the linked list has a link value of null.
• Here's how the above linked list might actually look in memory:
0x200 0x520 the variable items
0x204
0x208 72
the last node
0x212 null
0x216
… …
0x520 31
the first node
0x524 0x812
0x528
… …
0x812 52
the second node
0x816 0x208
before:
31 52 72
items
null
after:
31 52 72
items
null
63
• Disadvantages:
• they don't provide random access
• need to "walk down" the list to access an item
• the links take up additional memory
• Example: temp.next.ch
Working backwards…
• I know that I need the ch field in the 'e' node
• Where do I have a reference to the 'e' node?
• What expression can I use for the box containing that reference?
2) temp.next = temp.next.next;
Tracing length()
public static int length(StringNode str) {
if (str == null) {
return 0;
} else {
return 1 + length(str.next);
}
}
• Example: StringNode.length(str1)
str:null
return 0;
str:0x404 str:0x404 str:0x404
"t" "t" return 1+0
str:0x720 str:0x720 str:0x720 str:0x720 str:0x720
"at" "at" "at" "at"
return 1+1
str:0x128 str:0x128 str:0x128 str:0x128 str:0x128 str:0x128 str:0x128
"cat" "cat" "cat" "cat" "cat" "cat"
return 1+2
time
• It can also be done using iteration (for loops, while loops, etc.).
trav
• Java method:
public static void toUpperCase(StringNode str) {
StringNode trav = str;
while (trav != null) {
trav.ch = Character.toUpperCase(trav.ch);
trav = trav.next;
}
}
trav
str
trav
str
str 'f'
'F' 'i' 'n' 'e'
null
trav
str
trav
str
trav
str
• Examples:
• getNode(str, 0) should return a ref. to the 'f' node
• getNode(str, 3) should return a ref. to the 'e' node
• getNode(str.next, 2) should return a ref. to…?
prevNode
prevNode
after:
prevNode
_____________ = __________________;
after:
ch 'f'
'f'
newNode
ch 'f'
'f'
newNode
after:
ch 'f'
'f'
newNode
newNode
'a' 'c' 'e'
str
x null
ch 'm'
prevNode
• Recursive approach:
• base case: if str is empty, return null
• else: – make a recursive call to copy the rest of the linked list
– create and return a copy of the first node,
with its next field pointing to the copy of the rest
stack heap
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
copyRest null
str
copyRest
str
copyRest
str
copyRest
str
copyRest
str
'g'
null
copyRest
str
copyRest
str
'g'
null
copyRest 'o'
str
copyRest
str
'g'
null
'o'
copyRest
str
'g'
null
'o'
copyRest 'd'
str
'g'
null
'o'
'd'
'g'
null
'o'
'd'
trav
trail trav
trail trav
Extra practice!
address value
A. 0xbe00 'r'
B. 0x3004 'e'
C. 0xbb00 'a'
D. none of these
items null …
list
length 2
"if"
a variable of type
ArrayList an ArrayList object "for"
• The dummy head node is always at the front of the linked list.
• like the other nodes in the linked list, it’s of type Node
• it does not store an item
• it does not count towards the length of the list
public LLList() {
head = new Node(null, null);
length = 0;
}
Node trav = ;
int travIndex = -1;
while ( ) {
travIndex++;
;
}
return trav;
} trav travIndex -1
example for i = 1: -1 0 1 2
item null "how" "are" "you"
head
next null
length 3
Getting an Item
public Object getItem(int i) {
if (i < 0 || i >= length) {
throw new IndexOutOfBoundsException();
}
Node n = getNode(i);
return ________;
}
example for i = 1:
n
-1 0 1 2
item null "how" "are" "you"
head
next null
length 3
prevNode "hi!"
newNode null
length++;
return true;
}
(the gray code shows what we would need to add if we didn't have a dummy head node)
prevNode
return str;
}
average:
worst: worst:
average: average:
worst: worst:
average: average:
space
efficiency
• Using an inner class gives the iterator access to the list’s internals.
• The iterator() method is an LLList method.
• it creates an instance of the inner class and returns it
• its return type is the interface type
• so it will work in the context of client code
nextNode = _______________;
return item; "how" "are" "you"
}
}
item null
head
next null
length 3
LLList
object nextNode
LLListIterator object
Stack ADT
• A stack is a sequence in which:
• items can be added and removed only at one end (the top)
• you can only access the item that is currently at the top
• Operations:
• push: add an item to the top of the stack
• pop: remove the item at the top of the stack
• peek: get the item at the top of the stack, but don’t remove it
• isEmpty: test if the stack is empty
• isFull: test if the stack is full
• Items are added from left to right (top item = the rightmost one).
• push() and pop() won't require any shifting!
ArrayStack<String> s1 =
new ArrayStack<String>(10);
ArrayStack<Integer> s2 =
new ArrayStack<Integer>(25);
• Instead, we do this:
public ArrayStack(int maxSize) {
// code to check for invalid maxSize goes here...
items = (T[])new Object[maxSize];
top = -1;
}
• Full stack:
0 1 2 3 4 5 6 7 8
items
top 8
removed
public T pop() {
if (isEmpty()) {
return null;
}
s2
top
null
variable of type
LLStack object
LLStack Node objects
• Things worth noting:
• our LLStack class needs only a single field:
a reference to the first node, which holds the top item
• top item = leftmost item (vs. rightmost item in ArrayStack)
• we don’t need a dummy node
• only one case: always insert/delete at the front of the list!
• The inner Node class uses the type parameter T for the item.
• We don’t need to preallocate any memory for the items.
• The stack is never full!
top
null
item 8
newNode
LLStack push()
15 7
top x
null
item 8
newNode
top x
null
public T pop() {
if (isEmpty()) {
return null;
}
T removed = _______________;
____________________________;
return removed;
}
public T peek() {
if (isEmpty()) {
return null;
}
return top.item;
}
ArrayStack LLStack
push() O(1) O(1)
pop() O(1) O(1)
peek() O(1) O(1)
space O(m) where m is the O(n) where n is the number of
efficiency anticipated maximum number items currently on the stack
of items
Queue ADT
• A queue is a sequence in which:
• items are added at the rear and removed from the front
• first in, first out (FIFO) (vs. a stack, which is last in, first out)
• you can only access the item that is currently at the front
• Operations:
• insert: add an item at the rear of the queue
• remove: remove the item at the front of the queue
• peek: get the item at the front of the queue, but don’t remove it
• isEmpty: test if the queue is empty
• isFull: test if the queue is full
• Example: 0 1 2 3
items
queue
front 1
3
73
variable of type rear
ArrayQueue numItems 3 25 51
ArrayQueue object
the same queue after removing two items and inserting two:
front rear
21 17 89 65 43 81
we have room for more items, but shifting to make room is inefficient
front rear
after:
ArrayQueue remove()
front rear
before:
10 5 9 13
front rear
after: null
removed 10 5 9 13
public T remove() {
if (isEmpty()) {
return null;
}
T removed = _________________;
numItems--;
return removed;
}
0 1 0 1
items null null … items null …
front 0 front 0
rear -1 rear 0
numItems 0 numItems 1 "hi"
variable of type
LLQueue LLQueue object Node objects
front null
rear null
The next field in the newNode
item "now"
will be null regardless of whether
the queue is empty. Why?
newNode
null
}
return true;
}
front
rear null
x "now"
item
newNode
null
front
null
rear
public T remove() {
if (isEmpty()) {
return null;
}
T removed = _________________;
if (front == rear) { // removing the only item
front = null;
rear = null;
} else {
// we'll add this later
}
return removed;
}
front x
rear null
public T remove() {
if (isEmpty()) {
return null;
}
T removed = _________________;
if (front == rear) { // removing the only item
front = null;
rear = null;
} else {
}
return removed;
}
ArrayQueue LLQueue
insert() O(1) O(1)
remove() O(1) O(1)
peek() O(1) O(1)
space O(m) where m is the O(n) where n is the number of
efficiency anticipated maximum number items currently in the queue
of items
Applications of Queues
• first-in first-out (FIFO) inventory control
• In the next few lectures, we’ll look at how we can use a tree
for a data dictionary, and we'll try to get better efficiency.
edge
• The node at the "top" of the tree is called the root of the tree.
2 3 4 5 6
7 8 9 10 11 12
2 3 4 5 6
7 8 9 10 11 12
Types of Nodes
1
2 3 4 5 6
7 8 9 10 11 12
13
2 3 4 5 6
7 8 9 10 11 12
13
level 0
level 1
depth = 2 level 2
• Example: 26
4 18 38
12 32
4 18 38
7
7 null null
4 is the root of 4 18 38
12’s left subtree
1: Preorder Traversal
• preorder traversal of the tree whose root is N:
1) visit the root, N
2) recursively perform a preorder traversal of N’s left subtree
3) recursively perform a preorder traversal of N’s right subtree
9 5
8 6 2
2: Postorder Traversal
• postorder traversal of the tree whose root is N:
1) recursively perform a postorder traversal of N’s left subtree
2) recursively perform a postorder traversal of N’s right subtree
3) visit the root, N
9 5
8 6 2
• Note that the root is printed after the two recursive calls.
time
9 5
8 6 2
• Note that the root is printed between the two recursive calls.
time
Level-Order Traversal
• Visit the nodes one level at a time, from top to bottom
and left to right.
9 5
8 6 2
15 7
23 8 10 5
12 6 35 26
+ /
a * d 2
3 c
Huffman Encoding
• One type of variable-length encoding
0 1 0 1
t e
0 1 0 1
o i a s
'o' 'i'
11 23
5) Repeat steps 3 and 4 until there is only a single node in the list,
which will be the root of the Huffman tree.
'o' 'i'
11 23
't' - 'e' -
27 34 40 51
0 1
0 1 0 1
t e
0 1 0 1
o i a s
0 1
0 1 0 1
t e
0 1 0 1
o i a s
0 1 i
0 1
o
t e
0 1 s
0 1
a s t
o i
4) Read through the input file a second time, and write the
Huffman code for each character to the output file.
0 1 0 1
t e
0 1 0 1
o i a s
0 1 0 1
t e
0 1 0 1
o i a s
Search Trees
a search tree:
26
< 26 12 32 26
12
4 18 38
< 12
7
26
12 32
4 18 38
}
Node newNode = new Node(key, data);
if (root == null) { // the tree was empty
root = newNode;
} else if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
}
ex: delete 4 12 32 12 32
4 18 38 18 38
ex: delete 12 12 32 18 32
18 38 38
4 18 38
7 20
ex:
delete 12 12 x copy node y's 18 x 18 x
contents into delete
node x node y
4 18 y 4 18 y 4 20
7 20 7 20 7
4 17
3 8 10 25
1 5 20 36
Implementing Case 3
private void deleteNode(Node toDelete, Node parent) {
if (toDelete.left != null && toDelete.right != null) {
// Find a replacement – and
// the replacement's parent. toDelete
Node replaceParent = toDelete;
// Get the smallest item
26
// in the right subtree.
Node replace = toDelete.right;
// what should go here? 18 45
30
// Replace toDelete's key and data
// with those of the replacement item. 35
toDelete.key = replace.key;
toDelete.data = replace.data;
// Recursively delete the replacement
// item's old node. It has at most one
// child, so we don't have to
// worry about infinite recursion.
deleteNode(replace, replaceParent);
} else {
...
}
level 0
level 1
depth = 2 level 2
• Search, insert, and delete all have the same time complexity.
• insert is a search followed by O(1) operations
• delete involves either:
• a search followed by O(1) operations (cases 1 and 2)
• a search partway down the tree for the item,
followed by a search further down for its replacement,
followed by O(1) operations (case 3)
• worst case:
• you have to go all the way down to level h
before finding the key or realizing it isn't there
• along the path to level h, you process h + 1 nodes
• average case:
38
10 40 77 90
3 14 20 34 51 68 80 87 93 97
2-node: k 3-node: k1 k2
k1
<k k <k1 <k2 k2
10 40 77 90
3 14 20 34 51 68 80 87 93 97
50 50 50 54
… … …
54 70 52 54 70 52 70
Example 1: Insert 8
• Search for 8:
28 61
10 40 77 90
3 14 20 34 51 68 80 87 93 97
10 40 77 90
3 8 14 20 34 51 68 80 87 93 97
10 40 77 90
3 14 20 34 51 68 80 87 93 97
• Split the leaf node, and send up the middle of 14, 17, 20
and insert it the leaf node’s parent:
28 61 28 61
… 10 17 40
…
10 40
17
3 14 20 34 51 3 14 20 34 51
Example 3: Insert 92
28 61
10 40 77 90
3 14 20 34 51 68 80 87 93 97
10 40 77 90
3 14 20 34 51 68 80 87 93 97
• Split the leaf node, and send up the middle of 92, 93, 97
and insert it the leaf node’s parent:
28 61 28 61
… …
40 77 90 40 77 90 93
34 51 68 80 87 92 93 97 34 51 68 80 87 92 97
Example 3 (cont.)
• We split the [77 90] node and we send up the middle of 77, 90, 93:
• We try to insert it in the root node, but the root is also full!
28 61 28 61 90
… …
40 77 90 93 40 77 93
34 51 68 80 87 92 97 34 51 68 80 87 92 97
• Thus, we can use 2-3 trees for a O(log n)-time data dictionary!
External Storage
• The balanced trees that we've covered don't work well if you
want to store the data dictionary externally – i.e., on disk.
3 10 14 28 34 51 61 77 80 87 93 97
10 40 77 90
3 14 20 34 51 68 80 87 93 97
3 10 14 28 34 51 61 77 80 87 93 97
Insertion in B-Trees
• Similar to insertion in a 2-3 tree:
search for the key until you reach a leaf node
if a leaf node has fewer than 2m items, add the item
to the leaf node
else split the node, dividing up the 2m + 1 items:
the smallest m items remain in the original node
the largest m items go in a new node
send the middle entry up and insert it (and a pointer to
the new node) in the parent
10 20 40 68 90 10 20 68 90
… … … …
3 5 13 14 28 34 51 61 3 5 13 14 28 34 51 61
• Splitting the root increases the tree’s height by 1, but the tree
is still balanced. This is only way that the tree’s height increases.
Analysis of B-Trees
20 40 68 90
3 10 14 28 34 51 61 77 80 87 93 97
Priority Queue
• A priority queue (PQ) is a collection in which each item
has an associated number known as a priority.
• ("Ann Cudd", 10), ("Robert Brown", 15),
("Dave Sullivan", 5)
• use a higher priority for items that are "more important"
• Key operations:
• insert: add an item (with a position based on its priority)
• remove: remove the item with the highest priority
• Complete:
26 10 8 17 14 3
12 32
10
4 18 28
8 17
26 12 32 4 18 28 14 3
28 18 12
16 20 8 2 7 10
12 8 5 3 7
16 20 8 2 7 10
12 18 5 3 7 2 5
E. none of them
sift down 5 20 20
the 5:
20 12 5 12 16 12
16 8 16 8 5 8
7 18 7 10
3 5 8 6 3 5 8 6
sift down
7
the 7:
26 23
15 18 10
16 12 16 12
5 8 5 8 35
sift it up: 20 20 35
16 12 16 35 16 20
5 8 35 5 8 12 5 8 12
16 8
14 20 1 26
• This means we can use a heap for a O(log n)-time priority queue.
14 20 1 26
• Last element’s parent = contents[(7 – 2)/2] = contents[2].
Sift it down:
5 5
16 8 16 26
14 20 1 26 14 20 1 8
16 26 20 26
14 20 1 8 14 16 1 8
20 26 20 5 20 8
14 16 1 8 14 16 1 8 14 16 1 5
Heapsort Example
0 1 2 3 4 5 6
• Sort the following array: 13 6 45 10 3 22 5
6 45
10 3 22 5
6 3 13 5
• We begin looping:
while (endUnsorted > 0) {
// Get the largest remaining element and put it
// at the end of the unsorted portion of the array.
largestRemaining = heap.remove();
arr[endUnsorted] = largestRemaining;
endUnsorted--;
}
6 3 13 5
6 3 13 5 6 3 5 6 3 5
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 45 22 10 13 6 3 5 5 22 10 13 6 3 5 45
endUnsorted: 6 endUnsorted: 5
largestRemaining: 45
6 3 5 6 3 6 3
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 22 13 10 5 6 3 5 45 13 10 5 6 3 22 45
endUnsorted: 5 endUnsorted: 4
largestRemaining: 22
copy 13; 3
13 10 10
move 3 sift down 3; put 13 in place;
to root return 13 decrement
10 5 6 5 6 5
6 3 3 3
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 13 10 6 53 3 22 45 10 6 5
3 13 22 45
endUnsorted: 4 endUnsorted: 3
largestRemaining: 13
3
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 10 6 3 53 13 22 45 6 3
5 10 13 22 45
endUnsorted: 3 endUnsorted: 2
largestRemaining: 10
copy 6; 65 5 5
move 5 sift down 5; put 6 in place;
to root return 6 decrement
3 5 3 3
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 6 5 3 5 10 13 22 45 5 3
6 10 13 22 45
endUnsorted: 2 endUnsorted: 1
largestRemaining: 6
0 1 2 3 4 5 6 0 1 2 3 4 5 6
toRemove: 5 3 3 6 10 13 22 45 3 5
6 10 13 22 45
endUnsorted: 1 endUnsorted: 0
largestRemaining: 5
16 8
14 20 1 26
Hash Tables
• We'll now look at hash tables, which can do better than O(log n).
• Two options:
1. each bucket is itself an array
• need to preallocate, and a bucket may become full
2. each bucket is a linked list
• items with the same hash code are "chained" together
• each "chain" can grow as needed
0 "ant" "ape"
1 null null
2 "cat"
3 null null
… ...
Linear Probing
• Probe sequence: h(key), h(key) + 1, h(key) + 2, …,
wrapping around as necessary.
• Examples:
• "ape" (h = 0) would be placed in position 1, 0 "ant"
because position 0 is already full. 1 "ape"
• "bear" (h = 1): try 1, 1 + 1, 1 + 2 – open! 2 "cat"
• where would "zebu" end up? 3 "bear"
4 "emu"
5
• Advantage: if there is an open cell,
6
linear probing will eventually find it.
7
… ...
• Disadvantage: get "clusters" of occupied cells
22 "wolf"
that lead to longer subsequent probes.
23 "wasp"
• probe length = the number of positions 24 "yak"
considered during a probe 25 "zebra"
• Examples:
• "ape" (h = 0): try 0, 0 + 1 – open! 0 "ant"
• "bear" (h = 1): try 1, 1 + 1, 1 + 4 – open! 1 "ape"
• "zebu"? 2 "cat"
3
• Advantage: smaller clusters of occupied cells 4 "emu"
5 "bear"
• Disadvantage: may fail to find an existing 6
open position. For example: 7
table size = 10 … ...
x = occupied 0 x 5 x 25
1 x 1 81 6 x 16 36 22 "wolf"
trying to insert a
key with h(key) = 0 2 7 23 "wasp"
3 8 24 "yak"
offsets of the probe
sequence in italics 4 x 4 64 9 x 9 49 25 "zebra"
Double Hashing
• Use two hash functions:
• h1 computes the hash code
• h2 computes the increment for probing
• probe sequence: h1, h1 + h2, h1 + 2*h2, …
0 "ant"
1 "bear"
• Examples:
2 "cat"
• h1 = our previous h
3 "ape"
• h2 = number of characters in the string
4 "emu"
• "ape" (h1 = 0, h2 = 3): try 0, 0 + 3 – open!
5
• "bear" (h1 = 1, h2 = 4): try 1 – open!
6
• "zebu"?
7
… ...
• Combines good features of linear and quadratic:
22 "wolf"
• reduces clustering
23 "wasp"
• will find an open position if there is one, 24 "yak"
provided the table size is a prime number 25 "zebra"
4 null
… …
• We use a private inner class for the entries in the hash table.
4 null
… …
return i;
}
return i;
}
• To avoid overflow (and reduce search times), grow the hash table
when the % of occupied positions gets too big.
• problem: we need to rehash all of the existing items. why?
• h2(key) = key.length() 3
4 "emu"
• shaded cells are removed cells
5
• What is the probe sequence for "baboon"? 6
(the sequence of positions seen during probing) 7
8
9
10
A. 1, 2, 5
B. 1, 6
C. 1, 7, 2
D. 1, 7, 3
E. 1, 7, 2, 8
• h2(key) = key.length() 3
4 "emu"
• shaded cells are removed cells
5
• What is the probe sequence for "baboon"? 6
(h1 = 1, h2 = 6) try: 1 % 11 = 1 7
(1 + 6) % 11 = 7 8
(1 + 2*6) % 11 = 2 9
(1 + 3*6) % 11 = 8 10
A. 1, 2, 5
empty cell, so stop probing
B. 1, 6
C. 1, 7, 2
D. 1, 7, 3
E. 1, 7, 2, 8
Extra Practice
• Start with the hash table at right with: 0 "ant"
• double hashing 1
• h1(key) = ASCII of first letter – ASCII of 'a' 2 "cat"
• h2(key) = key.length() 3
4 "emu"
• shaded cells are removed cells
5
• What is the probe sequence for "baboon"? 6
(h1 = 1, h2 = 6) try: 1 % 11 = 1 7
(1 + 6) % 11 = 7 8
(1 + 2*6) % 11 = 2 9
(1 + 3*6) % 11 = 8 10
• h2(key) = key.length() 3
4 "emu"
• shaded cells are removed cells
5
• What is the probe sequence for "baboon"? 6
(h1 = 1, h2 = 6) try: 1 % 11 = 1 7
(1 + 6) % 11 = 7 8
(1 + 2*6) % 11 = 2 9
(1 + 3*6) % 11 = 8 10
Graphs
What is a Graph?
e
vertex / node
edge / arc b d f h j
a c i
185 Providence
New York
b d f h j
a c i
b d f h j
a c i
Directed Graphs
• A directed graph has a direction associated with each edge,
which is depicted using an arrow:
e
b d f
a c
b d f h
a c i
b d f h b d f h
a c i a c i
b d f h
a c i
a c i
• The trees on that slide were spanning trees for this graph.
Here are two others:
e e
b d f h b d f h
a c i a c i
• Example:
0 1 2 3
1. Portland 39
0 54 44
1 39 2. Portsmouth
83
2 54 39 83 54
44
3 44 83 3. Worcester 0. Boston
• This representation:
• wastes memory if a graph is sparse (few edges per vertex)
• is memory-efficient if a graph is dense (many edges per vertex)
Graph Class
public class Graph {
private class Vertex {
private String id;
private Edge edges; // adjacency list
private Vertex next;
private boolean encountered;
private boolean done;
private Vertex parent;
private double cost;
…
}
private class Edge {
private Vertex start;
private Vertex end;
private double cost;
private Edge next;
…
} The highlighted fields
private Vertex vertices; are shown in the diagram
… on the previous page.
}
“Portsmouth”
39 54 83
null
“Worcester”
44 83
null null
Traversing a Graph
• Traversing a graph involves starting at some vertex and visiting
all vertices that can be reached from that vertex.
• visiting a vertex = processing its data in some way
• if the graph is connected, all of its vertices will be visited
• Applications:
• determining the vertices that can be reached from some vertex
• web crawler (vertices = pages, edges = links)
185 Providence 5
New York 6
Another Example:
Depth-First Traversal from Worcester
• In what order will the cities be visited?
• Which edges will be in the resulting spanning tree?
84 Portland 39
Concord Portsmouth
74
63 83
54
134 44
Albany Worcester Boston
42 49
185 Providence
New York
cycle b d f h
a c i
Breadth-First Traversal
• Use a queue to store vertices we've seen but not yet visited:
private static void bfTrav(Vertex origin) {
origin.encountered = true;
origin.parent = null;
Queue<Vertex> q = new LLQueue<Vertex>();
q.insert(origin);
while (!q.isEmpty()) {
Vertex v = q.remove();
System.out.println(v.id); // Visit v.
// Add v’s unencountered neighbors to the queue.
Edge e = v.edges;
while (e != null) {
Vertex w = e.end;
if (!w.encountered) {
w.encountered = true;
w.parent = v;
q.insert(w);
}
e = e.next;
}
}
}
185 Providence 6
New York 8
185 Providence 6
New York 8
New York
185 Providence
New York
• Example applications:
• determining the shortest highway system for a set of cities
• calculating the smallest length of cable needed to connect
a network of computers
• The MST is the spanning tree with the minimal total edge cost.
• We can do better!
• use a heap-based priority queue to store the vertices in set B
• priority of a vertex x = –1 * cost of the lowest-cost edge
connecting x to a vertex in set A
• why multiply by –1?
Dijkstra’s Algorithm
• One algorithm for solving the shortest-path problem for
weighted graphs was developed by E.W. Dijkstra.
• Basic idea:
• maintain estimates of the shortest paths
from the origin to every vertex (along with their costs)
• gradually refine these estimates as we traverse the graph
• Initial estimates:
path cost C (inf)
the origin itself: stay put! 0 5 7
all other vertices: unknown infinity
A 14
B
(0) (inf)
• Example:
C (inf) C (5) C (5)
5 7 5 7 5 7 (5 + 7 < 14)
A 14
B A 14
B A 14
B
(0) (inf) (0) (14) (0) (12)
Finalizing a Vertex
origin
other finalized vertices
w encountered but
unfinalized
(i.e., it has a
non-infinite estimate)
185 Providence
New York
185 Providence
New York
CSCI E-251
MATH E-10 MATH E-104 CSCI E-124
CSCI E-215
CSCI E-50a CSCI E-50b CSCI E-119
D E F
G H
• Other applications:
• coin collection from phone booths
• routes for school buses or garbage trucks
• minimizing the movements of machines in automated
manufacturing processes
• many others
Cm Ct O Y
Ct O Y Cm O Y Cm Ct Y Cm Ct O
O Y Ct Y Ct O O Y Cm Y Cm O Ct Y Cm Y Cm Ct Ct O Cm O Cm Ct
Y O Y Ct O Ct Y O Y Cm O Cm Y Ct Y Cm Ct Cm O Ct O Cm Ct Cm
L L L L L L L L L L L L L L L L L L L L L L L L
• Better than brute force, but still exponential space and time.
• Algorithms that fall into one of the classes above the dotted line
are referred to as polynomial-time algorithms.
Classifying Problems
• Problems that can be solved using a polynomial-time algorithm
are considered “easy” problems.
• we can solve large problem instances in a
reasonable amount of time
Take-Home Lessons
• Computer science is the science of solving problems
using computers.