public class IntNode
{
// Invariant of the IntNode class:
// 1. The node's integer data is in the instance variable data.
// 2. For the final node of a list, the link part is null.
// Otherwise, the link part is a reference to the
// next node of the list.
private int data;
private IntNode link;
public IntNode(int initialData, IntNode initialLink)
{
data = initialData;
link = initialLink;
}
public static IntNode listSearch(IntNode head, int target)
{
IntNode cursor;
for (cursor = head; cursor != null; cursor = cursor.link)
if (target == cursor.data)
return cursor;
return null;
}
public void removeNodeAfter( )
{
link = link.link;
}
public void addNodeAfter(int item)
{
link = new IntNode(item, link);
}
public void add(int element)
{
head = new IntNode(element, head);
manyNodes++;
}
public boolean remove(int target)
{
IntNode targetNode; // The node that contains the target
targetNode = IntNode.listSearch(head, target);
if (targetNode == null)
// The target was not found, so nothing is removed.
return false;
else
{ // The target was found at targetNode. So copy the head data to targetNode
// and then remove the extra copy of the head data.
targetNode.setData(head.getData( ));
head = head.getLink( );
manyNodes--;
return true;
}
}
public static IntLinkedBag union(IntLinkedBag b1, IntLinkedBag b2)
{
// The precondition requires that neither b1 nor b2 is null.
// If one of them is null, then addAll will throw a NullPointerException.
IntLinkedBag answer = new IntLinkedBag( );
answer.addAll(b1);
answer.addAll(b2);
return answer;
}
public class ArrayBag <E> implements Cloneable{
private Object[ ] data;
private int manyItems;
……
public void add(E element){
if (manyItems == data.length){
ensureCapacity((manyItems + 1)*2);
}
data[manyItems] = element;
manyItems++;
}
}
ArrayBag <Integer> bagOfAges = new ArrayBag <Integer>();
bagOfNames.add(1);
ArrayBag <Color> bagOfColors = new ArrayBag <Color>();
bagOfNames.add(new Color(“blue”));
public class IntArrayBag implements Cloneable
public class ArrayBag<E> implements
private int[ ] data;
private Object[] data;
public boolean remove (int target)
public boolean remove (E target)
public static IntArrayBag union(IntArrayBag b1, IntArrayBag b2)
public static <E> ArrayBag<E> union(ArrayBag<E> b1, ArrayBag<E> b2)
Declare a generic method by defining type parameters between the method modifiers and the method return type
public static <T> boolean contains( T[ ] arr, T x ) {
for ( T val: arr )
if ( x.equals( val ) )
return true;
return false;
}
return data[i];
return (E) data[i];
grab() method returns (E) data type.
The data returned must == the data added
@SuppressWarnings("unchecked")
public E grab( ){
int i;
if (manyItems == 0)
throw new IllegalStateException("Bag size is zero");
i = (int)(Math.random( ) * manyItems);// + 1;
System.out.println("int is " + i);
return (E) data[i];
}
== and !=
== ~> obj1.equals(obj2)
!= ~> !(obj1.equals(obj2))
For example, when target in countOccurences(E target) is null
•Generics enable you to detect errors at compile time rather than at runtime
◦makes the program more reliable.
•Generics let you parameterize types.
◦Reduce duplicate code when same functionality applies to diff types
•autoboxing: Automatic Conversion between Primitive Types and Wrapper Class Types.
•No casting needed to retrieve a value from a list with a specified element type, because the compiler already knows the element type.
Interface Iterator<E>
boolean hasNext();
E next();
remove(); -> optional
public class FuckHead implements Cloneable {
protected FuckHead clone() {
try {
return (FuckHead) super.clone();
} catch (CloneNotSupportedException e) {
// TODO Auto-gddenerated catch block
e.printStackTrace();
throw new RuntimeException();
}
}
}
import java.util.Stack
Stack<String> myStrStack = new Stack<String>();
myStrStack.push(“CSU”);
System.out.println(myStrStack.peek());
Infix 1+2
Postfix 1 2 +
Infix Postfix
while get next operator or digit:
Push digits onto the stack until you hit an operator.
Pop 2 didgits and evaluate.
push result onto the stack.
Pop stack for results
( (A * B) + (C / D) ) ~> ( (A B *) (C D /) +)
((A * (B + C) ) / D) ~> ( (A (B C +) *) D /)
(A * (B + (C / D) ) ) ~> (A (B (C D /) +) *)
When you hit operator push to stack
When you hit number push to ouput.
When you hit left parenthesis push to stack.
When you hit right parentheses pop operators from stack until left perenthesis.
On push when top of stack has precedence over operator being pushed → pop stack before push
fail = false
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')‘ ){
if stack is empty
fail = true
else
pop a character off the stack
}
}
If stack is empty && !fail
print "balanced"
else
print “unbalanced”
public static void reverse(String word) {
Stack<Character> chars = new Stack<Character>();
for (Character c : word.toCharArray()) {
chars.push(c);
}
while (!chars.isEmpty()) {
System.out.print(chars.pop());
}
}
public static void reverse(String word) {
Stack<Character> chars = new Stack<Character>();
Queue<Character> rev = new LinkedList<Character>();
for (int i = 0; i < word.length(); i++) {
chars.push(word.charAt(i));
rev.offer(word.charAt(i));
}
boolean isPalindrome = true;
while (!rev.isEmpty() && !chars.isEmpty()) {
Character a = rev.poll();
Character b = chars.pop();
System.out.println(a + " : " + b);
isPalindrome = (a.equals(b)) ? isPalindrome : false;
}
System.out.println("Is palindrome:" + isPalindrome);
}
public static void Q( ) {
Queue<Integer> q = new LinkedList<Integer>();
q.add(69);
q.offer(666);
boolean contains = q.contains(13);
Integer next = q.peek();
boolean remove = q.remove(666);
next = q.poll();
System.out.println(next); // 69
}
Provide a base case or stopping condition, which is non-recursive.
Provide a recursive general case and progress towards the base case.
pre-, in- and post-order traversal (java implementation and examples)
BTNode class implementation, etc.
Explain depth-first search algorithm
Explain how DFS traverses for a given example graph
Explain breadth-first search algorithm
Explain how BFS traverses for a given example graph
Implementation of a method in the Graph class (add node/edge, find neighbours, etc.
Write the binary search algorithm with recursion
Write the binary search algorithm without recursion
Describe (step by step) the binary search process for a given array
Write the sequential search algorithm
Describe the sequential search process for a given array
Write the hashing algorithm
Describe (step by step) hashing algorithm for a given array
Write the selection sort algorithm
Describe the selection sort process for a given array
Write a merge sort algorithm
Describe the merge sort process for a given array
Write the quick sort algorithm
Describe the quick sort process for a given array, and
Write the insertion sort algorithm and describe the selection sort process for a given array