News feed

Innehåll visas utifrån dina val

Om du inte hittar någon sida, schemahändelse eller nyhet på din kurswebb kan det bero på att du inte ser den kursomgången/gruppen inom kursen som innehållet tillhör.

Veta mer om din kurswebb

Din kurswebb är sidorna för en kurs du prenumererar på. Du väljer sedan vilka omgångar/grupper inom kursen du vill ha information från. Är du registrerad på en kursomgång sköts prenumeration och val av kursomgäng automatiskt åt dig. Vill du ändra något av detta gör du det under Mina inställningar.

När du är inloggad på din kurswebb ser du:
  • Kursöversikt, nyheter och schema med information som är filtrerat utifrån dina valda omgångar/grupper inom kursen
  • Allmänna sidor för hela kursen
  • Kurswikin som är sidor som alla, lärare och studenter, kan skapa och redigera
  • Sidor som hör till de omgångar/grupper inom kursen du valt eller som valts för dig

You are not logged in KTH, so we cannot customize the content.

In the News feed, you find updates for pages, schedule and posts from teachers (when aimed also at earlier registered students).

May 2014
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 16 May 2014

Bra länkar! :)

Jag hittade denna, kanske är värd att få en plats här:

http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Riktigt bra och pedagogisk grafisk representation om algoritmer! :)

 
February 2014
under HT 2013 adk13

Teacher Viggo Kann created page 18 February 2014

Teacher Viggo Kann changed the permissions 11 April 2014

Kan därmed läsas av alla och ändras av lärare.
 
January 2014
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
Erik Lindén removed his/her comment
Carl Thomé removed his/her comment
commented 9 November 2013

Kan det tillhöra en ja-instans om varken divorna p1 eller p2 får minst en roll i någon scen men båda var med vid castingen för minst en roll i samma produktion?

Viggo Kann removed his/her comment
Teacher commented 9 November 2013

Ja-instanser är instanser som har svaret ja på frågan: Kan rollerna besättas med högst k st skådespelare så att p1 och p2 deltar men inte är med i samma scener som varandra? Divorna måsta alltså spela med i filmen.

commented 10 November 2013

Är det giltigt med indata som har roller som aldrig är med i någon scen?

commented 11 November 2013

Får man i teroiuppgift 3 ändra indata så att divorna byter plats? Tex att r4 kan innehas av diva 1 istället för diva 2?

Teacher commented 11 November 2013

I teoriuppgift 3 kan du tänka att du är castingansvarig på riktigt. Då kan du inte peka ut vilka skådisar som ska vara divor, utan du får acceptera dom skådisar (och scener) som finns. Försök alltså att göra om instansen till en ja-instans genom att anlita nya skådisar, för det är något som är rimligt att göra i verkligheten.

commented 11 November 2013

På teorifråga 5, gäller reglerna kring divorna även i denna fråga eller ska man inte räkna med divorna alls? 

Assistant commented 12 November 2013

Även på teorifråga 5 är det rollbesättningsproblemet som vi utgår ifrån. Det är bara "tilläggsvillkor" som presenteras i frågan.

commented 12 November 2013

I uppgift 3:

Får man ta bort scener för att lösa castingproblemet?

Assistant commented 12 November 2013

Se Viggos inlägg igår - tänk dig att någon annan har skrivit filmerna, och berättat vilka (sorters) skådisar som passar för de olika rollerna. 

Johan Arnör removed his/her comment
David Ekermann removed his/her comment
commented 18 November 2013

Jag är lite förvirrad då jag inte riktigt vet vad ni vill att jag ska göra!

Jag började för några dagar sedan att skriva ett program som översätter casting problemet till ett problem som löses med graffärgning.. I mina ögon så var detta uppgiften! Nu idag fick jag reda på att man ska reducera problemet graffärgning till casting och inte vise versa, av en kompis.. Och hans argument lät rimligt, det står: "reducera ett känt NP-fullständigt problem"

Varför är alla exempel som är bifogade i casting-format och inte hamilton/graffärgning om vi nu inte ska reducera dessa? 

Mvh förvirrad student

Assistant commented 18 November 2013

Labb 4 berättar om ett problem (inklusive indataformat) som vi vill veta något om. Det är oftast det man har när man vill visa att ett problem är NP-fullständigt: en formulering av problemet, mer eller mindre välspecificerad. Det är för att det är det nya problemet som vi behöver veta saker om och ge exempel på. De "kända NP-fullständiga problemen" känner vi redan till.

Att läsa lydelsen noga är bra, men tänk också på att vi gör på samma sätt när vi visar att ett problem är NP-fullständigt i labben som vi gör på föreläsningar, övningar och mästarprov! Det är att välja problem att reducera, att utföra reduktionen och att argumentera för att den är effektiv och korrekt som de olika kursaktiviteterna är tänkta att träna.

Hoppas att detta hjälper mot förvirringen!

commented 18 November 2013

Hej Emma!
Tyvärr så blev jag inte klokare av vad du skrev!

Kanske går det att svara på.. i mappen labb4 så har vi exempel på indata, men till vad?

commented 18 November 2013

Testfallen i mappen är till extrauppgiften då man ska lösa rollbesättningsproblemet och har inget med labb 4 att göra.

Labb 4: Visa att rollbesättningsproblemet är NP-svårt.
Extrauppgift: Lös rollbesättningsproblemet approximativt.

commented 18 November 2013

Det som ligger i mappen labb4 tillhör extrauppgiften som kan redovisas den 10 januari, och alltså inget som skall användas nu.

commented 20 November 2013

Hur kan n och s tillåtas vara 1 så att man får en scen med en roll och ändå hävda att man förbjuder monologer? Jag kanske missförstår? :)

commented 29 November 2013

Hej. Jag får "Otillåtet skådisnummer i lösningen". Hur kommer det sig, man fick ju lägga till hur många superskådisar man ville?

Assistant commented 29 November 2013

Emil: "Hur många superskådisar man vill" ska tydligen tolkas som att det får finnas max k+n st skådespelare totalt, och det högsta tillåtna skådespelarnumret var k+n-1, att döma av hur felmeddelandet uppstår. :)

Det vore klart bättre om den restriktionen inte såg ut just så, helt odokumenterat, tack för buggrapporten!  

Teacher commented 29 November 2013

Jag har nu lagt till information i labblydelsen om begränsningen av antalet superskådisar.

commented 29 November 2013

Hmm. Men om det får finnas högst n + k skådespelare och de numeras från 1 och uppåt blir väl den sistas nummer n + k, och inte n + k - 1 väl?

Assistant commented 30 November 2013

Emil: My bad, jag tittade inte jättenoga igår, och tolkade villkoret att skådespelarnumret skulle vara mindre än n+k som om någon tänkt sig max n+k skådespelare. Då tänkte jag förstås nollindexerat. Viggo läste noggrannare och hans uppdatering av problemlydelsen ovan tar hänsyn till 1-indexeringen. Eftersom divorna ändå måste vara med är det ju inga problem med att ha den gränsen, bara man berättar om den...

Elias: Jag tror att det enda som faktiskt kommer att tolkas som monologer just nu är scener som skrivs ut och som bara innehåller en skådespelare, åtminstone i grundversionen av labben. Att instanser får ha endast en scen kommer i en striktare tolkning "monologer" bara att betyda att det är en nej-instans. Nästa år när labben anpassas till Kattis nya problemformat kan vi även passa på att göra monologdefinitionen lite mera intuitiv, dvs explicit kräva att alla roller är med i någon scen.

commented 30 November 2013

Finns det några speciella krav för koden/algoritmen för extrauppgiften när man ska redovisa, förutom att programmet blir accepterat på Kattis och kommer under så många poäng man behöver (460 för A eller 560 för B)?

Teacher commented 1 December 2013

Emil: Koden ska lösa problemet i uppgiftslydelsen och den ska passera Kattis. Det är allt. Sedan måste man som vanligt kunna svara på frågor om sin kod vid redovisningen.

commented 1 December 2013

En sak jag funderat på:

Divorna "är garanterade vid varje castingtillfälle", betyder det att de är garanterade minst en roll, eller betyder det att de är garanterade minst en roll som faktiskt medverkar i någon scen. Det vill säga är det tillåtet att divan spelar bara en enda roll, fast rollen medverkar aldrig i någon scen?

Eller kan man anta att man inte får ha indata med roller som aldrig medverkar i någon scen?

