Ch 1, 2 & 4 –Big-O notation (very important!), Basic Java, Collection/Array
Given a equation f(n) = an2+bn+c+…, O(n) = ?
Given a java program/method, What is the Big-O notation for the method? Explain how you derive it?
W02 - Ch 3 & 7 – Linked Bag, Iterator and Generic Programming –
Linked List implementation (IntLinkedBag, IntNode, etc.) – complete implementation of a method in the
[ANNOTATION:
BY 'Unknown Author'
ON '2019-06-01T21:43:15'
NOTE: 'TODO: confirm what this is']LinkedList class:
add, remove, listsearch, union, etc…)
IntNode
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);
}
IntLinkedBag:
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;
}
Convert a LinkedList class to a generic ADT
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”));
1. Change name of class
public class IntArrayBag implements Cloneable
public class ArrayBag<E> implements
2. Change type of Data Array
private int[ ] data;
private Object[] data;
3. Change type of the element
public boolean remove (int target)
public boolean remove (E target)
4. Change static method
public static IntArrayBag union(IntArrayBag b1, IntArrayBag b2)
public static <E> ArrayBag<E> union(ArrayBag<E> b1, ArrayBag<E> b2)
Generic methods
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;
}
5. Typecast the element returned
return data[i];
return (E) data[i];
6. Suppress warnings
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];
}
7. Update equality tests
== and !=
== ~> obj1.equals(obj2)
!= ~> !(obj1.equals(obj2))
8. How to treat null reference
For example, when target in countOccurences(E target) is null
9. Set unused reference to null.
10. Update all documentation
Complete a LinkedList diagram (see the sample exam question 3(A)-ii)
Advantages of generic programming
-
•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.
Make a class:
Iterable
Interface Iterator<E>
boolean hasNext();
E next();
remove(); -> optional
Cloneable, etc.
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();
}
}
}
Ch 6 – Stack and Its Applications
import java.util.Stack
Stack<String> myStrStack = new Stack<String>();
myStrStack.push(“CSU”);
System.out.println(myStrStack.peek());
Evaluating postfix
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 /) +) *)
Infix to postfix conversion
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
Check balanced parentheses
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”
Reversing a word
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());
}
}
Java Stack Implementation, etc.
Ch 6 – Queue and its applications
implementing check palindromes method using java
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);
}
Implementation of a method (e.g., add, remove, etc.) in the LinkedQueue class, etc.
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
}
Ch 5 – Recursive thinking – complete a java recursive method to:
Two fundamental rules
Provide a base case or stopping condition, which is non-recursive.
Provide a recursive general case and progress towards the base case.
lines(int m, int n) // Print a pattern (lines of m to n asterisks)
Compute factorial
Compute Fibonacci
Display valid moves for tower of Hanoi, etc.
Ch 8 – Tree
pre-, in- and post-order traversal (java implementation and examples)
BTNode class implementation, etc.
Ch 14 – Graphs
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.
Ch 11 – Search
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
Ch 12 – Sorting
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