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

Föreläsning 2

• Har 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.tail != ys.head) {
            tail.next = ys.head.next;
            tail      = ys.tail;
        }
    }

Föreläsning 3

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

  • 7.

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

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

• Vad är tidskomplexiteten för att köra dequeue xs n gånger?

  • Θ(n²).

• Vilken rad i height är felaktig?

  • Rad 5. Korrekt alternativ: int largestHeight = -1;.

  (Man kan också rätta till koden genom att ändra på rad 12, men jag tycker att det leder till ett onödigt komplicerat program.)

• Om man implementerar prioritetskö-ADTn med listor, vad blir värstafallstidskomplexiteten för insert och delete-min?

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

Föreläsning 4

• Vilka träd är binära heapar?

  • A.
  • E.
  • F.

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

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

• Vilka träd är Braunheapar?

  • B.
  • E.
  • F.

• Om man kör deleteMin q, hur ser det nya trädet ut?

  • A.

• Vad är tidskomplexiteten för följande program, där i++ körs n gånger? Använd det logaritmiska kostnadskriteriet.

  • Θ(n).

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?

  • Ja.

Föreläsning 6

• Är grafer av följande typ täta?

  • Nej.

• Hur stor plats tar en graf representerad som en grannlista? (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.

• För vilka grafer ger Dijkstras algoritm rätt svar?

  • B.

Föreläsning 7

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

  • 22.

• Vad är värstafallstidskomplexiteten för Kruskals algoritm? (Anta att Edges är en binär heap och T en lista. Anta inte att ∣V∣ = O(∣E∣).)

  • Θ(∣V∣ + ∣E∣ log ∣V∣).

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

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

  • 6.

Föreläsning 8

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

  • Ja.

• 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²).

Föreläsning 9

• 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 blir resultatet av att sätta in 8 i följande splayträd?

  • C.

• Vad är det förväntade antalet noder med höjd ≥ h (exklusive vaktposten)?

  • np^h − 1.

Föreläsning 10

• 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).

• Är heapsort stabil?

  • Nej.

• Vad är tidskomplexiteten för att splaysortera en lista (med distinkta heltal) som är sorterad?

  • Θ(n).

• Vad är tidskomplexiteten för att splaysortera en lista (med distinkta heltal) som är omvänt sorterad?

  • Θ(n).

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

  • Θ(n²).