Skip to content

Lab 02

Welcome to the second lab! Previously we've checked your setup, and you now should already know how to compile simple java programs from source code to java bytecode on command line and how to run your code.

From here on we're using the IntelliJ IDE for writing code. However, keep in mind that the IDE does not add any sort of magic and is its core just an advanced text editor with UI element to invoke standard java tools, like the compiler and the java virtual machine.

In today's lab we'll refresh some java basics and add a little practice for programming paradigms seen in class.

Object orientation

  • Throughout the remainder of the course we'll be working exclusively with Object-Oriented (OO) concepts.
  • Before we dive into essential OO practices, we'll recap a fundamental OO concept: Classes, objects and class secrets.

Classes and objects

Java classes are not the same as java objects.

  • A class is a template.
    • A class defines common properties and behaviour.
  • An object is an instance of a class.
    • It assigns concrete values to the defined properties.
    • It can execute behaviour, using these values.

Illustration

  • As you're roaming the Montreal streets, you see many cars.
    • They take up space
    • They have concrete property values, e.g. weighs 1.4 tons, takes up 40L of fuel, has 83HP.
    • They can execute behaviour, like accelerate, break, fuel-up, ...
What concept fits each of these cars ?

An object: They have concrete values, and can execute behaviour.

What concept would be best suited to describe commonalities of all these cars ?

A class: The class defines properties (not concrete values), like "weight", "fuel consumption", "power", and the class defines behaviour like "accelerate", "break", "fuel-up", ...

Another way to recap is:

  • Classes are blueprints.
  • Objects are instances, created from these blueprints.

Keeping class secrets

Usually, you want to design your classes, so the objects reflect a notion of security, i.e. nothing too weird can happen when we create objects from the classes blueprint.

Example:

  • Car blueprints are designed so fuel can only be added, never removed (other than by driving).
  • In fact, it would be troublesome of cars could dump fuel to the asphalt at will.
  • If the car blueprint is designed not to allow dumping fuel, none of the car objects will be able to.

Open access

With the above fuel example in mind, what is the issue with below Car class implementation ?

public class Car
{

  public int remainingFuel = 50;
  public int mileage = 200;
  public int horsepower = 80;
  public int speed = 0;

  public void accelerate()
  {
    speed = speed + 10;
    System.out.println("Vroooooom");
  }

  public void slowDown()
  {
    speed = speed - 10;
    System.out.println("Screeeeech");
  }

  public void fuelUp()
  {
    remainingFuel = 100;
    System.out.println("Glug, glug, glug");
  }
}
What's the issue ?

All the fields are public. The cars would have an openly accessible tank. Anyone could add or remove gas anytime. Same for all other fields.

Restricted access

  • In java, you rarely want class fields to be public.
  • A public field is the equivalent to "I don't care about security, I assume nobody ever makes programming mistakes or uses my code other than I anticipated."

Create a secured version of the above code:

  • Make sure fuel can only be added, never removed.

