CSC 205 class notes

Fall 2017



In [ ]:

    
class Main{
    public static void main(String[] args){
        System.out.println("Testing");
    }
}

ADT Queue methods create empty queue insert delete isEmpty linked list ----------- head->[a][] [q][] [b][] [x][]->null front to back head->[x][] [b][] [q][] [a][]->null back to front



In [ ]:

    
//front to back
class Main{
    public static void main(String[] args){       
    }
}

class Link{
    public Object data;
    public Link next;
}

class Deque{
    private Link _head;
    private Deque(){
        _head = null;
    }
    public void insert(Object item){ //insert on end
        if(_head != null){
            Link finger = _head;
            while(finger.next != null){
                finger = finger.next;
            }
        }
        Link add = new Link();
        add.data = item;
        add.next = null; //already set **just good for clarity
        if(finger != null)
            finger.next = add;
        else
            _head = add;
        
    }
    public void delete(Object item){ //delete on end
        
    }
}



In [ ]:

    
//back to front
class Main{
    public static void main(String[] args){}
}
class Link{
    public Object data;
    public Link next;
}
class Deque{
    private Link _head;
    public Deque(){
        _head = null;
    }
    public Object delete(){
        if(_head == null)
            return null;
        Link finger = _head;
        Link prev = null;
        
        while(finger.next != null){
            prev = finger;
            finger = finger.next;
        }
        if(prev != null) //edge case with one item
            prev.next = null;
        else
            _head = null;
        return finger.data;
    }
}

Insert M @ 2 head->[A][]-[Q][]->[B][]->[X][]->null ->[M][]->

========================================================================================= A Graph Graph G = (N,E) N = {A,B,C,D,E} vertex or node E = {(B,A),(C,B),(C,D),(B,E),(E,C)} Edge Directed graph arrows go one way ------> Undirected graph arrows go both ways <------> Connected vs Unconnected A path is a sequence of nodes and edges A cycle is a path that starts and ends on the same node (in math) A tree is a connected graph with no cycles (in computer science) A tree is also rooted (all branches go down from the root) leafs nodes at the bottom A binary search tree a graph with no cycles, connected has one root and all edges go down to the root a binary tree each parent has no more than two children each child is "left" or "right" Value- left(less than) - right(geater than) Aa table or a Dictionary is a collection of items each with a unique identifying key Operations: lookup or search Given the key return all the data assosiated with the key.



In [ ]:

    
class Node {
    public    data;
    public Node left; //less than root
    public Node right; //greater than root
}

[40] [20] [60] [10] [30][50] [70] //binary search tree //no duplicates Binary Search tree has search by key left node key is less than parent node key right node key is greater than parent node key



In [ ]:

    
////////////////////////////////////////////////////////////////////////////////////////
class Node {
    public KeyComparable data;
    public Node left;
    public Node right;
}
interface KeyComparable {
    int compareTo(KeyComparable other);
}
class Table {
    private Node _root;
    public Table() {
        _root = null;
    }
    public KeyComparable search(KeyComparable key) {
        Node curr = _root;
        while(curr != null) {
            int comp = key.compareTo(curr.data);
            if(comp == 0) {
                return curr.data;
             }else if(comp < 0) {
                curr = curr.left;
                curr = curr.right;
            }else {
                curr = curr.right;
            }
        }
        return null;
    }
    public void insert(KeyComparable item) { //insert into binary search tree
        Node curr = _root;
        
        while(curr != null) {
            int comp = item.compareTo(curr.data);
            if (comp == 0) return;
            else if(comp < 0) curr = curr.left;
            else curr = curr.right;
        }
        Node add = new Node();
        add.data = item;
        add.left = add.right = null;
        if(parent == null)
            _root = add;
        else if(item.compareTo(parent.data) < 0) {
            parent.left = add;
        }else {
            parent.right = add;
        }
    }
    
}

Recursion N! = 1 * 2 * 3 ... (N-1) * (N) //defined recursivley N! = (N-1)! * N if N > 1 = 1 if N = 0,1 A recursive function calls itself Binary trees are naturally recursive



In [ ]:

    
int fact(int N) { //factorical code
    int product = 1;
    for(int i = 2, i <= N; ++i) {
        product = product * i;
    }
    return product;
}

//recursion
int fact(int N) {
    if(N > 1)
        return fact(N-1) * N;
    else
        return 1;
}

fibb - 1,1,2,3,5,8,13,21,34,55,89, defined recursivley fibb(i) = fibb(i-1) + fibb(i-2) if i > 2 1 if i=1,2



In [ ]:

    
//fibb code
int fibb(int i) {
    if(i >= 3) 
        return fibb(i-1) + fibb(i-2);
    else
        return 1;
}

Order for binary tree pre-order root-left-right in-order left-root-right post-order left-right-root post order ex: (30-20-40)-(70-60-80)-50



In [ ]:

    
class Node {
    public Object data;
    public Node left;
    public Node right;
    
    public Node(KeyComprable item) {
        data = item;
        left = right = null;
    }
}

interface KeyComparable {
    int KeyCompareTo(KeyComparable other);
}

class Tree {
    private Node _root;
    //////////////////////...
    public void PreOrder() {
        PreOrder(_root);
    }
    private void PreOrder(Node myRoot) { //method overload
        if(myRoot != null) {
            System.out.println(myRoot.data);
            PreOrder(myRoot.left); //recursive traversial
            PreOrder(myRoot.right);
        }
    }
}

