INF2220 ukeoppgaver uke 1 (27/8-31/8)
=====================================



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

MAW (Marc Allen Weiss) oppgave 2.1 og 2.7


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

a)  F?lgende programbit vil sortere en heltallsarray int[] A = new
    int[n]. Av hvilken orden er tidsforbruket til dette programmet?
    (Big-O klassifisering)


	for (int i = 0; i < n; i++) {
		minj = i;
		for (j = i + 1; j < n; j++) {
			if (A[j] < A[minj]) {
				minj = j;
			}
		}
		bytt(i, minj);
	}



b)	For en gitt n > 0, hvilken verdi vil ligge i variabelen L2
	etter kj?ringen av denne programbiten? (gitt som en funksjon av n)  
	Av hvilken orden er tidsforbruket til programmet? (Big-O klassifisering)


	i = 1;
	L2 = -1;
	while (i <= n) {
		i = i * 2;
		L2++;
	}






OPPGAVE 3:
----------

MAW oppgave 4.1, 4.2, 4.3


OPPGAVE 4:
----------

I denne oppgaven skal vi se p? en type Tre der nodene
kan ha ubegrenset med barn. Disse nodene er representert
ved klassen TreeNode, det er 2 (rekursive) funksjoner dere skal
implementere.


   boolean findNode(String _id)


denne funksjonen skal returnere true dersom det finnes
en node med id lik _id. 


   int max()


denne funksjonen skal returnere antallet barn
til den noden i treet med flest barn.





(hvis klassen LinkedList er ukjent se Java API 
dokumentasjonen p? nett, evt. bruk google til ? finne 
noen eksempler p? bruk. se ogs? prettyPrint funksjonen 
for eksempel p? gjennoml?ping av en LinkedList med Java
sin foreach-variant, samt eksempel p? rekursiv funksjon) 






------------------------- Main.java -------------------------------


import java.util.LinkedList;


class Main{

	public static void main(String[] args){

		TreeNode root = new TreeNode("one");
		TreeNode t2 = new TreeNode("two");
		TreeNode t3 = new TreeNode("three");
		TreeNode t4 = new TreeNode("four");
		TreeNode t5 = new TreeNode("five");
		TreeNode t6 = new TreeNode("six");
		TreeNode t7 = new TreeNode("seven");
		TreeNode t8 = new TreeNode("eight");
		TreeNode t9 = new TreeNode("nine");
		TreeNode t10 = new TreeNode("ten");
		TreeNode t11 = new TreeNode("eleven");
		TreeNode t12 = new TreeNode("twelve");

		root.addChild(t2);
		root.addChild(t3);
		t2.addChild(t4);
		t2.addChild(t5);
		t2.addChild(t6);
		t4.addChild(t7);
		t5.addChild(t8);
		t5.addChild(t9);
		t5.addChild(t10);
		t5.addChild(t11);
		t5.addChild(t12);

		System.out.println("\nmax number of children : "+root.max()+"\n");

		root.prettyPrint();

		System.out.println("\nSearching for node 'seven'. found = "+root.findNode("seven"));
		System.out.println("\nSearching for node 'twenty'. found = "+root.findNode("twenty"));

	}



}




class TreeNode {

	TreeNode(String _id){
		this.id = _id;
		this.children = new LinkedList<TreeNode>();
	}

	String id;
	LinkedList<TreeNode> children;


	void addChild(TreeNode t){
		this.children.add(t);
	}

	int size(){
		return children.size();
	}


	int max(){

		// TODO

		return -1;
	}

																	
				
	public boolean findNode(String _id){

		// TODO

		return false;
	}


	public String toString(){
		return id;
	}




	/**
	*	fake default value with overloaded
	*	prettyPrint function, ie. we fake this
	*	construct:
	*
	*	  prettyPrint(spacer="")
	*
	*	since the root-node needs no spacing	
	*
	*/

	void prettyPrint(){
		prettyPrint("");
	}

	void prettyPrint(String spacer){

		System.out.println(spacer + this);

		for(TreeNode child : children){
				child.prettyPrint(spacer.replace('|','-').replace('-',' ') + "|--- ");
		}
	}

}