Tenta Mars 10

Uppgift 1

a) for-loopen har tidkomplexiteten O(logN) pga funktionen halverar varje gång.

b) Antingen kommer den kanske aldrig hitta talet vi sökte efter (NOT_FOUND) eller så kommer den hoppa fram och tillbaka mellan vänster-halvan och höger-halvan och i värsta fall fastna i en evig loop.

c) Vet inte ifall detta är bästa men det är en lösning
metoden börjar i mitten av arrayen och kollar ”grann-elementerna” till mid osv för att se ifall arrayen är sorterad
 public boolean check (int [] a, int x){
	mid = a.length/2;
	low = mid-1;
	high = mid+1;

	while (high <= a.length || low >= 0{
		if (high <= a.length && a[high] > a[high+1){
			return false;
			high++;
		}

		if (low => 0 && a[low] < a[low-1]{
			return false;
			low++;
		}
		return true;

d) Eftersom tidskomplexiteten kommer vara O(n) för att kolla om arrayen är sorterad så kommer O(n) vara den dominanta. Då binarySearch är O(logN). Vilket i detta fal försämrar tidskomplextiteten och Tonys lösning är värdelös

Uppgift 2

a1) De personer som är födda samma år kommer att läggas på samma plats och kollision kommer hända.
Istället hade man kunnat välja hela personnumret istället då varje personnr är unikt.

a2) vid pop() vid position 0 kommer ej gå ifall vi gör push() flera gånger. Eftersom vid pop() i stackar så tar vi alltid det senaste elementet som senast pushades in. (TopOfStack)
Hade man velat ha ut ett element med ett speciellt index hade vi kunnat använda en annan datastruktur, typ ArrayList

b) o c) har jag inte skrivit ned tyvärr

Uppgift 3
public class BoundedBuffer {
	ListNode head;
	ListNode tail;
	int maxSize;
	int size;

	public BoundedBuffer(int theSize){
		head = new ListNode(head);
		tail = new ListNode(tail);
		maxSize = theSize;
		size = 0;
	}

	//Sätter in elementet x i bufferten om den inte är full.
	//Om bufferten innehåller maximalt antal tillåtna element genereras BuffertOverflowException
	public void insert(Object x){
		ListNode nynode = new ListNode(x);
		ListNode temp = head;

		if (isFull()){
			System.out.println("BuffertOverflowException!");
		}
		while (temp != tail){
			if (temp.next == tail){
				temp.next = nynode;
				x.next = tail;
				size++;
				break;
		}
		temp = temp.next;
	}

	//Returnerar och tar bort första elementet i bufferten.
	//Om bufferten är tom returneras null.
	public Object getFirst(){
		if(head.next == tail){
			return null;
		}
		Object remove = head.element;
		head = head.next;
		return remove;
	}

	//Undersöker om bufferten är tom
	public boolean isEmpty() {
		return size == 0;
	}

	//Undersöker om bufferten innehåller maximalt antal tillåtna element
	public boolean isFull() {
		return size == maxSize;
	}

	//Skriver ut innehållet i bufferten
	public void print(){
		ListNode node = head.next;
		while (node != tail){
			System.out.println(node.element);
			node = node.next;
	}
}

Uppgift 4

a1) Nej det är inte ett binärt sökträd. Ett binärt sökträd har maxim två barn för varje nod. Elementen är även ordnade. Lägre värde till vänster och högre värde till höger.
För vilken nod som helst i trädet, alla noder som innehåller ett värde mindre än sitt eget värde befinner sig i det vänstra delträdet.
Alla noder som innehåller ett värde som är större än sitt värde befinner sig i det högra delträdet.

a2) Ja det är ett balanserat träd. Eftersom höjdskillnaden mellan det vänstra och högra delträdet är maximun 1.

a3) Ja, det är en MinHeap. Värdet i förälder är alltid mindre än sina barn. Objektet med den minsta prioritetsnumret (högst prioritet) finns alltid i roten vid minHeap.

b) Postfix: 5 3 4 2 ^ * 6 / +

c1) 34 45 3 67 65 1 17  19

c2) Problemet som uppstår är att de andra värdena som har samma index kommer att försvinna. Vid remove måste vi sätta en ”markering” ifall andra element har samma plats.

d) QuickSort använder en divide and conquer - strategi som går ut på att man delar ett problem i två mindre ”subproblem” rekursivt repeterade gånger (tills det inte går att dela mer).

7 13 5 2 18 10
Välj ut pivot genom att ta left(7), mid(2), right(10) i arrayen. medianen är 7 av dom 3.
Lägg minsta värdet till left och pivoten o störta värdet till right.

2 13 5 18 7 10

pivot = 7
left = 13
right = 5 byt plats på left och right

2 5 13 18 7 10

pivot = 7
left = 13 byt plats på pivot och left

2 5 7 18 13 10

Elementen till vänster är mindre än 7. Elementen till höger är större än 7.
Vilket ger oss två nya subproblem.

vänstra halvan:	2 5 		-> left = 2, right = 5. Färdig!
pivot		7 		-> pivot index
högra halvan:	18 13 10 	-> left = 18, right = 10

Så nu kör vi quickSort på högra halvan bara. osv osv osv osv :) :)