CS 245 Lecture 9 – Computational Complexity and Binary Search
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
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];
}
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
It’s called “ordering”
Picking one meal’s hard enough
No room for seconds
Picking one meal’s hard enough
No room for seconds