Computer Science 1027A/B Study Guide - Final Guide: Longest Path Problem, Binary Logarithm, Preorder
1 Jul 2018
School
Department
Course
Professor
Runtime errors:errors are unrecoverable situations,running out of memory runtime exceptions: Exceptions can be handled in some way Example: division by zero (lets ask them to try again, logic error). Examples of Java
predefined exception classes (types): ArithmeticException(divide by 0), IndexOutOfBoundsException, IOException(reading character a when you expect integer),NullPointerException.throwable:error,exception.error:linkage error,
threaddeath, virtual machine error, AWTError. Exception:runtimeexception,,illegalaccessException,nosuchmethodexception,classnotfoundexception.runtimeexception:arithmetic exception,indexoutofboundsexception,
nullpointerexception.Advantages of linked lists:- The items do not have to be stored in consecutive memory locations: the successor can be anywhere physically. So, can insert and delete items without shifting data Can increase the
size of the data structure easily - Linked lists can grow dynamically (i.e. at run time) - the amount of memory space allocated can grow and shrink as needed.Import java.util.Random to have random numbers.Expand Capacity
circular array: To expand capacity, make a new error and keep incrementing the front using the front = (front +1)%100 and copy the element onto the new array. Now the front becomes 0 and have a count for the queue and set the
reartothatfloat a = 7.0 or double a= 7.0. A list: int [] list = {0,1,2,3}; A tuple: final int [] constant = {0,1,2,3}; list certain length int [] arrayA = new int[10];Can’t make object for interfaceclass. (X varX = new X(); Y varY = varX; // Line 1
varY = new Y(); varX = varY; // Line 2 makes the error and Y is super) (Y varY = new Y(); X varX = (X) varY; // Casting varX.m(); -> creates runtime error)(Y varY = new X();varY.m();->this makes no errors).Getting userinput import
java.util.Scanner;System.out.println ("Enter a valid postfix expression: ");expression = in.nextLine();. An interface just has the method names. O(1) for things not O(n).
public class CircularArrayQueue<T> implements
QueueADT<T>
{private final int DEFAULT_CAPACITY = 100;
private int front, rear, count;
private T[] queue;
public CircularArrayQueue(){
front = rear = count = 0;
queue = (T[]) (new
Object[DEFAULT_CAPACITY]);}
public CircularArrayQueue (int initialCapacity){
front = rear = count = 0;
queue = ( (T[])(new Object[initialCapacity]) );}
public void enqueue (T element){
if (size() == queue.length)
expandCapacity();
queue[rear] = element;
rear = (rear+1) % queue.length;
count++;}
public T dequeue() throws
EmptyCollectionException{
if (isEmpty())
throw new EmptyCollectionException ("queue");
T result = queue[front];
queue[front] = null;
front = (front+1) % queue.length;
count--;
return result;}
public T first() throws EmptyCollectionException{
if (isEmpty())
throw new
EmptyCollectionException ("queue");
return queue[front];}
public boolean isEmpty() {
return (count==0);}
public int size(){
return count;}
public String toString() {
String result = "" ;
for (int i = 0 ; i < count ; i++ ){
result += queue[ (front + i) % queue.length ] +
"\n" ; }
return result ;}
public void expandCapacity(){
T[] larger = (T[])(new Object[queue.length *2]);
for(int scan=0; scan < count; scan++){
larger[scan] = queue[front];
front=(front+1) % queue.length;}
front = 0;
rear = count;
queue = larger;}
}
public class BinaryTreeNode<T> {similar in linear
node in simplicity of most methods
public int numChildren() {
int children = 0;
if (left != null)
children = 1 + left.numChildren();
if (right != null)
children = children + 1 + right.numChildren();
return children;}
public class LinkedStack<T> implements
StackADT<T> {
private int count;
private LinearNode<T> top;
public LinkedStack() {
count = 0;
top = null;
}
public void push (T element) {
LinearNode<T> temp = new LinearNode<T>
(element);
temp.setNext(top);
top = temp;
count++;
}
public T pop(){
if (isEmpty())
throw new EmptyCollectionException("Stack");
T result = top.getElement();
top = top.getNext();
count--;
return result;
}
public T peek() {
if (isEmpty())
throw new EmptyCollectionException("Stack");
return top.getElement();
}
public class LinearNode<E>
{ things like getNext() wich is just return next and
setElement which is element=elem
}
public class EmptyCollectionException extends
RuntimeException{
public EmptyCollectionException (String collection)
{
super ("The " + collection + " is empty.");
}}
import java.util.*;
public class ArrayIterator<T> implements Iterator
{
private int count;
private int current;
private T[] items;
public ArrayIterator (T[] collection, int size) {
items = collection;
count = size;
current = 0;}
public boolean hasNext() {
return (current < count);}
public T next(){
if (! hasNext())
throw new NoSuchElementException();
current++;
return items[current - 1];
}
public void remove() throws
UnsupportedOperationException{
throw new UnsupportedOperationException();}
}
public class ArrayOrderedList<T> extends
ArrayList<T> implements OrderedListADT<T> {
public ArrayOrderedList() {
super();}
public ArrayOrderedList (int initialCapacity) {
super(initialCapacity);}
public void add (T element) {
if (size() == list.length)
expandCapacity();
Comparable<T> temp =
(Comparable<T>)element;
int scan = 0;
while (scan < rear && temp.compareTo(list[scan])
> 0) {
scan++;}
for (int scan2 = rear; scan2 > scan; scan2--) {
list[scan2] = list[scan2-1];}
list[scan] = element;
rear++;}
}
Analysis Algorithms:
Ex. x = 0;
for (int i = 0; i < n; i++)
x = x + 1;
So kn+k` this is O(n)
Ex. for (int i=0; i<n; i++) {
x = x + 1;
for (int j=0; j<n; j++)
y = y – 1;
}
The loop is O(n2) because the loop executes n times
and the body of the loop, including a nested loop, is
O(n). K will run for n times so kn and p will run n
times so pn so kn x pn = kpn^2 so(t(n) = n(k’ + kn) =
k’n + kn2) On^2. Don’t bother with the lines in the for
loop only focus on how many times the loop runs.
Ex.
x = 0;
for (int i=0; i<n; i=i+2) {
x = x + 1;
}
algorithm is k’ + kn/2. The time complexity of this
algorithm, then is O(n).(1/2n -> O(n))
Ex. x = 0;
for (int i=0; i<n; i++)
for (int j = i, j < n, j ++) {
x = x + 1;
}
O(n2).
public class ArrayUnorderedList<T> extends
ArrayList<T>
implements UnorderedListADT<T>{
public ArrayUnorderedList(){
super();}
public ArrayUnorderedList (int initialCapacity){
public class ArrayStack<T> implements
StackADT<T>
{
private final int DEFAULT_CAPACITY = 100;
private int top;
private T[] stack;
public ArrayStack() {
top = 0;
stack = (T[])(new Object[DEFAULT_CAPACITY]);}
public ArrayStack (int initialCapacity){
top = 0;
stack = (T[])(new Object[initialCapacity]);}
public void push (T element){
if (size() == stack.length)
expandCapacity();
stack[top] = element;
top++;}
public T pop() throws EmptyCollectionException {
if (isEmpty())
throw new EmptyCollectionException("Stack");
top--;
T result = stack[top];
stack[top] = null;
return result;}
public T peek() throws EmptyCollectionException {
if (isEmpty())
throw new EmptyCollectionException("Stack");
return stack[top-1];}
public boolean isEmpty(){
return (top == 0);}
public int size(){
return top;}
public String toString(){
String result = "";
for (int scan=top-1; scan >= 0; scan--)
result = result + stack[scan].toString() + "\n";
return result;}
private void expandCapacity(){
T[] larger = (T[])(new Object[stack.length*2]);
for (int index=0; index < stack.length; index++)
larger[index] = stack[index];
stack = larger;}
}
public class Phone implements
Comparable<Phone>{
public int compareTo(Phone obj) {
return phone.compareTo(obj.phone);
}
Can concatenate int and string it becomes string.
public class PhoneTest {
public static void main(String[] args) throws
Exception {
ArrayOrderedList<Phone> phoneList=new
ArrayOrderedList<Phone>();
String name, phone;
do {
name = (reader.read());
phone = (reader.read());
Phone tempName=new Phone();
tempName.setName(name);
phoneList.add(tempName);
Phone tempPhone = new Phone();
tempPhone.setPhone(phone);
phoneList.add(tempPhone);
} while (!reader.endOfFile());
System.out.println("Here is my phone book:");
ArrayIterator<Phone>(phoneList,5);
Iterator<Phone> iter = phoneList.iterator();
while(iter.hasNext()) {
System.out.println(iter.next());
reader.close();
System.out.println("\nFile " + filename + " is
closed.");
}
}
public class QuickSort {
private int partition(int arr[], int low, int high) {
int tempArr[] = new int[high+1];
int pivot = arr[high];
int j=0;
for(int i =0; i<= high;) {
if(arr[i]<pivot) {
tempArr[j]=arr[i];
public class LinkedQueue<T> implements
QueueADT<T>{
private int count;
private LinearNode<T> front, rear;
public LinkedQueue() {
count = 0;
front = rear = null;}
public void enqueue (T element){
LinearNode<T> node = new
LinearNode<T>(element);
if (isEmpty())
front = node;
else
rear.setNext (node);
rear = node;
count++;}
public T dequeue() throws
EmptyCollectionException{
if (isEmpty())
throw new EmptyCollectionException ("queue");
T result = front.getElement();
front = front.getNext();
count--;
if (isEmpty())
rear = null;
return result;}
public T first() throws EmptyCollectionException{
if (isEmpty())
throw new EmptyCollectionException ("queue");
return front.getElement();}
public boolean isEmpty() {
return (count == 0);}
public int size(){
return count;}
public String toString(){
String result = "";
LinearNode<T> current = front;
while (current != null){
result = result +
(current.getElement()).toString() + "\n";
current = current.getNext();}
return result;}
}
public class TowersOfHanoi{
private int totalDisks;
public TowersOfHanoi (int disks){
totalDisks = disks;}
public void solve () {
moveTower (totalDisks, 1, 3, 2);}
private void moveTower (int numDisks, int start, int
end, int temp) {
if (numDisks == 1)
moveOneDisk (start, end);
else {
moveTower (numDisks-1, start, temp, end);
moveOneDisk (start, end);
moveTower (numDisks-1, temp, end, start);}
}
private void moveOneDisk (int start, int end){
System.out.println ("Move one disk from " + start
+ " to " +
end);}
}
public class RecursionLab{
public static void reversePrint (String inString){
if (inString.length() > 0){
System.out.print(inString.charAt(inString.length()-1));
inString =
inString.substring(0,inString.length()-1);
reversePrint(inString);}
else {return;}
}
public static String reverseString(String inString) {
String result = "";
if(inString.length() == 0) {return "";}
else {return result =
inString.charAt(inString.length()-1) +
reverseString(inString.substring(0,inString.length()-1)
);}
}
public static void main(String[] args){
String inString = "abcde";
reversePrint(inString);
String revString =
reverseString(inString);
