Algorithm Runtime

Algorithm Runtime
> Click or hit Control-Enter to run Example.main above

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?

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?

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?

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?

Algorithm: a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.

As computer scientists, we implement algorithms by having computers:

Perform simple calculations
Store the results
Make simple decisions
Do things over and over again as fast as possible

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.

What’s a simpler approach?

Brute force solution: a very general problem-solving 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 Control-Enter to run Example.main above

That’s a good thing!

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

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: the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

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 worst-case running times?
How is the algorithm’s performance related to its inputs?

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.

Q5 Review: `static`

Q5 Review: Inheritance

Q5 Review: Method Inheritance

Q5 Review: Class Design

Review: What’s An Algorithm?

Algorithms

Greatest Common Denominator

But If We’re In A Hurry…

Brute Force Solution

You Don’t Need the Fastest Algorithm to Change the World

But Speed Eventually Matters

So How Long Will It Take?

Algorithm Analysis

At The Limit

Announcements

Q5 Review: static