Göm menyn

TDDI16 Datastrukturer och algoritmer

Ht1 2020

Laborationer

Laborationerna genomförs på distans under HT2020. Laborationerna genomförs i vanlig ordning i par. Samtliga kursdeltagare förväntas bidra till lösandet av laborationsuppgifterna. Alla ska individuellt kunna förklara lösningen på laborationen och vara beredda att individuellt besvara frågor från laborationsassistenterna under redovisning.

I samband med första lektionen (dagen efter första föreläsningen) kommer ni bli inbjudna till ett Team i Microsoft Teams (finns länkat via Lisam, tryck på de nio punkterna i övre vänstra hörnet). I och med detta är det viktigt att ni redan i samband med första föreläsningen (31 augusti) anmäler er i Webreg, så att vi kan bjuda in er.

En guide för Microsoft Teams finns här.

  • I varje Team finns en privat kanal för varje labbgrupp. Här kan ni kommunicera med varandra inom gruppen, antingen via text eller med videosamtal där ni kan dela skärmen med varandra.
  • Det finns också en kanal som heter "!Handuppräckning". Denna används för att få hjälp under labbpassen. Om ni behöver hjälp skriver ni ett meddelande där. I meddelandet ska ni ha med namnet på er privata kanal, en kort beskrivning av vad ni vill ha hjälp med, samt att ni "taggar" er assistent. Assistenten kommer sedan att hjälpa er när det är er tur. Exempelvis:

    • @Axel Frosthagen A01: Problem med borttagning i AVL-trädet
    • @Bror Wijgård B03: Redovisa AVL-träd

    För att använda assistentens tid så effektivt som möjligt är det viktigt att ni har skärmdelning och mikrofoner igång i er privata kanal, så att allt är klart när assistenten kommer.

    Tänk också på att inte svara på det meddelande ni publicerade i kanalen, eftersom det då flyttar sig i kön och att det finns risk att assistenten missar ert meddelande då.

    Meddelanden som skrivs i "!Handuppräckning" utanför labbtid kommer inte att behandlas. För en labb som är schemalagd klockan 08:15-10:00 kan man börja lägga meddelanden i "!Handuppräckning" från klockan 08:00. Frågor utanför labbtid skickas via e-post som vanligt, och besvaras i mån av tid.

  • Det finns också en kanal som heter "General". Där kommer assistenten göra utskick till hela gruppen, samt hålla eventuella gemensamma genomgångar. Försök vara uppmärksam ifall något händer där, så att ni kan ta del av gemensamma genomgångar. Även lektionerna kommer att hållas i "General"-kanalen.

Hur gör jag laborationerna?

Det finns ett antal alternativ för hur du kan göra laborationerna i år. De beskrivs nedan ordnat efter hur bra de är:

  1. På ditt Linux-system

    Kör du redan Linux på din dator (eller vill installera och test) kan du göra laborationerna där. Du behöver se till att ha en C++-kompilator installerad (GCC version 7 eller senare). På Ubuntu eller Debian kan du köra sudo apt install g++ make för att få det mesta som behövs. För lab 4 krävs även ett SFML, som enkelt installeras med sudo apt install libsfml-dev.

    Även MacOS bör fungera utan problem, dock har jag inte möjlighet att testa laborationerna där. Se till att du har kommandot g++ i terminalen (har jag förstått det hela rätt så räcker det att installera XCode, men jag kan ha fel). Laboration 1-3 ska fungera som under Linux, men laboration 4 kan behöva andra kompileringsflaggor i och med att SFML används.

  2. På ditt Windows-system

    I år är laborationerna även testade på Windows. I och med att andra byggsystem och kompilatorer är vanliga på Windows behövs en separat version av den givna koden med lite andra filer. Dessa finns tillgängliga här, tillsammans med detaljerade installationsinstruktioner.

    Instruktioner

  3. I en virtuell maskin

    Om du inte kan eller vill köra laborationerna på ditt ordinarie system kan du installera ett Linux-system för laborationerna i en virtuell maskin och laborera därifrån. Att köra i en virtuell maskin kan innebära att programmen kör något långsammare jämfört med om man kör dem utanför den virtuella maskinen, vilket kan påverka tidsmätningarna i laboration 2-4 något. Detta ska i de allra flesta fall inte göra att en "bra" lösning kräve längre tid än vad som anges i laborationerna.

    För installationsinstruktioner, se följande alternativ från TDIU16. Efter att ha följt de instruktionerna behöver du installera en C++-kompilator och SFML med kommandot: sudo apt install g++ libsfml-dev

  4. Via ThinLinc

    Kan du inte köra direkt på din dator hemma, eller i en virtuell maskin kan du även använda ThinLinc för att få tillgång till en miljö lik den som finns i SU-salarna. Ladda ner ThinLinc-klienten från Cendios hemsida. Öppna sedan ThinLinc-klienten och anslut till thinlinc.edu.liu.se och ange användarnamn (LiU-ID) och lösenord.

Laborationsuppgifter

  1. AVL-träd (AVL) - Deadline 2020-09-15

    Instruktioner - Givna filer

  2. Knäcka lösenord (Passwords) - Deadline 2020-09-24

    Instruktioner - Givna filer

  3. Ordkedjor (Wordchains) - Deadline 2020-10-09

    Instruktioner - Givna filer

  4. Mönsterigenkänning (Patterns) - Deadline 2020-10-12

    Instruktioner - Givna filer

Hjälp att skriva testfall (experimentellt, inte obligatoriskt)

Tidsmätning och tidsgränser

