Facit till föreläsningsuppgifter

Föreläsning 1

• Hur lång tid tar det att köra "java Bits 200000", jämfört med "java Bits 100000"?

  • Ca 4 ggr så lång tid.

• Blir programmet effektivt om vi lägger till 10 element istället för att göra arrayen dubbelt så stor?

  • Nej.

• Vilka påståenden är korrekta?

  • n² = Ω(n).
  • n = O(n²).
  • 10n + 7 = Θ(3n + 1).
  • 10n + 7 = Θ(13n + 12).

• Vilka analyser är korrekta?

  • A: Θ(n²).
  • B: Θ(n).

Vi hann inte med sista frågan, den kommer på nästa föreläsning.

Föreläsning 2

• Kan man ge add och remove amorterade tidskomplexiteten O(1) om man halverar arrayen när den blir…

  • …halvfull? Nej.

  • …kvartsfull? Ja.

• Vilken rad i addFirst är felaktig?

  • Rad 6. Korrekt alternativ: first.next.prev = node;.

• Är implementationen av append korrekt?

  • Nej. Korrekt variant:

    void append(List<A> ys) {
        if (ys.last != ys.first) {
            last.next     = ys.first.next;
            last          = ys.last;
            ys.first.next = null;
            ys.last       = ys.first;
        }
    }

Sista frågan kommer på nästa föreläsning.

Föreläsning 3

• Hur många consceller innehåller tails [1, 2, 3] (när uttrycket är fullt evaluerat)?

• Vilka datastrukturer ger O(1) enqueue och dequeue (ev amorterat) för FIFO-köer?

  • Cirkulära, dynamiska arrayer.
  • Enkellänkade listor med pekare till sista noden.
  • Dubbellänkade listor med pekare till två vaktposter (först och sist).

• Vad är tidskomplexiteten?

  • Θ(n²).

• Vad blir resultatet av att applicera s på följande träds rot?

• Om man implementerar prioritetskö-ADTn med listor, vad blir tidskomplexiteten (ev amorterad) för insert och delete-min?

  • insert: Θ(1), delete-min: Θ(n).
  • insert: Θ(n), delete-min: Θ(1).

  Notera att den här frågan inte är helt korrekt formulerad, se föreläsning 4.

• Identifiera alla binära heapar.

  • A.
  • E.
  • F.

Föreläsning 4

• Vad blir resultatet om delete-min appliceras på den givna binära heapen?

  • D.

• Konstruera en sorteringsalgoritm baserad på binära heapar. Vad är dess tidskomplexitet, givet att jämförelser tar konstant tid?

  • O(n log n).
  • O(n²).
  • O(n² log n).

• Identifiera leftistheaparna.

  • A.
  • D.
  • F.

• Vad är resultatet av att applicera deleteMin på den givna leftistheapen?

  • B.

Föreläsning 5

• Hur många kollisioner inträffar?

  • 2.

• Vad är tidskomplexiteten för borttagande av n strängar, var och en med n tecken, från en hashtabell som innehåller alla strängarna? Anta att hashfunktionen är perfekt, och linjär i strängarnas storlek.

  • Θ(n²).

• Vad är bästa- och värstafallstidskomplexiteten för insertionSort, givet att jämförelser tar konstant tid?

  • Θ(n), Θ(n²).

• Är mergeSort stabil?

  Förtydligande: Frågan gäller den variant av mergeSort som presenterades på föreläsningen.

  • Ja.

Föreläsning 6

• Gäller |E|  =  Θ(|V|²) för följande klass av grafer?

  • Nej.

• Hur stor plats tar en array med grannlistor? (Anta att etiketter/vikter tar liten plats.)

  • Θ(|V|+|E|).

• Analysera värstafallstidskomplexiteten.

  • Θ(|V|+|E|).

• Vad händer om man använder en stack istället för en kö?

  • Algoritmen fungerar fortfarande, och värstafallstidskomplexiteten är fortfarande Θ(|V|+|E|), men resultatlistan blir inte alltid ordnad på samma sätt som om man använder en kö.

• Fungerar algoritmen för viktade grafer (om + 1 byts ut mot + vikten av kanten från v till v'? Testa!

  • A: Ja.
  • B: Nej.

• Ger Dijkstras algoritm rätt svar för följande grafer?

  • A: Nej.
  • B: Ja.

Föreläsning 7

• Vad är den totala vikten av följande två grafers minsta uppspännande träd?

  • 22.

• Hur många bakåtkanter innehåller DFS-skogen för följande graf, givet att vi, då vi kan välja mellan flera noder, alltid väljer den lägst numrerade noden?

  • 2.

• Vilka sekvenser är korrekta topologiska sorteringar av följande graf?

  • 1, 2, 3, 4, 5, 6, 7.
  • 2, 4, 1, 3, 6, 5, 7.

• Hur många starkt sammanhängande komponenter innehåller följande graf?

  • 6.

• Ger följande funktion en lista av starkt sammanhängande komponenter som svar?

  • Ja.

Föreläsning 8

• Vilka träd är binära sökträd?

  • B.
  • C.
  • F.

• Vad är värstafallstidskomplexiteten för inorder t (om t innehåller n element)?

  • Θ(n²).

• Vilka träd är AVL-träd?

  • A.
  • B.
  • C.
  • F.

• Vad blir resultatet av att sätta in 5 i följande AVL-träd?

  • A.

• Vad är värstafallstidskomplexiteten för att testa medlemskap av en sträng i en mängd som innehåller n strängar? Varje sträng har längd ℓ, prefixträdet använder arrayer, och hashfunktionen har tidskomplexiteten Θ(ℓ).

  • Hashtabell: Θ(ℓn).
  • Prefixträd: Θ(ℓ).
  • AVL-träd: Θ(ℓ log n).

  (Förtydligande: Alfabetet kan antas innehålla Ω(n) tecken.)

Föreläsning 9

• I en skipplista med n noder, vad är det förväntade antalet noder med höjd ≥h (exklusive vaktposten)?

  • np^h − 1.

• Ge en skarp undre gräns för antalet löv i ett beslutsträd.

  • n!.

• Vad är tidskomplexiteten för hinksortering? Anta att bucket tar konstant tid.

  • Θ(N + n).

Föreläsning 10

• Är heapsort stabil?

  • Nej.

• Vad är värstafallstidskomplexiteten för quicksort om p alltid är arraysegmentets första element? Anta att partitionering tar linjär tid.

  • Θ(n²).

Föreläsning 11

• Vilka påståenden är sanna?

  • 5n² + 3n + 7  =  O(n²).
  • log₂ (n²)  =  Θ(log n).
  • 5n + 2log₂ (7n + 3)  =  O(n).

• Vad är tidskomplexiteten för följande program, där i++ körs n gånger? Använd det logaritmiska kostnadskriteriet. (Se int som en dynamisk array med bitar.)

  • Θ(n).

  Notera: Svaret ovan gäller om vi ser int som en dynamisk bitarray, eller som en statisk bitarray med max(1, ⌈log₂ (n + 1)⌉) element, och i++ implementeras på ett effektivt sätt. I den kanske vanligaste varianten av den logaritmiska kostnadsmodellen har dock i++ tidskomplexiteten "antalet bitar i den binära representationen av i", och då blir svaret Θ(n log n).

• Klassificera träden: Binär minheap, leftistminheap, AVL-träd.

  • A: AVL-träd.
  • B: Leftistminheap.
  • D: Binär minheap, leftistminheap.