Introduction to Algorithms

Introduction to Algorithms
> Click or hit Control-Enter to run Example.main above

public class Car {
  // Constructor and private variable not shown
  public int increaseMileage() {
    return odometer++;
  }
  public boolean equals(Car other) {
    return odometer == other.odometer;
  }
}
public class Example {
  public static void main(String[] unused) {
    Car[] cars = new Car[10];
    Car car = new Car(10);
    for (int i = 0; i < cars.length; i++) {
      cars[i] = car;
    }
    for (int i = 0; i < cars.length; i++) {
      cars[i].increaseMileage();
    }
    System.out.println(cars[0].odometer);
  }
}

When the main method runs, what will be printed?

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

Define a class called All. It should provide a single class method named orNothing which takes two parameters: an int (first) and a boolean (second). orNothing should return an array of All references with the size provided as the first parameter. (If the first parameter is negative, return an empty array.) If its second parameter is false orNothing should return the array containing all references to different All instances. If its second parameter is true orNothing should return the array containing all references to the same All instance.

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

/**
 * Compares this object with the specified object for order.
 *
 * Returns a negative integer, zero, or a positive integer as this object is
 * less than, equal to, or greater than the specified object.
 */
public interface Comparable {
  int compareTo(Object other);
}

Interfaces represent a contract between the interface provider and the interface user.

The interface represents all that the two components on either side need to agree on for things to work correctly.

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

About references, interfaces, or other object-oriented concepts?

This week: a quiz, primarily on interfaces and inheritance
Next week: Midterm 1 covering object-oriented programming

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

Data structure: a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

As Java programmers we implement more complicated data structures using a mix of:

Primitive types and objects to store and organize data values
Existing data structures like arrays
References to reflect relationships among objects

Algorithms and data structures are highly complementary:

We will implement algorithms that utilize specific features of data structures
We will implement data structures to support specific algorithms
We will use our existing imperative and object-oriented ideas along the way
And we’ll introduce a few more important ideas along the way

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
You’re in a job interview

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.

The MP4 early deadline is today at 5PM. Get your 50 points!
I now have office hours MWF from 10AM–12PM in Siebel 2227. Please stop by!
Remember to provide feedback on the course using the anonymous feedback form.
I’ve started to respond to existing feedback on the forum.

Q6 Review: References

Q6 Review: All or Nothing

Review: Interface as Contract

Questions?

Reminder: Midterm 1 is Next Week

Algorithms

Data Structures

Algorithms and Data Structures

Example: 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

Announcements