TDDI16 Datastrukturer och algoritmer

Ht1 2021

Laborationer

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, och vara beredda att individuellt besvara frågor från assistenterna under redovisning.

Från och med måndag den 4:e oktober kommer laborationerna återgå till ett mer normalt läge. Från och med då får vi nyttja salarna till full kapacitet. Ni kan då sitta parvis vid samma dator, och skärmarna behöver inte längre vara på plats. I och med detta tar vi bort de båda delgrupperna i schemat - alla som vill vara på plats kan då vara på plats. Notera dock att det fortfarande gäller att du inte ska vara på plats om du är sjuk.

Vid pass på distans använder vi teams som beskrivet här: teams-användning. Grundidén ä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. Under labpass på distans förväntar vi oss att ni arbetar i denna kanal, så att vi snabbt hittar er när ni vill ha hjälp.

• Det finns också en kanal som heter "!Handuppräckning". Denna används för att få hjälp under labbpassen. Labassistenten kommer vid labpassets start lägga ett meddelande där. Svara på det om ni behöver hjälp. Inkludera namn på er kanal, samt en kort beskrivning av vad ni vill ha hjälp med. Assistenten kommer sedan att hjälpa er när det är er tur. Assistenten markerar avklarade meddelanden med en symbol så att ni kan se ungefär hur långt det är kvar till er tur. Exempelvis:

  • A01: Problem med borttagning i AVL-trädet
  • 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.

  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.

Om du har anmält dig i en grupp som är på plats räknar vi med att du är i en labbsal. Vi har därmed ingen personal i de Teams som finns för grupperna som ska vara på plats. Är det så att du är sjuk ska du dock hålla dig hemma, och missar därmed passed (likt vanliga år). I och med att det i år är extra viktigt att stanna hemma vid symptom tillåter vi att de som stannar hemma på grund av sjukdom ställer frågor i Teams. Detta behandlas dock i mån av tid, och vi kan inte garantera att vi hinner hjälpa de som inte kan vara på plats när de ska vara på plats.

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

   • Installera en virtuell maskin
   • Installera en virtuell maskin från färdig avbild
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 2021-09-15

   Instruktioner - Givna filer

2. Knäcka lösenord (Passwords) - Deadline 2021-09-23

   Instruktioner - Givna filer

3. Ordkedjor (Wordchains) - Deadline 2021-10-08

   Instruktioner - Givna filer

4. Mönsterigenkänning (Patterns) - Deadline 2021-10-14

   Instruktioner - Givna filer

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

Extra redovisningspass: Fredag 2021-10-22 klockan 13:15. Här kan ni redovisa lab 3 och lab 4. Passet sker på distans via Teams. Kom i tid om ni vill redovisa, vi kommer bara vara kvar så länge vi har redovisningar att ta.

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 (2021-10-14). Då ska alla laborationer vara redovisade för assistent.

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

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, använda otillåtna hjälpmedel eller ej godkända AI-baserade assistenter) 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: 2021-10-07