class Table {
    private Node _root;
    public Table() {
        return _root;
    }
    public KeyComprable Search(KeyComprable key) {
        return SearchR(_root, key)
    }
    private KeyComparable SearchR(Node myRoot, KeyComparable key) {
        if(myRoot == null)
            return null;
        else {
            int comp = key.KeyCompareTo(myRoot.data);
            if(comp < 0)
                return SearchR(myRoot.left, key);
            else if(comp > 0)
                return SearchR(myRoot.right, key);
            else { 
                return myRoot.data;
            }
        }
    }
    public void Insert(KeyComprable item) {
        if(_root != null)
            InsertR(_root, item);
        else
            _root = new Node(item);
    }//assume myRoot is NOT null!
    private void InsertR(Node myRoot, KeyComprable item) {
        int comp = item.KeyCompareTo(myRoot.data);
        if(comp < 0) {
            if(myRoot.left != null)
                insertR(myRoot.left, item);
            else
                myRoot.left = new Node(item);
        }else if(comp > 0) {
            if(myRoot.right != null)
                insertR(myRoot.right, item);
            else
                myRoot.right = new Node(item);
        }
    }
}

class Main {
    public static void main(String[] args) {
        Tree t = new Tree();
        t.preOrder();
    }
}



In [ ]:

    
//bubble sort O(N^2)

public static void bubbleSort(double num[], int size) {
    boolean sorted;
    do {
        sorted = true;
        for(ix = 0; ix < size - 1; ++ix) {
            if(num[ix] > num[ix + 1]) {
                swap(num, ix, ix + 1);
                sorted = false;
            }
        }
    while(!sorted);
}

Merge Sort O(N) per level * number of levels O(logN) = NlogN //////////////////////////////////////////////////////////////////// depth or level = distance from root; height is the max distance from a leaf depth of a node is one more than the depth of the parent 1 + max(height of the left, height of the right) The height of the tree is the worst-case for search insertion. Size = SizeL + SizeR + 1 avg = sum of all node levels / number of nodes



In [ ]:

    
public int getHeight() {
    return getHeight(_root);
}
private int getHeight(Node myRoot) {
    
}



In [ ]:

    
//delete algoritm

//case 1:
    //no children
//case 2:
    //one child
//case 3:
    //two children    Find a substitute: max of left, or min of right
    //                Replace the data with the substitute
    //                Delete the substitute

class Node {
    public Comparable data;
    public Node left;
    public Node right;
}
interface Comparable {
    int compareTo(Comparable other);
}
class Table {
    private Node _root;
    public Table() {
        _root = null
    }
    public void delete(Comparable key) {
        Node curr = _root;
        Node parent = null;
        int comp;
        while(curr != null && (comp = key.compareTo(curr.data)) != 0) {
                parent = curr;
            
                if(comp < 0)
                    curr = curr.left;
                else
                    curr = curr.right;
        }
        //case 1
        if(curr == null) return;
        if(curr.left == null && curr.right == null){
            if(parent == null)
                _root = null;
            else if(key.compareTo(parent.data) < 0)
                parent.left = null;
            else
                parent.right = null;
        }
        //case 2
        else if(curr.left == null && curr.right != null) {
            if(parent == null)
                _root = curr.right;
            else if (key.compareTo(parent.data) < 0)
                parent.left = curr.right;
            else 
                parent.right = curr.right;
        }
        else if(curr.left != null && curr.right == null) {
            if(parent == null)
                _root = curr.left;
            else if (key.compareTo(parent.data) < 0)
                parent.left = curr.left;
            else 
                parent.right = curr.left;
        }
        //case 3
        else { // curr.left != null && curr.right != null
            parent = curr;
            Node sub = curr.left;
            while(sub.right != null) {
                parent = sub;    
                sub = sub.right;
            }
            curr.data = sub.data;
            parent.right = sub.left; //special cases
            if(parent == curr) {
                parent.left = sub.left;
            }else {
                parent.right = sub.left;
            }
        }
    }
}



In [ ]:

    
//recursive algorithm
public void delete(Comparable key) {
    _root = deleteR(_root, key);
}
private Node delete(Node myRoot, Comparable key) {
    if(myRoot == null) return null;
    int comp = key.compareTo(myRoot.data);
    if(comp < 0) {
        myRoot.left = delete(myRoot.left, key);
    }else if(comp > 0) {
        myRoot.right = delete(myRoot.right, key);
    }else {
        if(myRoot.left == null && myRoot.right == null)
            return null;
        else if(myRoot.left != null && myRoot.right == null)
            return myRoot.left
        else if(myRoot.left == null && myRoot.right != null)
            return myRoot.right;
        else {
            Comparable subData = findMax(myRoot.left);
            myRoot.data = subData;
            myRoot.left = delete(myRoot.left, subData);
        }
    }
}

public Comparable findMax() {
    if(_root == null)
        return null;
    else
        return findMax(_root);
}
private Comparable findMax(Node myRoot) {
    if(myRoot.right == null)
        return myRoot.data;
    else
        return findMax(myRoot.right);
}

Merge Sort if it is small enough (1 or 2): sort directly otherwise: split it in half sort each half merge the sorted halfs O(N) per level * O(log base 2 of N)levels = O(NlogN)

Height of a Node Maximum distance from the node to a leaf Height balanced tree the difference between the height of the left sub tree and the right sub tree is less than or equal to one AVL - Height Balanced Tree