DA3009 Programmeringsteknik för Datorlingvistik

Algoritmlabb

Innehåll:
Komplexitet, sökning, sortering.

Denna labb redovisas på gruppmötet på måndag. Ta med dina program och resultat samt dina svar på instuderingsfrågorna. Vid redovisningen ska du kunna förklara både program och svar för dina kurskamrater och din assistent.

Uppgift 1:

Skriv ett program med två nästlade for-slingor, som går igenom alla alfabetets bokstäver och skapar en lista med tvåbokstavsorden:

aa, ab, ac, ... , öö

Använd time-modulen för att mäta körtiden. Låt även programmet skriva ut antal ord.

Bygg nu ut programmet så att det skapar ord med tre bokstäver, och skriv ner dina resultat. Fortsätt att bygga ut på samma sätt tills programkörningen verkar ta orimligt lång tid.

Uppgift 2:

Skriv funktioner för linjärsökning och binärsökning (kodexempel finns i föreläsningen). Testa att funktionerna fungerar!

Lägg in funktionerna i programmet från uppgift 1. Jämför linjärsökning och binärsökning på två sätt:

Genom att mäta körtiden för ett funktionsanrop
Genom att räkna antal jämförelser som funktionen gör

Prova programmet med listor av olika längd.

Uppgift 3:

Blanda om dina ord med random.shuffle(listan).

Skriv funktioner för två olika sorteringsalgoritmer (kodexempel finns i föreläsningen) och testa att dom fungerar.

Jämför funktionerna på samma sätt som i förra uppgiften (tidsåtgång och antal jämförelser).
Låt programmet skriva ut en tabell över tidsåtgång/jämförelser för listor av olika längd.
Tips: Dubblera listan med listan = listan*2
Ta också tid på Pythons inbyggda listsorteringsmetod: lista.sort()!

Instuderingsfrågor

Hur många nästlade slingor fick du ihop i Uppgift 1? Hur många ord blev det?
Vad är komplexiteten för de nästlade for-slingorna?
Uppskatta hur lång tid körningen skulle ta om du la till ytterligare en nästlad slinga!
Hur snabb är binärsökning? Ange som funktion av n och berätta vad n är.
Varför fungerar binärsökning bara i en sorterad lista?
Hur många jämförelser behöver du göra (som mest) för att hitta ett ord i SAOL med binärsökning?
Visa hur mergesort fungerar för de sex först bokstäverna i ditt namn.
Skulle du använda quicksort eller bubbelsortering i ett program som ska sortera tio värden?
Hur stora listor är det rimligt att sortera med den snabbaste av dina sorteringsfunktioner?
Vilken typ av sortering använder Pythons inbyggda listsorteringsmetod?