Other languages

  • Many scripting languages, e.g. python do not have a proper concept for protecting fields.
  • At first, it may seem easier (I do not need to worry about security, so I'm faster at programming my little app)
  • In reality the absence of security concepts is rarely an advantage. Just because something seemingly "works", does not mean it is a good solution:

We don't care if it works.

In this course we do not care if code "works". Working code is the bare minimum we expect. In this course we only care about the quality of a solution, i.e. if it is reliable, fitting, sound and elegant.

Loop and recursion

In this second segment we take a look at another paradigm theme touched in the last lecture: Different ways to implement iterations.

But before we train going back and forth between loop and recursive code equivalents, here's brief reminder of the java syntax.

  • We are looking at the integer sum example, i.e. for a given number n, we want to compute the sum of all numbers below.
  • Example: For n = 5 we want to compute 1 + 2 + 3 + 4 + 5

Technically we can do better

The example is a bit contrived, for as you certainly know we can also just use Gauß sum formula, and sidestep any need for loops or recursion in the first place:
sum(n) = n*(n+1) / 2.
But to keep up the fun we'll pretend we've never heard of Gauß and hence have to compute the result step by step.

Loop syntax sample

As a java loop this is pretty straightforward:

public static void main(String[] args) {
    System.out.println(addAll(100));
}

// Loop implementation (we're using a for loop to iterate)
public static int addAll(int limit)
{
    int sum = 0;
    for (int i = 0; i <= limit; i++)
    {
      sum = sum + i;
    }
    return sum;
}

The for statement allows us to repeatedly perform computations (add +i), until an end criteria is reached (we've reached 100).

Recursion syntax sample

But what if no for statement is allowed (or we're working with a non-imperative language) ? In this example we'll stick to the java syntax, but we see how the same can be achieved with a recursive function call:

public static void main(String[] args)
{
    System.out.println(sum(100));
}

// Loop implementation (we're using recursion to iterate)
public static int sum(int i)
{

    // End recursion criteria
    if (i == 1)
    {
      return 1;
    }

    // Otherwise continue recursion
    return sum(i - 1) + i;
}

Check out the last line: sum(i-1) + i. We have no loop, but by just delegating to the next iteration using recursion we can still add up all numbers.

Conversion

  • A basic principle of programming is that every algorithm expressed as a loop can be converted to a recursive equivalent and vice versa. The counterpart may not always be obvious though.
  • In the following exercises, you must find counterpart:
    • I'll provide you with a recursive implementation and you must write the corresponding loop java code.
    • I'll provide you with a loop implementation and you must write the corresponding java recursive code.

Recursion to loop

Below you find a very short java function. It is an implementation of the Collatz Conjecture.

Recursive version

  • Try to understand what this code does, express in your own words the algorithm.
  • When you think you understand what it does, check your answer with the green box below.

Just try

You can play it through on a piece of paper, e.g. for an initial input value 4.

public static void collatz(int n) throws InterruptedException
{

    System.out.println(n);

    // Just a little sleep, so you can observe what is going on.
    Thread.sleep(300);

    if(n%2 ==0)
      collatz(n/2);
    else
      collatz(n*3 +1);
}
What is the algorithm.

It is an infinite recursion. On each step the current number is either:
- Divided by 2 (if it is even)
- Multiplied by 3, then added 1 (if odd) The same can be implemented with an infinite loop.

Your turn

Fill in the blanks:

  • Convert the provided code to a loop version.
  • Verify your solution by executing the code: Compare the outputs of your iterative program, to the outputs of the provided recursive program:
public static void main(String[] args) throws InterruptedException
{
    collatz(100);
}

public static void collatz(int n) throws InterruptedException
{
    // ... your code here.
}
Any observations when you try a few different inputs ?

It seems whatever number you start with, the series always ends in a loop: 4 -> 2 -> 1.
Funny though, although every number ever tried ends with the same loop, no one has ever come up with a proof.
(If you find a proof, let me know !)

Loop to recursion

This last exercise is the counterpart to the previous. You have to convert a loop implementation to a recursive implementation, i.e. no while or for allowed.

Loop version

  • This time I'm not telling your what the function does.
  • Take a good look at the code, try to understand it. When you think you understood the code, check your understanding with the green box below.
  public static void main(String[] args) throws InterruptedException
{
    // Initialize numbers
    int i1 = 1;
    int i2 = 1;
    int iterationCounter = 0;

    // An end-condition could be, we want to stop after 10 iterations.
    while (iterationCounter < 10)
    {

        System.out.println(i1);
        Thread.sleep(300);
        int nextNumber = i1 + i2;
        i1 = i2;
        i2 = nextNumber;

        // Don't forget to increment the counter, so our loop actually stops eventually:
        iterationCounter++;
    }
}
What is this function all about.

It is an implementation of the Fibonacci sequence.
It prints fibonacci numbers (the next number is always the sum of the previous two), so: 1, 1, 2, 3, 5, ...

Your turn

Fill in the blanks:

  • Convert the provided code to a recursive version.
  • Verify your solution by executing the code: Compare the outputs of your iterative program, to the outputs of the provided recursive program:
public static void main(String[] args) throws InterruptedException
{
    // Initialize numbers
    int i1 = 1;
    int i2 = 1;
    int iterationCounter = 10;
    // Start recursion
    fib(i1, i2, iterationCounter);
}

public static void fib(... your parameters here) throws InterruptedException
{
        // Your code here...
}