INF2220 ukeoppgaver uke 1 
=========================


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

Oppgaver fra Marc Allen Weiss sin bok:
Data Structures and Algorithms in Java

2.1, 2.7, 4.1, 4.2 og 4.3

(PDF ligger vedlagt)


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
---------

Vi vil bruke et bin?rt s?ketre til ? lagre et antall objekter som
inneholder en "int verdi", samt en del andre data. Vi skal anta at
hver node har en venstre og en h?yre peker p? vanlig m?te. Det kan
imidlertid v?re flere objekter som har samme verdi (men gjerne med
forskjellig data), og disse skal alle lagres som separate objekter i
treet.

a) Vi kan l?se dette ved ? g? videre nedover i treet n?r vi skal gj?re
   en innsetting, SELV OM vi treffer p? et objekt med samme verdi p?
   veien. Vi kan da velge alltid ? g? videre ned i h?yre subtre n?r vi
   passerer et objekt med samme verdi. Skriv en innsettingsmetode som
   f?lger denne filosofien, og tegn noen typiske tr?r denne kan gi
   oss.

b) I hvilken rekkef?lge vil vi f? ut objektene med lik verdi dersom vi
   skriver ut tr?rne produsert under a) i vanlig infiks rekkef?lge?
   Hvordan blir dette om vi g?r til venstre istedenfor til h?yre n?r
   vi treffer p? en node med lik verdi under innsettingen?

c) I denne oppgaven skal vi legge noder med lik verdi i en liste 
   ut fra den f?rste noden med denne verdien. 
   Dette vil imidlertid kreve at vi har en ekstra
   peker for denne listen, men vi kan klare oss som f?lger: N?r vi vil
   sette inn et objekt og det allerede finnes ett (men bare ett)
   objekt med denne verdien i treet, s? hekter vi det nye objektet inn
   mellom det gamle, og dets h?yre subtre. Dersom det senere kommer
   flere objekter med samme verdi, s? hektes disse inn p? en liste ut
   fra det ANDRE objektet, med venstre-pekeren som listepeker. TEGN
   eksempler, og skriv en innsettingsmetode som bruker denne
   filosofien.

d) Vis at dersom man skriver ut treet produsert under c) i innfiks
   rekkef?lge, s? kommer fremdeles nodene med like verdier samlet. Men
   i hvilken rekkef?lge kommer de? Skriv en modifisert utskriftsmetode
   som gj?r at noder med like verdier skrives ut i den rekkef?lge de
   ble satt inn.