CIS 3020 Part 5

Messy Example 1

Code

ass Mess1 {
  public static void main (String[] arg) {
    int d;
    d=10;
    System.out.println(d);
    Ex1 g;
    g=new Ex1();
    g.a(d);
    System.out.println(d);
  }
}

class Ex1 {
  int p;
  
  Ex1() {
    p=0;
  }
  
  public void a (int p) {
    this.b(p);
    this.printVals(p);
    this.b(this.p);
  }

  private void b (int q) {
    this.printVals(q);
  }

  private void printVals(int r) {
    System.out.println(r);
  }
}

Output

10
10
10
0
10

Messy Example 2

Code

class Mess2 {
  public static void main (String[] arg) {
    int d,e;
    d=4;
    e=6;
    System.out.println(d + " " + e);
    Ex2 g = new Ex2();
    g.a(d,e);
    System.out.println(d + " " + e);
  }
}

class Ex2 {
  int p;
  
  Ex2() {
    p=3;
  }
  
  public void a (int p, int r) {
    this.b(r,p);
    this.printVals(p,r);
    this.b(this.p,r);
  }

  private void b (int p, int r) {
    this.printVals(p,r);
    this.printVals(this.p,r);
  }

  private void printVals(int p, int r) {
    System.out.println(p + " " + r);
  }
}

Output

4 6
6 4
3 4
4 6
6 3
3 3
4 6

Messy Example 3

Code

class Mess3 {
  public static void main (String[] arg) {
    int d,e;
    d=4; e=6;
    System.out.println(d + " " + e);
    Ex3 g = new Ex3();
    g.a(d,e);
    System.out.println(d + " " + e);
  }
}

class Ex3 {
  int p;
  
  Ex3() {
    p=3;
  }
  
  public void a (int p, int r) {
    this.b(r,p);
    this.printVals(p,r);
    this.b(r,this.p);
  }

  private void b (int p, int r) {
    this.printVals(r, this.p);
    c(p,r);
    c(this.p, r);
  }

  void c(int r, int p) {
    this.printVals(p,r);
  }

  private void printVals(int p, int r) {
    System.out.println(p + " " + r);
  }
}

Messy Example 4

Code

class Mess4 {
  public static void main (String[] arg) {
    int d,e,f;
    d=4; e=6; f=8;
    System.out.println(d + " " + e + " " + f);
    Ex4 g = new Ex4();
    g.a(d,e,f);
    System.out.println(d + " " + e + " " + f);
  }
}

class Ex4 {
  int p;
  Ex4() {
    p=3;
  }
  
  public void a (int p, int q, int r) {
    b(q,r,p);
    this.printVals(p,q,r);
    this.b(r,q,this.p);
  }

  private void b(int p, int q, int r) {
    this.printVals(p,q,r);
    c(this.p, q, r);
    c(p,r,q);
  }

  void c(int q, int p, int r) {
    this.printVals(p,q,r);
  }

  private void printVals(int p, int q, int r) {
    System.out.println(p + " " + q + " " + r);
  }
}

Tree Recursion

• Consider the Fibonacci Number Sequence:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

• This sequence is defined by the rule:

        /  0                     when n=0
fib(n)= |  1                     when n=1
        \  fib(n-1) + fib(n-2)   otherwise

• As code this is:

public int fib (int n) {
  int result;
  if (n<=0)
    result = 0;
  else if (n == 1)
    result = 1;
  else 
    result = (fib(n-1) + fib(n-2));
  return result;
}

Orders of Growth

• An important consideration in the comparison of different soluytions to problems is the complexity of the algorithms used.
• This complexity is measured on two important quantities:
  • The space requirements (space complexity) to represent all values used in the algorithm
  • The time requirements (time complexity) needed to perform all of the needed calculations

The BIG-O

Informal Definition

If function Est(n) times some integer constant, m, dominates funciton Time(n), then we say:

Time(n) = O(Est(n))

Algebraic Identities for Big-O

Assume c denotes a constant and that f and g are arbitrary functions

1. c * f = O(f) -- you can drop constant multipliers

17n = O(n)

25n² = O(n²)

99 = O(1)

2. f + g = O(f), so long as f dominates g

n² + 3 = O(n²)

n5 + n3 + n = O(n5)

3. f * g = O(f) * O(g)

n3m² = O(n3) * O(m²)