Labb 1
- Inlämningsdatum 12 Sep 2025 av 17:00
- Poäng 1
Beständig array
Om ni redovisar labben senast den 12 september får ni en labbleveranspoäng var, som kan ge högre betyg på labbmomentet. Till labben hör teoriuppgifter som kan redovisas för en teoripoäng till tentan, och detta görs på övningen den 2 september (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör ni ha gjort dom.
|
Målen för labb 1 är att ni ska
|
En beständig datastruktur (persistent data structure) är en datastruktur som inte skriver över sig själv (muteras) när man gör en förändring i den. Det betyder att man alltid kan gå tillbaka till en tidigare version av datastrukturen. Se vidare föreläsning 3.
En array är en indexerad datastruktur där det går snabbt att slå upp och ändra vilket element som helst. Se vidare föreläsning 2. I denna uppgift har arrayen dynamisk storlek och kan vara gles, dvs inte alla möjliga element har tilldelats något värde.
Uppgift
Implementera (i valfritt programspråk som Kattis kan hantera) en beständig datastruktur för en dynamisk array (indexerad med naturliga tal) med heltal som har följande operationer:
| newarray() | Returnera en ny array. |
| set(a, i, value) | Sätt a[i] till value och returnera den nya versionen av arrayen. i är ett ickenegativt heltal och value är ett heltal. Såväl i som value är 32-bitstal, dvs högst 231 − 1. |
| get(a, i) | Returnera värdet a[i]. Om a[i] inte har tilldelats ett värde tidigare returneras 0. |
En beskrivning av hur datastrukturen ska byggas finns på https://conjoin-it.se/#clojure/persistent-data-structures
Skriv sedan ett styrprogram som skapar en beständig array och sedan utför ovanstående operationer på den utifrån följande kommandon som läses från standard input:
| get i | Skriv ut värdet på index i på standard output på en egen rad. Om inget värde tilldelats ska 0 skrivas ut. Det ska vara ett mellanslag mellan get och indexet. |
| set i value | Sätt värdet på index i till value. Det ska vara ett mellanslag mellan set och i och mellan i och value. |
| unset | Backa tillbaka till läget en set-operation tidigare. Om ingen set-operation gjorts händer inget. |
Exempel
| Inmatningen: | ska ge utskriften: |
| set 3 17 set 3 4711 get 3 set 3 1000 unset get 3 unset get 3 |
4711 4711 17 |
Parprogrammering
För att få labbleveranspoäng på denna labb måste ni (förutom att redovisa den senast ovanstående datum) genomföra den i tvåpersonsgrupper som arbetar enligt den agila programutvecklingstekniken parprogrammering. Läs här om parprogrammering.
Testning
Ni ska skriva ett par egna testfall för att testa ett program. När programmet passerar alla era egna testfall ska ni skicka det till Kattis för automatisk testning av funktionalitet, tidskomplexitet och minneskomplexitet.
Gå in i Kattis och registrera er på kursen adk25 i Kattis. Lägg in er labbgrupp i adk25, för då kommer ni inte råka ut att Kattis varnar för plagiat om båda två skickar in liknande lösningar. Från och med 5 september planeras problemet Beständig array att vara tillgängligt i Kattis. Läs gärna Kattis instruktioner för hur man skickar in sin lösning och Kattis hjälptexter.
Kattisproblemet Beständig array har tre publika testfall som också finns tillgängliga på /afs/kth.se/misc/info/kurser/DD2350/adk25/labb1/
Vid labbpassen och redovisningen
Labbpassen genomförs både i sal (se schemat) och på distans med hjälp av Zoom. Varje labbgrupp som vill delta i labbpasset i Zoom skapar ett eget Zoomrum att arbeta i under labbpasset. I kursen används (för både sal och Zoom) kön ADK i kösystemet Stay a while på queue.csc.kth.se för att hålla reda på hjälp- och redovisningskön vid hjälplabbpassen (tvåtimmarspassen, som huvudsakligen är till för hjälp men där redovisningar också tas emot). Skriv i rutan Location in länken till den Zoomsession som ni arbetar i (för Zoomlabb) och i kommentarsrutan vilken labb det gäller. Ange om ni vill redovisa eller få hjälp. Er labblösning ska redovisas för en labbhandledare vid något av kursens schemalagda labbpass.
Vid redovisningslabbpassen (fyratimmarspassen, som huvudsakligen är till för redovisningar men då hjälp också ges) bokas redovisningstider med systemet Remores, men Stay-a-while-kön används för den som vill ha hjälp, tala om att man är klar med en komplettering eller berätta var man sitter/vilket Zoomrum man är i om det inte framgår av bokningslistan.
Länk till bokningslistor för labbredovisning 12 september publiceras här ett dygn före passets start.
Det finns tillräckligt med tider för alla som vill redovisa. Läs instruktionerna noga innan ni bokar er redovisningstid. Avboka den bokade tiden om ni inte är redo för redovisning.
Boka inte in er för redovisning för en assistent som ni känner väl, då blir det jäv.
Den som vill ha hjälp använder Stay A While på samma sätt som vid hjälppassen.
Innan ni redovisar, gå igenom punktlistan med kraven på lösningen ovan och kontrollera att ert program uppfyller alla krav. Förbered själva redovisningen och ha program, testfall och skisser redo. Ni kommer då att få redovisa följande (med delad skärm om det är en Zoomredovisning):
- Reflektera över er erfarenhet från parprogrammeringen vid denna labb (krävs endast för labbleveranspoäng).
- Visa en uppsättning testfall som ni har tagit fram för att kolla att programmet gör rätt. Ni ska också kunna motivera varför ni valt just dessa testfall.
- Visa att er lösning accepterats av Kattis.
- Visa och förklara hur er lösning fungerar.
- Visa programkoden och vara beredd att svara på frågor om den.
Båda studenterna i labbgruppen ska kunna redogöra för hela programmen (vilket blir en naturlig följd av att ni parprogrammerat).
Hitta matris