commented 9 December 2013

Kan man få godkänt på uppgiften ifall man har en ickedeterministisk heuristik?

Teacher commented 9 December 2013

Ja. Heuristiker som använder slump är ofta bra, och speciellt bra är att man kan köra flera varv och få olika lösningar och plocka den bästa.

commented 14 December 2013

Någon som vet vad som "Otillåtet skådisnummer i lösningen" innebär? Är det endast att man har för många superskådisar? För även som jag inte skriver ut något superskådis överhuvudtaget så får jag samma felmeddelande på första testfallet i Kattis.

commented 14 December 2013

Det är löst nu iaf. Antar att otillåtet skådisnummer innebär < 1 samt >= n+k.

Jonas Stendahl removed his/her comment
Jonas Stendahl removed his/her comment
Jonas Stendahl removed his/her comment
commented 16 December 2013

Jag har felsökt detta felmeddelande i 6 timmar idag och vill försäkra mig om att jag har förstått det rätt.

"Fel i lösningen: en skådis har tilldelats ett otillåtet rollnummer"


Tillåtna rollnummer är [1 - antalet roller i indata].
Kan detta meddelande även antyda att samma skådespelare spelar i två skilda roller i samma scen? Eller är detta ett annat felmeddelande?

Ytterliggare en fråga är hur man ska hantera roller som inte är med i någon scen? Ska dessa fortfarande tilldelas till en skådis?

commented 16 December 2013

"Endast lösbara instanser kommer att ges som indata, men för att heuristiken i polynomisk tid säkert ska kunna hitta en lösning så är det tillåtet att använda högst n-1 särskilda superskådisar med nummer k+1k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll."

Det högsta tillåtna skådespelarnumret är alltså k+n-1. Det minsta skådespelarnumret är 1.

"Kan detta meddelande även antyda att samma skådespelare spelar i två skilda roller i samma scen? Eller är detta ett annat felmeddelande?"

Jag tror det är ett annat felmeddelande.

I fallet hur man ska göra med en roll som inte ingår i någon scen verkar det som att denna ändå måste tillsättas en skådespelare. Emma får gärna bekräfta det. Jag antar att detta även gäller för divorna, dvs. att det räcker att de får en roll, oavsett om rollen faktiskt spelar i någon scen eller inte?

commented 17 December 2013

Kommentarerna här antyder att man ska få olika typer av felmeddelanden beroende på vilka "regler" ens lösning bryter mot. Jag har en lösning som jag testat med flera testfall lokalt och allt går fint... men när jag skickar in den till kattis får jag felmeddelandet "wrong answer" på problem 2 av 8. Jag funderar på om man utifrån detta våga göra tolkningen att det är ett fel i utskriftformat som triggas på andra problemet snararare än att det är någon regel som bryts?

commented 17 December 2013

Står det inget mer under "Error information"?

commented 17 December 2013

Detta är allt jag får

This is a mail from your friendly local Problemset Judge. I'm
saddened to inform you that your submission (ID: 476088) on problem
"oldkattis:adkcasting" was not accepted. It ran for 0.235000 seconds.
On test file 2/8 it failed:
Wrong Answer
I will now go and sulk in a corner for the next 5 minutes while
you fix this problem and resubmit.

Yours truly,

commented 17 December 2013

Ok, men om du går in under dina submissions och trycker på ID-numret så borde du får lite mer info. 

commented 17 December 2013

Jag hade på labb 3 där Kattis klagar på att jag hade extra mellanslag i utskriften och testet inte gick igenom..

Jonas Stendahl removed his/her comment
commented 17 December 2013

Angående min fråga ovan så undrade jag vad tillåtna rollnummer är, inte tillåtna skådespelarnummer?

commented 17 December 2013

Tillåtna rollnummer är ju från 1 till n, i samma ordning som listan över roller i indata där det specificeras vilka skådespelare som klarar den rollen.

Assistant commented 18 December 2013

För att förhoppningsvis göra det lite enklare att lista ut om ett felmeddelande innefattar händelse X eller om det är ett annat felmeddelande, här kommer en lista på alla felmeddelanden som domarprogrammet verkar kunna spotta ur sig:

  • Fel i lösningens första rad
  • Otillåtet skådisnummer i lösningen 
  • Fel i lösningen: samma skådis nämns flera gånger
  • Otillåtet antal roller i en skådisrad i lösningen
  • Fel i lösningen: en reservskådis har fått mer än en roll
  • Fel i lösningen: en skådis har tilldelats ett otillåtet rollnummer
  • Fel i lösningen: en skådis har tilldelats en otillåten roll
  • Fel i lösningen: för många roller angivna för en skådis
  • För mycket data i lösningen
  • Alla roller är inte besatta
  • Skådespelare 1 som är diva är inte med i lösningen
  • Skådespelare 2 som är diva är inte med i lösningen
  • Samma skådespelare har flera roller i samma scen
  • Båda divorna är med i samma scen
  • Trailing output (standardfelmeddelande om utdatat inte är slut när allt data som utlovats på rad 1 är läst)

Det stämmer alltså att alla roller måste besättas, och att det är olika felmeddelanden för ett otillåtet rollnummer (utanför den range som indata specificerat) och otillåten roll (en som inte hade skådespelaren på sin lista över tillåtna roller) och ytterligare ett annat felmeddelande för att en skådis har flera roller i samma scen. 

Ni ska inte behöva göra något aktivt för att undvika monologer - om det förekommer roller som inte medverkar i någon scen så är det tillåtet med sådana roller, för alla skådisar.

commented 20 December 2013

(Tävlingsprogrammerings)uppgifter på Kattis tenderar att specificera gränser för storlek på indata, exempelvis "1 ≤ K ≤ 1000". Finns det några sådana övre gränser på storleksparametrarna n, s, k till castingproblemet, eller måste man stödja "obegränsat" stora tal ("får plats i en 32-bitars int") för dessa?

commented 20 December 2013

De verkar vara i storleksordningen ca 100.

commented 7 January 2014

Kan samma skådespelare stå flera gånger på en rad som representerar en roll i indata?

commented 7 January 2014

Är det något speciellt med testfall nr 6? Jag klarar alla testfall fram tills 6:an då jag får time limit exceeded. Även om jag inte kör flera gånger utan bara kör en enda gång och tar den lösningen så får den time limit exceeded och jag förstår inte varför.

Teacher commented 7 January 2014

Victor: Testfall 6 är stort. Det har omkring 1000 scener.

Tonima: Samma skådespelare borde inte förekomma flera gånger på samma rad. Men jag har inte tillgång till alla testdata så jag kan inte lova att det är så.

commented 7 January 2014

Okej, Är det fortfarande godkänt om man passar Kattis nån gång?

Jag kör exakt samma kod och får ibland Time Limit Exceeded från Kattis

commented 8 January 2014

Ja den beter sig ytterst märkligt för mig med, jag gör små ändringar som bör förbättra tidskomplexiteten, men istället anser kattis att den blir mycket sämre, beror det då på att min herustik baseras på slump och just denna körning tog det lång tid att slumpa fram en lösning, eller beror det på att det faktiskt tar längre tid?

Teacher commented 8 January 2014

Om algoritmen använder slump så är det inte konstigt om vissa körningar tar längre tid. Det är den bästa godkända körningen i Karttis som ska redovisas på labben på fredag.

Victor Hung removed his/her comment
commented 9 January 2014

Om man kör C++ och använder rand() så kommer den alltid generera exakt samma sekvens vid varje körning. Vad jag känner till finns det inget bra sätt att seeda den (med srand) med ett slumpvärde, då time(0) alltid returnerar 0 på Kattis istället för tiden.

Om man kör Java och använder new Random() så genererar den olika tal vid varje körning. Om man dock seedar med ett konstant värde så kommer den alltid ge samma sekvens vid varje körning.

commented 9 January 2014

Emil: Vet du om det finns något bra alternativ till rand() annat än att implementera en egen slumpfunktion för C++?

commented 10 January 2014

rand() är det enda jag känner till. Varför skulle du vilja använda någon annan slumpfunktion?

commented 10 January 2014

rand() är väl pseudo-random så om man seedar den med samma värde får man väl samma resultat varje gång i kattis om man inte kan seeda srand med time(0) ?

commented 10 January 2014

