Algorithm Runtime
> Click or hit ControlEnter to run Example.main above
Q5 Review: static
public class Laptop {
public static int count = 0;
private String model;
Laptop(String setModel) {
model = setModel;
count++;
}
public static void main(String[] unused) {
Laptop apple = new Laptop("Apple");
Laptop PC = new Laptop("Windows");
Laptop broken = new Laptop("Linux");
System.out.println(apple.count);
}
}
When the main
method defined above runs, what will be printed?
Q5 Review: Inheritance
public class Shape {
// Position coordinates
private double x;
private double y;
Shape(double setX, double setY) {
this.x = setX;
this.y = setY;
}
}
public class Rectangle extends Shape {
private double length;
private double height;
Rectangle(double setX, double setY, double setLength, double setHeight) {
this.x = setX;
this.y = setY;
this.length = setLength;
this.height = setHeight;
}
}
Given the classes defined above, why does it make sense for Rectangle
to
extend
Shape
?
Q5 Review: Method Inheritance
class Furniture {
private String type;
Furniture(String setType) {
type = setType;
}
public String toString() {
return "I'm furniture";
}
public String getType() {
return this.type;
}
}
class Couch extends Furniture {
private int numCushions;
Couch(int setNumCushions) {
super("Couch");
numCushions = setNumCushions;
}
private int getNumCushions() {
return numCushions;
}
}
Why does Furniture
not have a setType
method?
Q5 Review: Class Design
class Computer {
protected static int count = 0;
protected String brand;
Computer(String setBrand) {
this.brand = setBrand;
this.count++;
}
}
class Laptop extends Computer {
public static String type = "laptop";
Laptop(String setBrand) {
super(setBrand);
}
}
class Desktop extends Computer {
public static String type = "desktop";
Desktop(String setBrand) {
super(setBrand);
}
}
What would be the best variable to add to the Desktop
class?
Review: What’s An Algorithm?
Algorithms
Algorithm: a process or set of rules to be followed in calculations or other problemsolving operations, especially by a computer.
As computer scientists, we implement algorithms by having computers:

Perform simple calculations

Store the results

Make simple decisions

Do things over and over again as fast as possible
Greatest Common Denominator
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.
But If We’re In A Hurry…
What’s a simpler approach?
Brute Force Solution
Brute force solution: a very general problemsolving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement.

Computers today are very, very fast

So try the simple thing first

If it’s too slow, try something a bit more sophisticated
> Click or hit ControlEnter to run Example.main above
You Don’t Need the Fastest Algorithm to Change the World
That’s a good thing!
But Speed Eventually Matters
Even if you don’t at the beginning, you will eventually start to care about how fast your code runs. For any number of the following reasons:

You’re embarrassed that your algorithm makes your incredibly fast computer seem slow

You have to start paying for machines

Your customer tells you that your program is too slow
So How Long Will It Take?
How long will our brute force GCD algorithm take?

To compute the GCD of 4 and 6

To compute the GCD of 185 and 2045

To compute the GCD of M and N
Algorithm Analysis
Algorithm analysis: the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.
At The Limit
We’re usually want to analyze an algorithm in the general case, rather than for a specific set of input.

How does the algorithm perform on arbitrarily difficult or large inputs?

What are the best, average, and worstcase running times?

How is the algorithm’s performance related to its inputs?
Announcements

MP4 is out and due in less than two weeks. The early deadline is a week from today. Please get started. MP4 is not easy.

Continue to communicate with the course staff about the strike as needed. We’re trying to keep everything up and running.

The grading page has some new features allowing you to evaluate your performance. Check it out.

My office hours continue today at 11AM in the lounge outside of Siebel 0226.