teaching machines

CS 245 Lecture 9 – Computational Complexity and Binary Search

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

Agenda

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

TODO

Your lab partner has a competing solution for an algorithm. You say, “I bet mine’s faster.” Your partner says, “I’ve got my watch here. We’ll let time decide the better solution.”

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];
}

// 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);
}