Yes, det stämmer. För att få slump som inte är pseudo-random behöver man ha tillgång till hårdvara, vilket inte går på Kattis. Men pseudo-random räcker så gott som alltid så länge det inte är kryptografi man sysslar med.

 
Teacher Viggo Kann posted 1 January 2014
 
December 2013
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 17 October 2013

I Chrome blir marginalerna väldigt konstiga på denna sida.

commented 22 October 2013

Hej

Vi har tittat på sidan i Chrome och förstår inte riktigt vad som är fel. Är det att texten efter punkt kommer längre in än texten utan? I så fall är det för att man gjort en radbrytning efter texten med punken.

/Åsa

 

Viggo Kann tagged with detaljschema. 31 October 2013

commented 29 December 2013

Hej

Hur anmäler man sig till muntan? Får man själv välja en av dagarna 15-17 jan?

commented 29 December 2013

Sidan där man anmäler sig till muntan ligger inte under någon sida under den vanliga menystrukturen utan ligger lite dolt här: https://www.kth.se/social/course/DD1352/subgroup/adk13/post/munta-och-ommastarprov-den-som-har-minst/

Kanske det vore bättre att lägga in den på sidan Examination under Muntlig tenta?

 
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 3 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 11 November 2013

"Ordinarietentan går den 20 december 2012 klockan 9.00 i sal F1." verkar vara felaktigt, 2012 har varit.

Teacher commented 12 November 2013

Nu bytt till 2013! Tack!

Karl Arvidsson removed his/her comment
commented 1 December 2013

Om man får A eller B på extralabben, stämmer det då att betyget på teoritentan (så länge det är godkänt) är helt irrelevant för slutbetyget?

Till exempel: Om man får A på båda mästarproven, E på teoritentan och A på extralabben, stämmer det då att man får A i slutbetyg utan att behöva munta?

Teacher commented 1 December 2013

Ja. För att få redovisa extralabben måste man ha godkänt på teoritentan. Det betyg (A eller B) som man får på extralabben rapporteras som betyg på TEN-momentet. På sista föreläsningen kommer jag att gå igenom betygsättningen och svarar på alla frågor om den.

commented 5 December 2013

Hej! Kan någon förklara om tentan kommer vara 20p max? Och om det är så, hur mycket är den maximala bonusen man kan få och vad är gränserna? Är bonuspoängen på summan så man max kan få 20p + bonus eller är de på enskilda uppgifter? Tack

Carl Thomé removed his/her comment
Teacher commented 5 December 2013

På teoritentan finns frågor som ger totalt 20 poäng. Till det adderas bonuspoängen från labbteori och labbredovisningar, som maximalt är 8. Kolla gärna på extentorna för att se upplägget.

Emma Enström removed his/her comment
commented 27 December 2013

Vilken typ av frågor kommer på muntan för att höja betyget från tentan?

Teacher commented 27 December 2013

Frågorna på muntan är problemlösningsuppgifter av den typ som finns på mästarprov och på kursens övningar, men eftersom presentationen görs muntligt är det inte samma krav på detaljnivån som på mästarproven. Det är betygskriterierna som bestämmer vad frågorna kan handla om. Till exempel, för nivå A på tentabetyget är betygskriteriet: "konstruera och analysera approximationsalgoritmer eller heuristiker, eller visa undre gränser för approximation". Då kan en fråga till exempel vara: "Konstruera och analysera en algoritm som approximerar problemet X inom en konstant" eller "Visa att problemet Y inte kan approximeras inom 3/2 om inte P=NP".

commented 28 December 2013

Jag skrev inte tentamen den 20:e december - när ges omtentan i ADK?

Teacher commented 29 December 2013

Nästa teoritentatillfälle för ADK är ordinarietentan för kursen DD2352 Algoritmer och komplexitet som går 5 juni 2014 klockan 9-12. En gemensam omtenta för DD1352 och DD2352 ges också i augusti 2014. Efter varje teoritenta finns det möjlighet att munta till högre betyg.

 
Teacher Viggo Kann posted 20 December 2013
commented 27 December 2013

Ska man dyka upp sin bokade tid eller starttiden för passet man har bokat in sig på?

Teacher commented 27 December 2013

Trots att bokningssystemet visar starttiden för hela redovisningspasset så ska du dyka upp på den tid du bokat och inte på starttiden för passet.

 
under HT 2013 adk13

Teacher Viggo Kann created page 27 September 2013

Teacher Viggo Kann changed the permissions 27 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 28 September 2013

Jag har problem att tolka uppgiftslydelsen på fråga 3.

Hur ska "Låt n vara totala antalet tal i indata" tolkas? Är problemstorleken, dvs komplexiteten ska anges som O(g(n))? Är n=p+s eller n=p+s+[summan av längden på listorna i alla reaktionstuplar] eller något annat? Hur kommer m in?

Har k samma värde för alla reaktioner? Vad är komplexiteten för att titta på varje element i listan över ämnen som behövs för given en reaktion? Beror den på problemstorleken?

Teacher commented 28 September 2013

n är problemstorleken, m är det största ämnesnumret som ingår i indata, k behöver inte ha samma värde för olika reaktioner. Komplexiteten för att indexera i en array är 1. Använd enhetskostnad i analysen.

Här är ett exempel på indata som bör skingra alla oklarheter:a[]=[1,2,4], b=5, r[]=[(3,[1,4]), (5,[2,3,4])].
Eftersom det är 11 tal i indata så blir n=11. Eftersom största ämnesnumret är 5 så blir m=5.

På föreläsningen den 7 oktober kommer lydelsen till uppgift 3 att gås igenom.

commented 28 September 2013

I fråga 3, kan man anta att listan med möjliga reaktioner är sorterad efter ämnesnummer som de framställer? Dvs om två reaktioner framställer samma ämne, kommer de ligga bredvid varandra i indataarrayen?

Teacher commented 29 September 2013

Nej, man kan inte anta att indata är sorterat om det inte står det i uppgiftslydelsen.

commented 29 September 2013
The content of this comment is hidden.

has hidden kommentaren 29 September 2013

Reason: Emil undrar: Kan man anta att varje ämnesnummer mellan 1 och m finns med i indata? Svaret är nej. Att jag tog bort frågan här beror på att den fortsatte med en analys av vad olika svar på den har för verkningar, men mästarprovet ska lösas utan samarbete eller hjälp.
commented 29 September 2013

Ok, då vet jag. (Försökte formulera frågan utan att säga för mycket, men men ...)

Teacher commented 30 September 2013

mästarprovssidan finns nu ett dokument med titeln "Vad är pseudokod? En vägledning till hur man skriver pseudokod i mästarprovet". Det beskriver syftet med pseudokod, ger riktlinjer för pseudokodsskrivande och ger exempel på pseudokod.

Teacher commented 30 September 2013

På föreläsningen idag gick jag igenom lydelsen till fråga 1. Vanligaste frågan var om man får byta ordning på orden i texten. Det får man inte (för då förstör man texten).

Kristoffer Emanuelsson removed his/her comment
commented 3 October 2013

Tips till er som vill skriva lösningar i LaTeX men inte riktigt vet rent tekniskt hur ni kommer igång kan använda den här mallen. Resultatet blir någonting i stil med så här.

Dokumentation över pseudokod-syntax: http://pages.cs.wisc.edu/~tdw/files/alg.pdf.

För att få ut en pdf, så kör kommandot "pdflatex texten.tex" på någon av skolans datorer, eller ssh:a till u-shell.csc.kth.se och kör det därifrån.

commented 4 October 2013

På fråga 2, får kedjan vikas ner en rad utan att byta håll? Alltså, får nästa länk av kedjan läggas på raden nedanför utan att också byta riktning?

Teacher commented 4 October 2013

Nej, kedjan måste byta riktning när den går ner till nästa rad.

commented 6 October 2013

Ang fråga 3. Är ämnet b endast uppbyggt av råvaror a[1...p] eller kan det vara uppbyggt av råvaror samt/eller ämnen i r[1...s].

Exempel: Vi får a[1,2,3,4,5]. Vi vill framställa b. I listan r[1...s] hittar vi (b,[1,2,c,5]) - men även (c,[3,4]). Dvs vi kan framställa b genom att först bygga c. Är detta ett möjligt scenario?

commented 6 October 2013

Får man designa algoritmerna i mästarprovet med andra progammeringsparadigmer såsom funktionell programmering?

Teacher commented 6 October 2013

