teaching machines

CS 245 Lecture 9 – Computational Complexity and Binary Search

February 18, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• finishing up OurrayList
• think about this
• linear search
• binary search
• computational complexity

TODO

• Synchronize on Bitbucket and pull in Eclipse. No 1/4 sheet.
• Optional: read http://bugs.java.com/bugdatabase/view_bug.do?bug_id=5045582 and http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html.

Think About This

Code

Super.java

package lecture09;

import java.awt.image.BufferedImage;

public class Super {
  public Super(int a, BufferedImage img) {
    
  }
}

Sub.java

package lecture09;

import java.awt.image.BufferedImage;

public class Sub extends Super {
  public Sub() {
    super(5, image);
    BufferedImage image = new BufferedImage(512, 256, BufferedImage.TYPE_INT_RGB);

  }
  
  private void foo(int a, BufferedImage img) {
    
  }
}

OurrayList.java

package lecture09;

import java.util.NoSuchElementException;

public class OurrayList {
  private String[] items;
  private int itemCount;

  public OurrayList(int initialCapacity) {
    items = new String[initialCapacity];
    itemCount = 0;
  }

  public OurrayList() {
    this(10);
  }

  public int size() {
    return itemCount;
  }

  public String get(int i) {
    if (i < 0 || i >= itemCount) {
      throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
    }
    return items[i];
  }

  public void add(String s) {
    // Are we full?
    if (itemCount == items.length) {
      String[] moreItems = new String[2 * items.length];
      for (int i = 0; i < items.length; ++i) {
        moreItems[i] = items[i];
      }
      items = moreItems;
    }

    items[itemCount] = s;
    ++itemCount;
  }

  public void remove(int i) {
    --itemCount;
    for (int j = i; j < itemCount; ++j) {
      items[j] = items[j + 1];
    }
    items[itemCount] = null;
  }

  public int indexOf(String s) {
    for (int i = 0; i < itemCount; ++i) {
      if (items[i].equals(s)) {
        return i;
      }
    }
    return -1;
    // throw new NoSuchElementException();
  }

  public void remove(String s) {
    int i = indexOf(s);
    if (i >= 0) {
      remove(i);
    }
  }

  public String toString() {
    String s = "[";

    if (size() > 0) {
      s += items[0];
      for (int i = 1; i < size(); ++i) {
        s += ", " + items[i];
      }
    }

    return s + "]";
  }

  public static void main(String[] args) {
    OurrayList l = new OurrayList(1);
    l.add("Alice");
    // l.add("Bob");
    // l.add("Carol");
    // l.add("Moon Unit");
    System.out.println(l);

    l.remove(0);
    System.out.println(l);
  }
}

Haiku