Till KTH:s startsida Till KTH:s startsida

Laboration_A

Laboration för betyg A

För betyg A ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.

Din uppgift är att lösa ett av följande problem:

Resurser

Redovisning

Labben får göras enskilt eller i grupper om två och redovisas muntligt av bägge gruppmedlemmarna var för sig (boka in varsin redovisningstid). Ett dokument med algoritmbeskrivning, program, testdata och tidskomplexitet lämnas in på kurswebbsidan (se Inlämningsuppgifter i vänstermenyn). Skriv bägge gruppmedlemmarnas namn i dokumentet.

Vid redovisningen ska du

  • visa upp en tydlig och korrekt algoritmbeskrivning för ditt problem,
  • visa upp tre nya uppsättningar testdata,
  • redogöra för hur ditt program fungerar,
  • visa att du fått godkänt i Kattis,
  • visa vilken tidskomplexitet din algoritm har.

Denna uppgift kan bara redovisas fram till och med 18 januari 2016, och kan inte kompletteras eller plussas.

Teacher Linda Kann created page 10 December 2015

commented 15 December 2015

Hej, 

Gällande problem CD, hur mycket data är det tänkt att programmet ska kunna hantera på mindre än 3 sekunder? Som jag har uppfattat det kan inputen vara oändlig eftersom att det inte finns någon begränsing på antal sekvenser i filen. När jag själv testar med stora textfiler med flera sekvenser får jag godkända resultat, men jag misslyckas med 2:a testfallet i Kattis.

Kattis-ID: 994951 

Teacher commented 15 December 2015

Hej,

Precis som du räknat ut så testar Kattis med en riktigt lång sekvens! Vad kan du snabba upp i ditt program?

commented 16 December 2015

Tack!

När kan en boka redovisning för labb A?

commented 28 December 2015

Hej Linda,

Jag gör också CD problemet och har fastnat på testfall 2 pga fel svar. Jag har testat flera egna testfall men förstår inte varför kattis säger fel. Time limit kan jag förstå men inte fel svar.

Kattis-ID: 1003367

Teacher commented 28 December 2015

Har du testat med en infil som har flera uppsättningar indata?

commented 29 December 2015

Hej igen! Tack för tipset, nu har jag kommit vidare men mitt program är för långsamt. Jag har testat flera olika varianter för att tidsoptimera men nu vet jag inte hur jag kan snabba upp mitt program mer. Är det regex som är tidskrävande? Jag har även testat att ta bort pop(0) men det gjorde ingen skillnad.

Kattis-ID: 1003878

commented 29 December 2015

Hej Linda, 

Jag har skrivit om min (förbättrade) algoritm i java med hjälp från Marko och får tiden 0.81 men mitt pythonprogram får fortfarande i Time limit. Kan det vara så att tiden är lite väl knapp i python? Det är endast två som har klarat sig.

Teacher commented 30 December 2015

Hej Sara,

Det är en A-uppgift, så det ska inte vara helt lätt! Du kan använda time.time() för att kolla vilka delar av ditt program som tar lång tid.

Du har rätt i att det går snabbare i Java. Men du har faktiskt skrivit en annan algoritm i ditt Java-program.

Det är inte så många från tilda-kursen som har försökt sig på denna uppgift än, så det är inte konstigt att det bara är två som klarat den.