Pseudokoden kan vara byggd på funktionell programmering, bara det är tydligt vad som menas. Men det är klokt att undvika programspråkskonstruktioner som tar mer än konstant tid, så som till exempel ofta är fallet i logikprogrammering, för det blir svårt att analysera tidskomplexiteten då.

På föreläsningen måndag 7 oktober kl 11 kommer uppgift 3 att gås igenom, så den som har frågor på formuleringen av uppgift 3 är mycket välkomna då.

commented 8 October 2013

För uppgift 3, tillhör talet m också indata?

Elias Lousseief removed his/her comment
Teacher commented 8 October 2013

Nja, m är inte direkt indata, men det kan beräknas ur indata som det största ämnesnumret som ingår i en reaktion.

m kan vara större än antalet ämnen som ingår i indata (för vissa ämnesnummer kanske inte förekommer). Men det är inte större än att man till exempel kan deklarara en array av storlek m.

commented 9 October 2013

Alltså kunde du inte sagt det tidigare eller från början, alltså att man kan deklarera en array av storlek m? I uppgiftslydelsen ser det ut som att talen i indata kan vara i princip hur stora som helst, vilket ju innebär att man inte hur som helst bara kan deklarera en array av storlek m utan att man använder för mycket minne. I alla olika problemlydelser jag läst genom åren har jag aldrig stött på att man kan anta att indatatalen (om det bara står heltal) är så små att det går att deklarera en array med storleken av det största talet. Om så ändå är fallet brukar en tydlig övre gräns på det största talet anges, eller någon typ av indikation att största talet är av samma storleksordning som storlek på indata etc.

Det var egentligen det här jag ville komma fram till i min fråga förut, då du tog bort min fråga, eftersom, precis som du skrev ovan, olika svar på den ger olika verkningar, och jag hade ingen lust att göra uppgiften svårare än vad som egentligen behövs.

Teacher commented 9 October 2013

Jag är ledsen att du fick intrycket att uppgiften var mycket svårare än den var. När talen i indata anger storlekar av något slag så kan det som du skriver vara så att datastrukturer med storlek av det största talet tar för mycket plats. I denna uppgift är talen nummer (på ämnen) och då är det en annan sak. Om du hade frågat om minneskomplexitet m var okej så hade jag svarat ja. I uppgift 3 är det ordoklassen för tidskomplexiteten som ska vara lika med undre gränsen. Hoppas inga oklarheter återstår nu!

commented 9 October 2013

Kan du avslöja huruvida det förekommer direkta eller indirekta loopar i reaktionslistorna? Typ:

r(2[2,4,5])

eller

r(2[3,4,5], 3[2,4])

Teacher commented 9 October 2013

Ja, det kan självklart förekomma cykliska beroenden bland reaktionerna.

commented 10 October 2013

Jag lämnade mitt mästarprov i den svarta brevlådan märkt CSC på Osquars Backe 2, plan 4 (enligt uppgiftslydelsen???). Kommer mitt prov att hamna i rätt händer?

commented 11 October 2013

Du sa något om att vi inte behövde vara noggranna med t ex triviala loopar. Innebär det att om jag låt säga vill kopiera en matris så räcker det att beskriva det med ord i algoritmen? Eller var det invarianten som var överflödig för (mer eller mindre irrelevanta och) triviala loopar?

commented 11 October 2013

Kopiera matris skulle kunna se ut så här:

copy[1..n,1..n] <- matrix[1..n,1..n]

Det är väl tillräckligt? (Tar naturligtvis hänsyn till en sån sats vid tidskomplexitet)

Teacher commented 11 October 2013

Inlämning av mästarprovet kan göras i den svarta brevlådan som sitter i trapphuset utanför studentexpeditionen på plan 4 i E-huset. Om expeditionen är öppen lämnar man in där.

Vad som är "tillräckligt" i pseudokod beror på pseudokodens syfte och sammanhanget. I mästarprovsuppgift 2 är det rimligt att skriva en matriskopiering på det sätt som Erik Norell föreslår.

På föreläsningen sa jag att man inte behöver ange invarianter för och argumentera korrekthet för triviala loopar. Det är dom delar av algoritmen som inte är självklara som behöver motiveras.

commented 11 October 2013

Hej, på uppgift 2 står det att man ska motivera att algoritmen är korrekt. Ska man föra ett resonemang för att algoritmen är korrekt eller vill du vill ha något mer konkret, t.ex. induktionsbevis eller hoare-logik? Och generellt i mästarprovet, måste man beskriva algoritmen förutom pseudokoden helt? Eller räcker det med att förklara kod som inte är trivial?

Teacher commented 11 October 2013

En god vana är att inleda med att förklara idén till algoritmen och därefter ge pseudokoden. Efter det analyserar man tidskomplexiteten och motiverar korrektheten. Korrekthetsmotiveringen kan se ut på många sätt. Om man använder dekomposition eller dynamisk programmering ska man utnyttja rekursionen i motiveringen (visa att rekursionen löser problemet och visa att pseudokoden implementerar rekursionen). Självklara delar (som att en slinga summerar talen i en array) behöver man inte bevisa. Läs Emmas häfte om pseudokod för att förstå vad som krävs av algoritmbeskrivningen. Titta på gamla mästarprov och deras lösningar för att få en uppfattning om vad som förväntas.

Johan Stenberg removed his/her comment
commented 11 October 2013

Tack då vet jag vad jag ska göra!

commented 12 October 2013

Vet inte om du svarar på frågor under helgen Viggo, all heder om du gör det men jag har full förståelse om du inte gör det. Svar på måndag blir nog i senaste laget, men jag har bara mig själv att skylla som inte tänkt på att fråga om detta tidigare. Det gäller två frågor kring uppgift 3 och båda berör minneskomplexitet. Ett ja eller nej räcker för min del. 

1) Det är inte angivet hur stort 's' kan vara i 'r[1..s]'. Vi vet att i '(j,[i1..ik])' så är 'j' och 'i' mindre än 'm', men även att det kan förekomma fler förekomster av ett ämne i 'r'. Med andra ord så finns inte angivet någon begränsning på 's'. Ska vi därmed anta att 's' kan vara hur stort som helst, t ex kan vi inte med säkerhet veta att det går att deklarera en array av storlek 's'?

2) Får vi ha hur komplexa datastrukturer som helst (om man kan motivera varför de behövs)? För att ta ett konstigt exempel: kan jag, i uppgift 3, deklarera en m*m-matris där varje element är en heap  - om det behövs?

commented 12 October 2013

Erik, som Viggo skrev tidigare så verkar det som att minneskomplexiteten inte spelar någon roll i denna uppgift, utan det han vill att man ska optimera är tidskomplexiteten.

I övriga fall brukar man nästan alltid kunna anta att minnesanvändningen får vara åtminstone linjär mot storleken på indata. Det vill säga man kan anta att indatat får plats i RAM.

commented 12 October 2013

Tack Emil! Det svaret duger för mig om du läser det här Viggo. Så du behöver endast svara ifall Emils resonemang inte skulle vara ok.

Eric Klaesson removed his/her comment
commented 13 October 2013

Angående Eriks exempel om komplexa datastrukturer, kan man anta att tiden det tar att skapa dessa är försumbar? Är det till exempel okej att deklarera en m*m-matris av stackar? Tekniskt sett så behöver man väl ägna konstant tid per element för att initialisera varje stack, vilket då skulle göra tidskomplexiteten beroende av m.

commented 13 October 2013

Okej, ang latex-paketet som Emil rekommenderade för pseudokod.

Jag ville dela upp pseudokoden på två sidor och det har jag lyckats med..

dock vill jag sätta radräknaren till rätt siffra, då den börjar om på 1 igen på andra sidan. Låt oss säga att jag vill sätta den på 24 istället.

Har läst lite i dokumentationen, men detta fungerar ju inte.. och vad betyder alg@inmargin?
\newcounter{alg@inmargin}\setcounter{alg@inmargin}{24}

commented 13 October 2013

Hmm jag vet inte, Eric. Oftast brukar algoritmerna få plats på en sida :)

Kan du kanske dela upp koden i två eller fler funktioner?

commented 14 October 2013

Vet inte vilket algo-paket ni använder men algpseudocode kan man göra

\setcounter{ALG@line}{11}

med t.ex.

\begin{algorithmic}[1]
\setcounter{ALG@line}{11}
\For{$i := 1$ to $m$}
    \State $n := n+1$
\EndFor
\end{algorithmic}

None

commented 23 October 2013