I laborationerna är vi ute efter att ni kommer fram till lösningar som involverar bra algoritmer med en bra tidskomplexitet. En stor anledning att använda bra algoritmer är just för att de är snabba, och därför nämner instruktionerna för de tre sista laborationerna tidsgränser för att ge en fingervisning om hur bra algoritm ni bör komma fram till. Däremot är det, som ni säkert kommer att märka, mycket svårt att bara titta på körtider för att bedöma om en algoritm är bra eller inte. Tiden det tar att köra algoritmen beror såklart på hur snabb dator man har, men också på hur mycket arbete man gör i olika steg (exempelvis om man råkar göra en extra kopia av en sträng i en loop eller inte). I och med detta är gränserna i labbhandledningarna att se som just fingervisningar. I de flesta fall är det enkelt att komma långt under de tiderna som anges där eftersom de är tilltagna för olika typer av hårdvara och för att inte helt utesluta att man gör lite extra arbete utan att påverka tidskomplexiteten. Det innebär att det i vissa fall går att implementera sämre lösningar som kommer under tidsgränserna i och med att de är implementerade på ett "smart" sätt. Dessa lösningar är dock inte godkända i och med att det är bra algoritmer vi är ute efter.

Alltså: fundera på vilken tidskomplexitet er lösning borde ha, och om det går att göra något för att förbättra tidskomplexiteten eller inte. Tror ni er ha en optimal lösning för problemet så kommer er lösning antagligen bli godkänd.

För att enkelt mäta hur lång tid det tar att köra program i Linux kan man helt enkelt skriva time framför. Då skrivs tre rader ut efter programkörningen: real, user och sys. Raden real anger hur lång tid körningen tog totalt. Exempelvis: time g++ minkod.cpp för att se hur lång tid det tog att kompilera programmet. Vissa labbar har tidsmätning inbyggd i den givna koden, andra inte.

Redovisning

Redovisning av labbar sker i två steg:

  1. Demonstration av labben för assistent i sal.
  2. Inlämning av kod till assistent enligt nedan.

Deadlines och bonus

Alla laborationspass är markerade med en kommentar som anger vilken laboration ni förväntas arbeta med under passet, samt om det är deadline för någon laboration. Varje mött deadline under kursen ger 0.5 bonuspoäng på tentamen. Dessa bonuspoäng gäller endast vid första tentamenstillfället, och endast mot högre betyg.

Den deadline som anges för varje laboration är den bonusgivande deadlinen. Det är okej att redovisa laborationer både innan och efter denna deadline. Redovisa gärna era lösningar så tidigt ni kan, då slipper ni eventuell köbildning på deadlinepassen, samt får mer tid till nästa laboration!

En deadline räknas som mött om du har redovisat och skickat in laborationen innan deadline. Får du komplettering på laborationen efter första inskickningen har du en chans att komplettera laborationen inom fem arbetsdagar för att deadlinen fortfarande ska räknas som mött. Tar kompletteringen längre tid än fem arbetsdagar, eller behövs fler än en komplettering räknas deadlinen som missad.

Hård deadline för redovisning av laborationer är vid sista passet (2020-10-13). Då ska alla laborationer vara redovisade för assistent.

Eventuella kompletteringar ska vara korrigerade så att alla laborationer är godkända senast 2020-10-31. Se därför till att skicka in eventuella kompletteringar i god tid!

Extrapass

Om du inte har hunnit redovisa lab 3 och 4, men är klar fram till och med lab 2 så finns det möjlighet att redovisa lab 4 (och om tid finns, även lab 3) på tisdag den 20:e oktober klockan 13:15 i Teams. Vi kommer att vara kvar så länge det finns grupper som vill redovisa laborationer, dock maximalt till 15:00. Vill du redovisa något, se därför till att vara på plats klockan 13:15 och lägga ett inlägg i handuppräckningskanalen.

Inskickning av laborationer

I denna kurs används ett system för labinlämning som vi kallar sendlab. Använd länken i vänstermenyn för att komma åt systemet.

Regler för datorlaborationer

Regler för examinering av datorlaborationer vid IDA

Datorlaborationer görs i grupp eller individuellt, enligt de instruktioner som ges för en kurs. Examinationen är dock alltid individuell.

Det är inte tillåtet att lämna in lösningar som har kopierats från andra studenter, eller från annat håll, även om modifieringar har gjorts. Om otillåten kopiering eller annan form av fusk misstänks, är läraren skyldig att göra en anmälan till universitetets disciplinnämnd.

Du ska kunna redogöra för detaljer i koden för ett program. Det kan också tänkas att du får förklara varför du har valt en viss lösning. Detta gäller alla i en grupp.

Om du förutser att du inte hinner redovisa i tid, ska du kontakta din lärare. Då kan du få stöd och hjälp och eventuellt kan tidpunkten för redovisningen senareläggas. Det är alltid bättre att diskutera problem än att, t.ex., fuska.

Om du inte följer universitetets och en kurs' examinationsregler, utan försöker fuska, t.ex. plagiera eller använda otillåtna hjälpmedel, kan detta resultera i en anmälan till universitetets disciplinnämnd. Konsekvenserna av ett beslut om fusk kan bli varning eller avstängning från studierna.

Policy för redovisning av datorlaborationer vid IDA

För alla IDA-kurser som har datorlaborationer gäller generellt att det finns en bestämd sista tidpunkt, deadline, för inlämning av laborationer. Denna deadline kan vara under kursens gång eller vid dess slut. Om redovisning inte sker i tid måste, den eventuellt nya, laborationsserien göras om nästa gång kursen ges.

Om en kurs avviker från denna policy, ska information om detta ges på kursens webbsidor.


Sidansvarig: Filip Strömbäck
Senast uppdaterad: 2020-10-14