INF2220 l?sning ukeoppgaver uke 1 
=================================


OPPGAVE 1:
----------

2.1) 
     2/n, 37, sqrt(n), n, n*log(log(n)), n*log(n), n*log(n^2)
     n*log(n)^2, n^(1.5), n^2, n^2*log(n), n^3, 2^(n/2), 2^n



2.7) 
     1) O(n)
     2) O(n^2)
     3) O(n^3)
     4) O(n^2)
     5) O(n^5)
     6) O(n^4)


4.1) 
    a) A
    b) G,H,I,L,M og K



4.2)  
    for node B
    
    a) A
    b) D og E
    c) C
    d) 1
    e) E



4.3)  4
   





OPPGAVE 2:
----------

a)  O(n^2)

b)  O(log2(n))




OPPGAVE 3
---------


============================================


/**
 * 
 * This binary tree has been made without a wrapper
 * class, i.e., without a BinTree class holding the
 * root and so on. We only have a pointer to the root,
 * which forces us to do some serious recursive
 * programming :-)
 *
 *
 * @author bjarneh@ifi.uio.no
 */


class Main {


    public static void main (String[] args){

        Element root = new Element(5);
        root.setData("R"); // R for root

        int[] elms = {4,23,11,11,-11,100,1,11,11,2,11,3,7,12,23,23,11,3,11};
        Element[] elements = new Element[elms.length];

        for(int i = 0; i < elements.length; i++){
            elements[i] = new Element(elms[i]);    
            elements[i].setData(""+i);
        }

        BinNode r = new BinNode(root);

        for(Element element : elements){
            r.add(element);
        }

        System.out.println("infix >> 1");
        r.printInfix();


        BinNode r2 = new BinNode(root);
        for(Element element : elements){
            r2.add2(element);
        }

        System.out.println("infix >> 2");
        r2.printInfix();
        System.out.println("fancy >> 2");
        r2.fancyPrint();

    }

}


// the elements inside our binary tree
// they are sorted based on the int 'verdi'
// and they also have a String with 'data' to
// be able to tell them apart

class Element{

    int verdi;
    String data = ""; 

    Element(int _verdi){
        verdi = _verdi;
    }

    int getVerdi(){
        return verdi;
    }

    void setData(String s){
        data = s;
    }

    public String toString(){
        return "[ d: "+data+", v: "+verdi+" ]";
    }

}


class BinNode {

    BinNode left;
    BinNode right;
    Element element;


    BinNode(Element e){
        element = e;
    }

    public Element getElement(){
        return element;
    }

    void printInfix(){

        if(left != null){
            left.printInfix();
        }

        System.out.println(element);

        if(right != null){
            right.printInfix();
        }
    }



    /**
     * oppgave 4 a)
     *
     * */

    void add(Element e){

        if(e.getVerdi() == element.getVerdi()){


            if(right == null){
                right = new BinNode(e);
            }else{
                right.add(e);
            }


        }else{

            if(e.getVerdi() < element.getVerdi()){
                if(left == null){
                    left = new BinNode(e);
                }else{
                    left.add(e);
                }

            }else if(e.getVerdi() > element.getVerdi()){
                if(right == null){
                    right = new BinNode(e); 
                }else{ 
                    right.add(e);
                }
            }
        }
    }



    /**
     * oppgave 4 d)
     *
     * */

    void semiPrefix(){

        System.out.println(element);

        if(left != null){
            left.semiPrefix();
        }

    }


    /**
     * oppgave 4 d)
     *
     * */

    void fancyPrint(){

        if(left != null){
            left.fancyPrint();
        }

        System.out.println(element);

        if(right != null){
            
            // special case
            if(right.getElement().getVerdi() == element.getVerdi()){

                right.semiPrefix();

                if(right.right != null){

                    right.right.fancyPrint();

                }

            }else{
                right.fancyPrint();
            }
        }
    }





    /**
     * oppgave 4 c)
     *
     * */

    void add2(Element e){


        if(e.getVerdi() == element.getVerdi()){

            if(right == null){
                right = new BinNode(e);
            }else if(right.getElement().getVerdi() == element.getVerdi()){
                right.addEqual(e);
            }else if(right.getElement().getVerdi() != element.getVerdi()){

                BinNode tmp = right;
                BinNode new_right = new BinNode(e);
                right = new_right;
                right.right = tmp;
            }

        }else{

            if(e.getVerdi() < element.getVerdi()){
                if(left == null){
                    left = new BinNode(e);
                }else{
                    left.add2(e);
                }

            }else if(e.getVerdi() > element.getVerdi()){
                if(right == null){
                    right = new BinNode(e); 
                }else{ 
                    right.add2(e);
                }
            }
        }
    }

    /**
     * oppgave 4 c)
     *
     * */

    void addEqual(Element e){

        // just go to bottom of left subtree and add
        if(this.left != null){
            left.addEqual(e);
        }else{
            left = new BinNode(e);
        }
    }

    // for debugging....
    void printDepth(String spacer){

        System.out.println(spacer+" "+element);

        if(left != null){
            left.printDepth("---"+spacer);
        }
        if(right != null){
            right.printDepth("---"+spacer);
        }
    }

}



=====================================