Hur gör man om man ännu inte redovisat Mästarprov 1 och det inte verkar finns några lediga tider att boka kvar?

Teacher commented 23 October 2013

Hej Magnus! Sista redovisningspassen var idag onsdag 23 oktober 2013. Du hade bokat ett pass igår. Det går inte att redovisa mästarprovet efter idag, så vi får hänvisa till ommästarprovet i januari.

commented 31 October 2013

Nu när mästarprov 1 är redovisat och klart, kommer det att läggas upp lösningsförslag för uppgifterna?

commented 1 November 2013

Se till att prenumerera på kursen i kth social, då får du uppdateringar direkt på emailen ;)

https://www.kth.se/social/course/DD1352/subgroup/adk13/post/resultat-pa-mastarprov-1-mast/

John Eriksson removed his/her comment
commented 1 November 2013

Emil, jag har redan inställt att få dagliga mejl från KTH Social, men det skickades först kl. 4 på natten timmarna efter att jag frågade. När jag skickade kommentaren kunde jag inte heller se någon länk bland menyerna.

commented 1 November 2013

Jag håller med om att kth social inte är optimalt för att föra fram viktig information, då information från lärare brukar spridas ut på tre olika sätt: genom att uppdatera sidorna som finns, genom att posta viktig information bland kommentarer till inlägg, eller skapa nya "lärarinlägg" som finns till höger i menyn på kursens startsida som är ganska svåra att upptäcka tycker i alla fall jag.

Det man kan göra är att ställa in inställningarna på att man får notifieringsmailen "direkt" istället för ett samlat mail kl 4 på natten. Det kan man ställa in här: https://www.kth.se/social/course/DD1352/subscription/

commented 18 November 2013

Angående mästarprov 2, uppgift 1, får man anta att textpackningsproblemet alltid blir en Nej-instans (oavsett målfunktion) om någon ordlängd är större än radlängden?

Teacher commented 18 November 2013

(Det är bara beslutsproblem som har ja-instanser och nej-instanser.)

Ni kan, liksom i mästarprov 1, anta att alla ordlängder i indata är begränsade av radlängden.

commented 18 November 2013

Hej,

Får man anta någon övre gräns för hur stora talen i indata-mängden till mängdpartitioneringsproblemet i uppgift 1 kan vara? Eller räcker det att analysera tidskomplexiteten med avseende på enhetskostnad?

Teacher commented 19 November 2013

Förtydligande till uppgift 1 och 3 på mästarprov 2

Uppgift 1

Egentligen är NP definierat med hjälp av Turingmaskinen, och därför ska bitkostnad användas vid komplexitetsanalysen om man ska vara noga. NP-verifikationen och reduktionen ska vara polynomiska i indatas längd. Om indata består av n bitar så är uppenbarligen antalet tal i indata mindre än n och största talet i indata mindre än n bitar.

Uppgift 3

Ni kan anta att det existerar en lösning till problemet, alltså att det i indata finns minst ett exjobb för varje mål som bedömts ha bristande kvalitet.

Teacher commented 20 November 2013

Bedömningen av uppgift 1 på mästarprov 2

I uppgift 1 är alla indata positiva heltal. Jag har fått frågor om vad som händer om man ändå tillåter ordlängder som är noll. Bedömningen av uppgift 1 kommer att bli så att den som löser uppgiften med ordlängder som tillåts vara noll (men i övrigt har en korrekt lösning) får mindre fel. Det är nämligen bara en liten ändring av reduktionen som behövs för att den inte ska generera några ordlängder som är noll.

commented 20 November 2013

Kan man anta att listan med positiva tal i mängdpartitioneringsproblemet innehåller minst ett tal?

commented 21 November 2013

Måste bitkostnad användas för uppgifternas komplexitetsanalys eller är det endast ifall man skall vara noga?

Teacher commented 22 November 2013

Emil: Ja, det går bra att anta att mängdpartitioneringsproblemets indata består av minst ett tal.

Adrian: Bitkostnad ger bara en faktor n större komplexitet (där n är antalet bitar i största talet) i detta fall så det spelar ingen roll för kravet att algoritmen ska vara polynomisk. Men jag vill gärna att ni visar att ni kan räkna med bitkostnad, så gör det!

commented 22 November 2013

Får man underkänt eller mindre fel om man räknar med enhetskostnad istället för bitkostnad?

Teacher commented 23 November 2013

Om man inte räknar med bitkostnad i den skriftliga lösningen får man chans att fixa till det vid den muntliga redovisningen.

commented 23 November 2013

På fråga tre på mästerprov 2 ska man anta att UKÄ problemets lösning bara är ja eller nej, eller kan man anta att den om ja skickar med en ja-instans som är utformad så som vi antog i fråga 2?

I lösningarna till gamla mästarprov ser det ut som om man bara kan säga att det är uppenbart att reduktionen är polynomisk, utan att ange exakt vad komplexiteten blir, när är det ok att detta är uppenbart?

Känner mig lite osäker på komplexitetsanalys med bitkostnad så vart kan man läsa mer om det? (utöver det som står på frl 1)

På lösningen till mästerprov 2 2012 första uppgiften anges att komplexiteten är O(n^2), beror det på att sigma adderas med si vilket med bikostnad tar n tid och att detta sker i en for-loop så det blir n^2? Om jag har en räknare i en loop som adderar 1 för varje varv, är komplexiteten då n^2 med bitkostnad, n för att n varv sker och n för varje addition?

På fråga 1 om man känner sig ganska lost på beviset av att reduktionen är korrekt (men är ganska säker på att den är korrekt, kan bara inte motivera det), kan man istället reducera ett av problemen från frl 25 till det givna problemet eller är det just Mängdpartitionering som måste reduceras?

Teacher commented 23 November 2013

Här är svar på alla Moas frågor på mästarprov 2:

1. Ett beslutsproblemet är alltid en fråga med svaret ja eller nej. En algoritm som löser beslutsproblemet svarar på denna fråga; den ger alltså ett booleskt värde som resultat. En ja-instans är ett indata till ett beslutsproblem för vilket problemets svar är ja.

2. Det är uppenbart när det är uppenbart. Om du och läraren som du redovisar för har olika uppfattningar om vad som är uppenbart så får du förklara varför det är uppenbart. Det lönar sig alltså inte att skriva att något är uppenbart om man inte tycker det.

3. Bitkostnad innebär inget mer är det som står på föreläsning 1. Det finns många exempel i kursens övningar och i gamla mästarprov som du kan titta på. Bitkostnad och enhetskostnad skiljer sig bara åt när det sker beräkningar med stora tal. I detta mästarprov är det bara additioner av tal som görs och då räcker det att veta att det tar linjär tid i talens storlek (dvs antal bitar i talen) att addera två tal.

4. I uppgift 1 från mästarprovet 2012 adderas tal med n bitar n gånger, vilket tar tid O(n^2). Att räkna upp en räknare med steget 1 från 1 till n innebär n stycken additioner av tal med log n bitar vilket tar O(n log n). Om man gör det riktigt smart räcker det faktiskt med O(n) bitoperationer.

5. Det är tillåtet att i uppgift 1 välja ett av problemet ur listan från föreläsning 25 att reducera, men jag vill inte rekommendera det.

commented 24 November 2013

Var finns listan över NP-svåra problem som man kan utgå ifrån att de är NP-svåra i mästarproven? Och vad är den engelska benämningen på mängdpartitionering?

commented 24 November 2013

Daniel:

Ordlista för ADK (partition problem): https://www.kth.se/social/course/DD1352/page/ordlista-8/

Lista på NP-fullständiga problem: http://www.csc.kth.se/utbildning/kth/kurser/DD1352/adk13/schema/F25.pdf

commented 25 November 2013

På uppgift 3, kan man anta att det alltid finns en lösning för dem indata man får, dvs att det verkligen finns ett tal k för vilket det för varje mål finns minst ett exjobb som har bristande kvalitet?

commented 25 November 2013

Tonima: Se Viggos inlägg 19 november kl. 00:24 på denna sida. 

"Uppgift 3
Ni kan anta att det existerar en lösning till problemet, alltså att det i indata finns minst ett exjobb för varje mål som bedömts ha bristande kvalitet."

commented 27 November 2013

Måste man använda bitkostnad även vid komplexitetsanalysen av uppgift 3, eller är det okej med enhetskostnad där?

Teacher commented 27 November 2013

Problemet i uppgift 3 har inga tal som indata så det lär inte vara aktuellt att räkna med stora tal i den uppgiften. Därför finns det ingen anledning att använda bitkostnad.

commented 28 November 2013

Varför har Anders Ye 0 lediga platser! Jag är djupt besviken är det någon som kanske vill byta? :)

commented 28 November 2013

Alltså angående formuläret man ska fylla i:

"visualiseringsdemo den 10/11 (NP-reduktionsvisualisering med Alvie)"

10 november var en söndag så då hade vi ingen föreläsning.

Teacher commented 28 November 2013

Sant. Alvie-demon var 11/11 och inte 10/11!Var snäll och tolka 10/11 som 11/11 i formuläret.

Niklas Axelsson removed his/her comment
Niklas Axelsson removed his/her comment
Teacher commented 25 December 2013

Niklas, det står rätt i uppgiften. Du behöver läsa på mer om hur man visar NP-fullständighet.

 
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 10 September 2013

angånde labteorin ska hur ska den redovisas?

Administrator commented 10 September 2013

Labbteoriuppgifterna får lösas i grupp men till övningen ska var och en ta med sig en egen skriftlig lösning. Det är dock okej om två personer har med var sitt exemplar av samma lösning som man har skrivit tillsammans.

Någon gång under övningens första timme kommer labbteorin att redovisas muntligt för en kamrat. Ni kommer då att grupperas två och två och ställa ett urval av teorifrågorna till varandra. Efter detta ska ni lämna in frågeprotokollet och era skriftliga lösningar till övningsassistenten.

Resultatet av labbteorin kommer några dagar senare att synas i Rapp.

commented 11 September 2013

Hur många tecken bör man ta hänsyn till utöver å, ä, ö?

Administrator commented 12 September 2013

Det givna programmet tokenizer.c definierar vilka tecken som ska vara med och vad som utgör ett ord.

commented 13 September 2013

Förstår att en viktig del av labben är att inte använda mycket minne. För att träna på att lösa problem där man inte kan lagra allt i primärminnet. Hur mycket minne får man använda?

Administrator commented 13 September 2013

Konstant minne (dvs oberoende av antalet ord i indexet) är okej att använda.

commented 18 September 2013

Vi får felmeddelandet "export: command not found" när vi försöker export LC_COLLATE=C. Vi har även testat bash -c "export LC_COLLATE=C" utan framgång. Vad gör vi för fel?

Administrator commented 18 September 2013

Kommandot export hör till bash shell, så om ni kör något annat shell får ni sätta variabler med något annat kommando (till exempel setenv LC_COLLATE C om ni kör tcshell). Eller också startar ni bash med kommandot bash och därefter ger export-kommandot. Se Unixlathunden för mer information.

commented 19 September 2013

Annars brukar det gå bra med att skriva allt på samma rad (åtminstone i bash):

anvnamn@dator:~$ LC_COLLATE=C sort ...

Då sätter man temporärt LC_COLLATE=C bara för det programmet som körs.

commented 16 December 2013

Om man kör /info/adk13/labb1/tokenizer < /info/adk13/labb1/korpus | sort > /var/tmp/ut hamnar orden å, ä, ö längst upp - vad gör man för att åtgärda detta?

Teacher commented 16 December 2013

Ge kommandot    export LC_COLLATE=C       innan du kör sort så blir sorteringsordningen som den ska.

 
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 6 December 2013

Finns det flera möjligheter att redovisa restlabbar eller är det bara den 10:e som gäller?

Teacher commented 6 December 2013

Det finns en restlabbstid 19 december 2013 och en 10 januari 2014. Se detaljschemat för detaljer. Därefter går det normalt att redovisa restlabbar på labbtillfällena i systerkursen DD2352 under våren.

 
November 2013
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 18 October 2013

Vi får NullPointerExeption på testfall 27 på "Reduktion av bipartit matchning till flöde". Något tips om vad som kan vara felet här? Vi har testat med kantmängder som 0 och hörnmängder som 0. Dessutom skapar vi inga objekt, så vi känner oss lite lost.

Tacksam för svar.

Teacher commented 19 October 2013

Testfall 27 är en stor graf. Det är nog interaktionen med domaren som ger upphov till felet. Se till att in- och utmatningen använder Kattio och att ni gör flush efter att flödesinstansen skrivits ut, så att domaren kan lösa instansen och skriva ut en flödeslösning innan programmet läser den.

commented 19 October 2013

Ah det löste sig. Bytte ut allt mot Kattio istället så fungerade samma kod :)

Men en anna sak. Om kattis har accepterat din lösning av "den svarta lådan" i steg två, och sen får du time limit exceeded på steg 3 när man lägger ihop allting, kan man förutsätta att den svarta lådan är bra, och man borde snabba på reduktionen, eller finns det en möjlighet att även flödesproblemet löses för långsamt, även om steg 2 är passerat?

Teacher commented 23 October 2013

Steg 2 testar flödesalgoritmen på många olika typer av flödesgrafer. I steg 3 kommer flödesalgoritmen bara att testas med instanser som kommer från reduktionen av bipartit matchning, och dessa har ett speciellt utseende. Därför kan det ibland hända att flödesalgoritmer som klarar steg 2 tar lite för lång tid på steg 3, även om detta inte är avsikten.

commented 23 October 2013

Tack. Kom på lite fler optimeringar man kunde göra, så löste det sig fint.

commented 28 October 2013

Vi får felet "Försöker trycka mer flöde genom kant än den har kapacitet" på första testfallet i labbdel 2 på Kattis. Vi har testat med alla tesfall i kursmappen och allt ser korrekt ut, vi lyckas inte få något likande fel alls med någon testkörning utan allt verkar fungera. När vi skriver ut värdet för flödet för varje kant har vi till och med en koll att den inte är högre än kapaciteten. Några idéer? Hur kan graferna se ut, finns dubbelkanter, lömska grafer eller s och t som inte finns, osv? Hur stora värden på flödet kan det vara, så stora att de inte får plats i en short?

commented 28 October 2013

Varför köra short? Int fungerar väl bra?

Teacher commented 29 October 2013

Om man får felet "Försöker trycka mer flöde genom kant än den har kapacitet" beror det ofta på att man fått flöde i en bakåtkant som har kapaciteten noll. Algoritmen ska klara alla sorters grafer som uppfyller indatakraven, även såna som inte har någon förbindelse mellan källan och utloppet. Inga dubbelkanter. Kapaciteterna ryms i en int (och kanske också i en short).

commented 29 October 2013

Testar kattis med flöden som är över 1 i storlek i första uppgiften?

Teacher commented 29 October 2013

Kattis testar med bipartita grafer, inte med flödesgrafer, i första uppgiften. Flödesgrafen ska ert program generera i reduktionen.

commented 29 October 2013

Okej, men kan en kantvikt i den bipartita grafen ha ett värde över 1?

För jag printar ut:  io.println(a + " " + b + " " + 1); vid en kant och tar ingen hänsyn till kantvikten

Teacher commented 29 October 2013

I reduktionen av problemet bipartit matchning till flödesproblemet så ska alla kanter i flödesgrafen ha kapaciteten 1. Varje kant har flera värden så det är oklart vad du menar med "kantvikten".

commented 30 October 2013

Lite osäker på varför jag får wrong answer isf, men det blir ett trevligt problem för dagen...
Som tur är så har jag en till fråga!

I ett av exemplen ovan så är indata:

4
1 4
5
1 2 1
1 3 2<----
2 4 2<----
3 2 2<----
3 4 1

När kattis testar programmet kommer indatan att kunna se ut såhär, för jag har valt att inte läsa av värdet i sista kolumnen då jag antar att i vårt problem kommer den alltid att vara 1!

Men det kan vara så att ni vill ha en generell lösning till ett flödesproblem, stämmer detta?

Teacher commented 30 October 2013

I uppgift 2 ska ett program som löser flödesproblemet för generella flödesgrafer konstrueras. Det betyder att kapaciteterna inte behöver vara bara 1. Detta framgår av uppgiftslydelsen och exemplen som getts.

commented 30 October 2013

Vi har också problem med just uppgift 2 där Kattis anser att vi har "Wrong Answer" men vi kan inte finna var felet ligger, vi passerar aldrig case 1.
Vi har dessutom genererat flertalet grafer med programmet flowgen och jämfört vårt resultat med det som programmet maxflow visar och ser ingen skillnad.

Här är en körning med exemplet som nämndes ovan från io (fet-stil output):

4
1 4
5
1 2 1
1 3 2
2 4 2
3 2 2
3 4 1
4
1 4 3
5
1 2 1
1 3 2
2 4 2
3 2 1
3 4 1
commented 30 October 2013

Vi har också problem med wrong answer i uppgift 2. Vi har byggt 3 separata program i java som alla klarar våra testfall utanför kattis. Men i kattis får vi endast "Försöker ta ut mer flöde än vad som trycks in i nod skiljd från källan" samt "Försöker trycka ut mer flöde genom kant än den har kapacitet". Vad kan vara fel? Vi har hittat på så många specialfall vi kan men programmet fungerar för alla.

Assistant commented 30 October 2013

Tänk på att bakåtkanterna ska ha "initialkapacitet" 0! (Det är inte förrän man har ett flöde genom kanten e som det kan bli aktuellt att minska det flödet. Restkapaciteten på en bakåtkant talar ju om hur mycket man kan minska flödet längs den kanten.)

commented 30 October 2013

Ahhh.. sant :) Hade missade de, nu till att optimera koden så att den klarar case 27 :)

Tack Emma! :)

Tonima Afroze removed his/her comment
commented 31 October 2013

Är cykler tillåtna i uppgift 2?

Teacher commented 31 October 2013

Flödesgrafen är en generell riktad graf och kan innehålla cykler. Men ett flöde i grafen kan förstås aldrig gå i en cykel.

Robin Engström removed his/her comment
commented 31 October 2013

Vi får Time limit exceeded på testfall 28, är det något speciellt med den grafen eller är den bara väldigt stor?

Assistant commented 31 October 2013

28 är ungefär lika stort som 27 (nära maxstorleken) och jag har ingen lathund som berättar vad varje testfall är till för...

Teacher commented 31 October 2013

Det finns ingen dokumentation av vilket testfall som testar vad i Kattis. Labbuppgiften är att skriva ett program som är korrekt och tillräckligt snabbt, och det visas genom att det klarar alla testfall. Om man kör fast på ett specifikt testfall kan man fråga en labbhandledare på nästa labbtillfälle och då kan labbhandledaren (om ni har gått med i adk13 i Kattis) kolla i Kattis på just det testfallet och kanske ge en ledtråd till varför programmet fastnar på det.

commented 6 November 2013

Vår algoritm får problem när flowgen ger oss kanter både mellan a och b och mellan b och a. Dvs det finns kanter vars bakåtkant inte har kapacitet 0 i början. Är denna typ av indata korrekt?

Assistant commented 6 November 2013

Ja, en riktad graf kan ha kanter både från a till b och från b till a. Bakåtkanterna ni lägger till hör till restflödesgrafen som behövs i lösningsmetoden ni använder (Ford-Fulkerson/Edmond-Karp), och är ett sätt att representera att man kan minska flödet längs en kant som redan har flöde. 

Eric Molin removed his/her comment
Eric Molin removed his/her comment
commented 7 November 2013

Vi klarar alla testfall i del 1, och del 3, men i del 2 får vi time limit exceeded på testfall 27. Finns det nån förklaring till detta? Känns oerhört konstigt. Vi har exakt samma maxflödesalgoritm.

commented 7 November 2013

Vi klarar i uppgift 2 galant upp till 26, men i uppgift 27 får vi plötsligt "Utdatafilen inte fullständig, saknades kanter". Att felsöka detta testfall är extremt svårt då vi inte kan hitta några testfall där detta gäller. Hjälp?

commented 7 November 2013

Vi får time limit exceeded på testfall 26 i steg 2. Vi kommer inte på fler sätt att göra programmet snabbare, och vi har gjort alla uppenbara optimeringar. Är det något speciallfall som vi kan ha missat?

commented 7 November 2013

På uppgift 2 säger Kattis "Memory limit exceeded" på testfall 2. Hur begränsat är minnesutrymmet?

commented 7 November 2013

Minnesutrymmet är 64 MB. Det kan man se om man tittar i Kattis på problemsidan. Där ser man dessutom tidsgräns.

Assistant commented 7 November 2013

Till er som undrar om TLE i steg 3: Det är inte meningen att man ska ha större problem i uppgift 3 än i uppgift 2 med tiden, men det kan ju vara gränsfall. Om ni inte använder Kattio, och skriver i Java, kan ni eventuellt snabba upp IO med att använda Kattio.

Titta i övrigt på vilka datastrukturer ni använder, och att de är tillräckligt snabba, inte innebär en massa indirekta ominstansieringar osv.

Den som använder DFS kan skissa på ett testfall som triggar värstafallskomplexiteten, och se att det kan vara värt att byta till BFS.

Assistant commented 7 November 2013

För alla som undrar över "Wrong answer" för steg 2, fundera på om er algoritm gör rätt på ett testfall med exempelvis s=1, t=7 och kanterna 

1 2 10, 1 3 11, 2 4 8, 2 5 2, 2 6 11, 3 4 11, 4 2 3, 4 7 8, 5 7 2, 6 7 11,

där det inte ska spela någon roll i vilken ordning stigarna hittas. Det här är ett exempel jag gav till någon som frågade mig tidigare.

Eric, det fel som rapporteras som att det saknades kanter i utdatafilen, är att ni inte skriver ut en så stor utdatainstans som ni påstår i början. Jag vet inte om det är relaterat till andra testfallet ovan.

commented 7 November 2013

Vad jag har märkt så verkar trean alltid ta längre tid än tvåan, om man använder samma kod från tvåan i trean.

Assistant commented 7 November 2013

Marcus: Specialfall i för testfall 26 i adkmaxflow känner jag inte till något om. Jag har bara samma tips som för steg 3 i labben: kontrollera om det finns snabbare datastrukturer eller standardmetoder för det ni vill göra, se till att in- och utläsning är effektiv!

Assistant commented 7 November 2013

Emil: tack för iakttagelsen!

Den som vill utsätta sitt program för lite tuffare tester kan skicka in koden till problemet maxflow. Formatet för de första raderna av in- och utdata behöver ändras då, men algoritmen ska vara densamma.

commented 7 November 2013

Ni som kör Java och får Time Limit Exceeded, här är några optimeringstips:

1. Använd inte LinkedList. Kör istället ArrayList alternativt ArrayDeque (för kö-funktionalitet).

2. För att iterera över en ArrayList, använd inte inbyggda iteratorer utan gör det manuellt, dvs. skriv inte for(Obj obj : list) { ... } utan skriv for(int i=0; i<list.size(); i++) { Obj obj = list.get(i); ... }

I i alla fall uppgift 3 verkar man kunna spara ca 1.5 sekunder på att göra detta enligt mina tester.

För att få ännu bättre tid bör man givetvis köra C++ ;)

commented 15 November 2013

Hej!
Jag får felet: "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2.
Någon som vet vad jag gör för fel?

Teacher commented 16 November 2013

Meddelandet "Fel!  Kunde inte läsa svarsgrafen" i uppgift 2 betyder att programmet inte matade ut något som kunde tolkas som en  "svarsgraf", alltså ett flöde. Det kan till exempel bero på att det inträffat ett särfall (exception) som programmet fångat och skrivit ut istället för att skriva ut ett flöde.

commented 16 November 2013

Fast exceptions brukar väl skrivas ut till stderr och inte stdout? Vad jag vet så ignorerar Kattis allting som kommer på stderr.

Assistant commented 18 November 2013

Det stämmer att Kattis ignorerar stderr, och att det därför är lämpligt att göra sina debug-utskrifter där (även om det har hänt en gång att väldigt frekventa debug-utskrifter gjort att ett program tagit för lång tid).

 
Scheduling staff created event 5 November 2013
Teacher Viggo Kann edited 6 November 2013

Redovisning av extralabben

Redovisningstid för extralabben till labb 4 som kan ge betyg A eller B på tentamomentet. Detta är enda tillfället då extralabben kan redovisas.¶

I mån av tid tas även redovisningar av restlabbar emot.¶



Scheduling staff cancelled the event 14 December 2013
 
Scheduling staff created event 5 November 2013
Teacher Viggo Kann edited 6 November 2013

TentamenExtra labbredovisning

Restlabbsredovisning¶

Scheduling staff cancelled the event 14 December 2013
 
October 2013
Teacher Viggo Kann posted 16 October 2013
Teacher Viggo Kann edited 17 October 2013

Ändring av ADK-övning 17 oktober 2013 Anders övningsgrupp träffas i Q24 kl 13-15. (obs, ändrad sal!)

Marcus övningsgrupp träffas i M32 kl 13-15.

Emmas övningsgrupp ställs in och ersätts av en frågestund fredag 18 oktober kl 13-14 i seminarierum 4523 (D-huset, plan 5). Titta på övningsuppgifterna innan du går på frågestunden så att du har något att fråga om. Den som vill kan förstås gå till Anders eller Marcus grupp istället.

 
Teacher Viggo Kann posted 10 October 2013
 
Teacher Viggo Kann posted 10 October 2013
 
under
HT 2013 adk13
Scheduling staff created event 26 February 2013
Scheduling staff edited 31 August 2013

[u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, TCSCM1-SPRS', u', TCSCM1-TD', u'DPUB3']TIEMM1DKIA, TKOMK3

Scheduling staff edited 14 September 2013

CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS, TCSCM1-BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, [u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'TCSCM1-SPR, S', u'TCSCM1-TD', TIEMM1DKIA, TKOMK3u'DPUB3']

Scheduling staff edited 20 September 2013

V1K1 (K1 , Teknikringen 56)

Administrator Viggo Kann edited 20 September 2013

Observera att salen är ändrad.¶

Scheduling staff edited 10 October 2013

OnTisdag 27 nov3 december 2013 kl 103:00 - 114:00

K1 (K1 , Teknikringen 56)V2

Scheduling staff cancelled the event 14 December 2013
 
Assistant Emma Enström posted 3 October 2013

Emma Enström tagged with Schema. 3 October 2013

 
September 2013
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 16 September 2013

KATTIS verkar inte ha kursen adk13 ännu. När ändras detta?

Administrator commented 17 September 2013

Nu är kursen adk13 skapad i Kattis och labb 2-domaren finns med där. Övriga labbar läggs till efter hand.

Gå till adk13 i Kattis och klicka på Jag är student på den här kursen och vill registrera mig på Kattis.

commented 24 September 2013

I fråga 4, ska det stå O(2max(n,m)) (linjär tid) eller O(2^max(n,m)) (exponentiell tid)?

Administrator commented 24 September 2013

Detta uttryck blev fel i överföringen från gamla kurswebben. Det ska stå 2^max(n,m) alltså exponentiell tid. Tack för påpekandet! Jag har nu korrigerat sidan.

commented 29 September 2013

Finns det någon begränsning på hur långa orden i ordlistan eller indata är?

Teacher commented 29 September 2013

Försök konstruera programmet utan att sätta någon ordlängdsbegränsning i programkoden (men självklart sätter tillgången på minne en praktisk gräns). Alla ord i testordlistorna är äkta ord, så minnesutrymmet ska räcka till även om programmet använder kvadratiskt mycket minne.

commented 30 September 2013

Får man fler än ett förösk på KATTIS?

Teacher commented 30 September 2013

Det går bra att skicka in om och om igen till Kattis, även efter det att Kattis godkänt inskickningen. På det sättet kan man fortsätta att optimera och se hur snabbt programmet kan bli, om man har lust med det.

 
Teacher Viggo Kann posted 27 September 2013

Viggo Kann tagged with mästarprov. 27 September 2013

 
Teacher Viggo Kann posted 19 September 2013
Administrator Viggo Kann edited 20 September 2013

Ingen flytt av föreläsningar 23 och 25 september! Det går inte att byta salar nästa vecka så vi får hålla tillgodo med dom salar som vi schemalagts i, alltså sal V1 den 23 september kl 11-12, sal D2 den 24 september kl 9-10 och sal V1 den 25 september kl 11-12.

Däremot kommer sal V1 att bytas mot större och bättre salar föreläsningarna 9 oktober, 25 november och 27 november. Detta kommer attssa ändringar synas nu i schemat inom kort.

 
under
HT 2013 adk13
Scheduling staff created event 26 February 2013
Scheduling staff edited 31 August 2013

[u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, TCSCM1-SPRS', u', TCSCM1-TD', u'DPUB3']TIEMM1DKIA, TKOMK3

Scheduling staff edited 14 September 2013

CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS, TCSCM1-BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, [u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'TCSCM1-SPR, S', u'TCSCM1-TD', TIEMM1DKIA, TKOMK3u'DPUB3']

Scheduling staff edited 20 September 2013

VF1

Administrator Viggo Kann edited 20 September 2013

Observera att salen är ändrad.¶

Scheduling staff cancelled the event 14 December 2013
 
under
HT 2013 adk13
Scheduling staff created event 26 February 2013
Scheduling staff edited 31 August 2013

[u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, TCSCM1-SPRS', u', TCSCM1-TD', u'DPUB3']TIEMM1DKIA, TKOMK3

Scheduling staff edited 14 September 2013

CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS, TCSCM1-BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, [u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'TCSCM1-SPR, S', u'TCSCM1-TD', TIEMM1DKIA, TKOMK3u'DPUB3']

Scheduling staff edited 20 September 2013

V1D2

Administrator Viggo Kann edited 20 September 2013

Observera att salen är ändrad.¶

Scheduling staff cancelled the event 14 December 2013
 
Scheduling staff created event 17 September 2013
Administrator Viggo Kann edited 17 September 2013

OBS! Föreläsningen är flyttad till sal M2.¶

Scheduling staff cancelled the event 14 December 2013
 
Scheduling staff created event 10 September 2013
Administrator Viggo Kann edited 10 September 2013

OBS! Föreläsningen flyttad från kl 11-12 till kl 12-13 för att en större sal skulle kunna bokas.¶

Nya salen är F1.¶

Scheduling staff edited 14 September 2013

[{'user_name': u'Viggo Kann', 'user_id': u'viggo'}]

[u'DD1352H132']

CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS, TCSCM1-BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, [u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'TCSCM1-SPR, S', u'TCSCM1-TD', TIEMM1DKIA, TKOMK3u'DPUB3']

Scheduling staff cancelled the event 14 December 2013
 
Scheduling staff created event 10 September 2013
Administrator Viggo Kann edited 10 September 2013

OBS! Föreläsningen flyttad från kl 11-12 till kl 12-13 för att en större sal skulle kunna bokas.¶

Scheduling staff edited 14 September 2013

[{'user_name': u'Viggo Kann', 'user_id': u'viggo'}]

[u'DD1352H132']

CDATE3, CDATE3-INT, CDATE3STEK, DPUB3, TCSCM1, TCSCM1-AS, TCSCM1-BER, TCSCM1-DAT, TCSCM1-DSY, TCSCM1-IT, TCSCM1-LJD, TCSCM1-PRS, [u'TCSCM1-LJD', u'TCSCM1-DSY', u'TKOMK3', u'TCSCM1-DAT', u'TCSCM1-IT', u'TCSCM1-AS', u'TCSCM1-SPR', u'CDATE3', u'CDATE3STEK', u'TCSCM1-BER', u'TCSCM1', u'TIEMM1DKIA', u'CDATE3-INT', u'TCSCM1-SPR, S', u'TCSCM1-TD', TIEMM1DKIA, TKOMK3u'DPUB3']

Scheduling staff cancelled the event 14 December 2013
 
Teacher Viggo Kann posted 9 September 2013
 
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Teacher Viggo Kann changed the permissions 21 August 2013

Kan därmed läsas av alla och ändras av lärare.
commented 5 September 2013

Hej. Kolumnen för A-betyget syns inte här på hemsidan?

Administrator commented 5 September 2013

Det gick bra att se betygskriterierna i den gamla versionen av KTH Social, men nu när kurswebben lanserats med det nya utseendet så klipps för breda tabeller av. Jag har felanmält detta. Den som vill se betygskriterierna i sin helhet kan kolla i kurs-PM.

Jag ber om ursäkt för detta krångel som beror på att KTH bytte utseende på kurswebben utan att ha testat systemet tillräckligt.

Administrator commented 5 September 2013

Nu har en ny version av kurswebbspresentationen lagts upp där det finns en Min/Max-knapp uppe till höger som gör att man kan se hela tabellen!

 
under HT 2013 adk13

Teacher Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
 
under HT 2013 adk13

Viggo Kann created page 21 August 2013

Administrator Viggo Kann changed the permissions 4 September 2013

Kan därmed läsas av alla och ändras av lärare.
 
Feedback News