News feed

Log in to your course web

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).

August 2016
Teacher Viggo Kann posted 18 August 2016
 
May 2016
under HT 2015 adk15

Viggo Kann created page 20 August 2015

commented 13 December 2015

Går det en omtenta i Januari, isåfall när?

Teacher commented 14 December 2015

Daniel, det går ingen omtenta i januari. Systerkursen DD2352 som går i period 3-4 har tenta  efter period 4 och den fungerar också för DD1352. DD1352 och DD2352 har sedan en gemensam omtenta i augusti.

commented 14 December 2015

Gjorde det inte det i fjol eller har jag hört fel från en äldrekursare?

Teacher commented 14 December 2015

Ordinarietentan i ADK går i period 2, men den är utbruten ur tentaperioden och ligger före jul, i år 18 december. Det har aldrig gått någon omtenta i kursen i januari.

commented 18 December 2015

Kommer info om tentakomplettering bara man väntar?

Teacher commented 18 December 2015

Ja. 

commented 18 May 2016

Gäller bonuspoängen även för omtentorna?

Teacher commented 18 May 2016

Thomas, svaret är ja, "på alla tentor inom ett år från kursstart", som det står ovan.

 
January 2016
under HT 2015 adk15

Viggo Kann created page 20 August 2015

commented 3 October 2015

För teoriuppgift 1: Ska man bara analysera algoritmen för bipartita grafer eller för flödesproblemet generellt?

Viggo Kann removed his/her comment
Teacher commented 3 October 2015

Alexander, det är algoritmen för flödesproblemet som är det väsentliga i analysen i teoriuppgift 1. Det räcker att analysera denna flödesalgoritm för grafer som genererats från reduktionen av bipartitmatchningsproblemet.

commented 19 October 2015

"Denna graf har alltså X = {1, 2}".
Varför är inte 4 med i X också?

Mvh
Daniel

Teacher commented 19 October 2015

Daniel, första talet i indata anger antalet element i X. Om det är 2 är det två element i X, nämligen 1 och 2.


Daniel Richter removed his/her comment
commented 3 November 2015

Hej!

Vi har kört fast på testfall 1 för flödesproblemet (uppgift 2)i Kattis (https://kth.kattis.com/submissions/925049). Vi får felmeddelandet "Fel! Inte maximalt flöde". Vi har testat att generera grafer m.h.a. flowgen och kontrollera svaret vi får med det som svarta lådan i uppgift 1 fick. I samtliga fall har maxflödet blivit detsamma (det enda som skilt sig har varit ordningen för kanterna, men detta skall enligt uppgiften inte påverka resultatet). Någon idé om vad som kan vara fel och vad man testa på?

Teacher commented 3 November 2015

Veronica, det stämmer att ordningen mellan kanterna inte påverkar resultatet. Ert program genererar helt enkelt inte det maximala flödet på testfall 1. Gå igenom programkoden noga och leta efter var den inte gör exakt som pseudokoden ovan.

commented 3 November 2015

Vi har redan gått igenom vår kod jämfört med pseudokoden ovan. Vi ser ingen skillnad och då alla testfall vi kört får rätt svar så lyckas vi inte hitta vart ett fel finns. Skulle man kunna få ett exempel på ett typ av testfall som resulterar i ett felaktigt testflöde.

commented 3 November 2015

Vi har nu lyckats lösa problemet tack vare Johan Sannemos tips på testfall. Det visade sig att det inte var något fel i algoritmen utan fel på inläsning av data.

commented 4 November 2015

Hej! I steg 2, kan man utgå ifrån att om (u,v) tillhör flödesgrafen så gör inte (v,u) det? Det blir lite bökigt att hålla koll på restflödena annars :)

Teacher commented 4 November 2015

Både (u,v) och (v,u) kan ingå i en flödesgraf. Restkapaciteten i (v,u) är c[v,u] - f[v,u]. Om (v,u) inte finns i ursprungliga grafen är c[v,u] noll.

commented 4 November 2015

Tack för förtydligandet, det var nog bara jag som tänkte konstigt!

Teacher commented 5 November 2015

Nu finns ovanstående hjälpprogram kompilerade för Mac OS X också under katalogen
/info/adk15/labb3/OSX

Tack Johan Sannemo för hjälp med detta!

Shapour Jahanshahi removed his/her comment
 
under HT 2015 adk15

Viggo Kann created page 20 August 2015

commented 29 September 2015

När kommer de upp?

Teacher commented 29 September 2015

Nu!

commented 29 September 2015

Är tanken att man ska kunna svara på alla frågor nu? Eller kommer det tas upp saker under kommande föreläsningar behövs för att svara på frågorna?

Teacher commented 29 September 2015

Henning, ni kan börja jobba med alla tre uppgifterna nu, men för att lösa uppgift tre optimalt kan det hjälpa att använda metoder som tas upp på någon av dom närmaste föreläsningarna.

commented 29 September 2015

Okej, tackar!

commented 1 October 2015

Funktionen f(x) = b - x saknar minimum i [a, a + k) där a, b, k > 0 och b > a + k.

Teacher commented 1 October 2015

Svar till Isac: Detta är inget problem, för uppgift 2 utspelar sig helt på heltalspunkter på tallinjen. Efter förflyttningarna står alltså personerna fortfarande på heltalspunkter.

commented 7 October 2015

Ay, man kan ta bort andra personers bokningar på Doodle-länkarna. Känns ju inte som det bästa systemet....

Teacher commented 7 October 2015

Jag vet, men jag litar på er.

Det går att göra en en striktare Doodle -- men då kan de som saknar Doodlekonto inte ändra sina egna bokningar och inte heller se sina bokningar igen när de har glömt bort dem. Och jag litar mycket mer på er hederlighet än ert minne. :)

commented 11 October 2015

Är indata i uppgift 3 enbart ordlistan eller fås n (längden på det längsta ordet) och m (antal ord) med?

Teacher commented 11 October 2015

Alexander, man kan anta att m och n är kända.

(Om man inte känner till m och n så det ju billigt -- tidskomplexitet är inte högre än för resten av algoritmen -- att räkna ut dem.)

Mattias Larsson removed his/her comment
Joel Hagrot removed his/her comment
commented 12 October 2015

Är man helt ute och cyklar om man har kommit fram till en algoritm med en tidskomplexitet som inte direkt med något funktionsuttryck beror på k i uppgift 2, och man därför inte kan uttrycka tidskomplexiteten i annat än bara n?

Kan man anta att ordlistan i uppgift 3 inte nödvändigtvis är sorterad?

Tack på förhand!

Teacher commented 13 October 2015

Joel, det är tillåtet att ge ett tidskomplexitetsuttryck som inte innehåller k om tidskomplexiteten är oberoende av k.

Ordlistan som är indata i uppgift 3 behöver inte vara sorterad, se till exempel exemplet på indata.

Johan Darnald removed his/her comment
commented 20 October 2015

Tjenare, jag verkar ha missat att trycka på spara på doodle. Trodde att jag hade bokat 10.40 på torsdag med Adam. Hur göra nu?

Tackar på förhand!

Teacher commented 20 October 2015

Felix, kontakta Adam eller Marcus och kolla om dom har tider kvar.

Henning Spett removed his/her comment

Teacher Stefan Nilsson changed the permissions 30 November 2015

Kan därmed läsas av studerande och lärare och ändras av lärare.
commented 30 November 2015

Kort fråga om uppgift 1: man ska alltså inte lösa optimeringsproblemet öht?

Teacher commented 30 November 2015

Hej Ludvig! Man ska inte lösa problemet i uppgift 1 (eller 2) utan visa att det är NP-fullständigt. Om du gjorde logiklabben i programmeringsparadigmkursen som handlade om detta problem så fick du lösa det där, men det gick bara för små indata. Nu kommer förklaringen till att det inte gick att lösa effektivt för större probleminstanser!

Teacher Viggo Kann changed the permissions 30 November 2015

Kan därmed läsas av alla och ändras av lärare.
commented 1 December 2015

När jag har läst om delmängdssumma så formuleras det lite annorlunda på vissa sidor. Ibland står det att input kan vara endast icke-negativa tal, ibland kan det vara även negativa. Får man anta att det bara kommer inte positiva tal i för delmängdssumma?

Teacher commented 1 December 2015

Henning, använd definitionen av delmängssumma som finns i kursboken och i föreläsningsanteckningarna (föreläsning 25). Det innebär att talen i indata är positiva heltal. Problemet är fortfarande NP-fullständigt om man tillåter talen att även vara negativa, men det är inte den vanliga definitionen.

commented 4 December 2015

Hur hög nivå får man ha på sin pseudokod? Är det okej att använda mängdoperatorer såsom snitt, tillhörighet, och grafoperationer såsom grannskapet till ett hörn, och att skriva saker som att "G ← G utökad med hörnet x, kanten {x,y}"? Så länge man motiverar tidskomplexiteten tänker jag att det blir väl bara lättare att läsa.

Teacher commented 4 December 2015

Ludvig, det är okej med denna typ av pseudokod (så länge du har koll på tidskomplexiteten).

commented 4 December 2015

Fråga 2

Vad är en given lösning? Är det en spindel och ett nätverk eller är det en spindel, konspiratörer och ett nätverk?

Representeras nätverket som en graf G=(V, E)?

Teacher commented 4 December 2015

Ezeddin, att bestämma vad som är en lösning ingår i uppgiften.

Du får själv avgöra hur nätverket ska representeras på lämpligt sätt.

Andreas Forsten removed his/her comment
commented 7 December 2015

På fråga 1.

Är n , dvs antalet platser på flyktingboendet, ett positivt heltal?

Teacher commented 7 December 2015

Alexander, antal är icke-negativa heltal. I detta fall är problemet ointressant om antalet platser på boendet är noll.

Patrik Schwermer removed his/her comment
commented 7 December 2015

Något sen fråga, men i uppgift 2. Får en "vanlig person" vara bekant med fler än en konspiratör?

Teacher commented 7 December 2015

Alexander T: Ja, annars vore problemet trivialt.

commented 30 December 2015

Har det sedan igår lagts upp anmälningslistor någonstans för muntlig redovisning av ommästarprov? Jag hittar det inte.

Teacher commented 31 December 2015

Stefan kommer att lägga upp anmälningslistorna på denna sida.

commented 3 January 2016

Jag är omregistrerad på kursen så på inlämningsuppgifter ser jag bara ommästarprov adk14, ska jag lämna in där då? Det står ju också att det är ca ett år försenad.

Teacher commented 3 January 2016

Det går inte att lägga till nya personer efter att inlämningsuppgiften lagts upp så du kan inte lämna in den ordinarie vägen. Du får mejla din lösning till mej istället så ska jag skicka den vidare till den som tar emot redovisningen.

commented 3 January 2016

Jag ser fortfarande ingen anmälningssida och sista dagen är imorgon. Har den flyttats eller är den bara försenad? Och angående den nya inlämningslänken verkar den vara för adk14? Står att inlämningen är försenad med 363 dagar och ger mig inget alternativ att lämna in.

Teacher commented 3 January 2016

Niklas, eftersom anmälningssidan är försenad så tror jag att Stefan sträcker ut anmälningstiden någon dag.

Rätt länk till inlämningsuppgifterna finns under kursomgången HT2015 adk15 i menyn till vänster.

Stefan Nilsson removed his/her comment
Teacher commented 5 January 2016

Nu går det att boka tider för ommästarprovsredovisning. Boka din tid senast onsdag 6/1.

Joel Hagrot removed his/her comment
commented 8 January 2016

Tjena!

Jag undrar hur det fungerar med plussning i denna kurs.

- Går det att plussa t.ex. enbart A- eller C-uppgiften på ett visst mästarprov om man redan klarat de lägre uppgifterna i motsvarande mästarprov denna omgång?

- Kommer nästa kursomgång få en ny komplexitetsuppgift motsvarande extralabben i labb 4, och kommer man att kunna göra om bara den i så fall (förutsatt att man blev godkänd på denna kursomgångs tenta)?

Om svaret är ja på någon av dessa frågor, gäller det svaret även om man vill plussa momentet under den s.k. systerkursen som går under vårterminen?

Allt förutsatt att kursen inte ändras, givetvis.

Tacksam för svar!

Teacher commented 8 January 2016

Svar till Joel:

På muntan får man bara uppgifter på dom betygskriterier som man ännu inte visat att man uppfyllt.

Plussning innebär att man gör om ett prov (till exempel tenta eller mästarprov) som man redan är godkänd på för att få högre betyg än man tidigare hade. Vid en plussning börjar man från noll, dvs man kan inte utnyttja att man redan visat vissa kunskaper. I ADK kan man plussa teoritentan och mästarproven, och det kan man göra inom kommande omgångar av såväl ADK som systerkursen Algoritmer och komplexitet (DD2352).

Troligen kommer extralabben i labb 4 att vara kvar nästa år och redovisas i januari, men det är för tidigt att utlova något. Extralabben finns inte i systerkursen DD2352.

 
under HT 2015 adk15

Viggo Kann created page 20 August 2015

Teacher commented 10 November 2015

Ett förtydligande om divorna (p1 och p2 ovan):

Divorna är garanterade att få (minst) en roll var vid rolltilldelningen

commented 10 November 2015

Måste alla roller vara med i någon scen?

Teacher commented 11 November 2015

Jorge: Ja, tänk på det verkliga problemet: varje roll i en film eller skådespel är med i minst en scen.

commented 11 November 2015

Har en tolkningsfråga gällande teoriuppgift 5. Kan en och samma skådespelare ha roller i båda grupperna? Och i sådana fall, krävs det att alla roller i den ena gruppen skall kunna spela mot alla roller i den andra gruppen?

commented 11 November 2015

Är det tal eller uttryck som söks på fråga 5 det minsta antalet skådespelare som krävs för att instansen ska kunna ge något annat svar än "Nej" ?

commented 11 November 2015

Förstår inte hur en lösning kan se ut till fråga 1. Ska man skriva vilka roller alla kan ha för att det ska ge svaret ja? 

commented 16 November 2015

Hej, vad menas med bevisa i denna mening: "Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte." ? Vad ska man bevisa och ska beviset vara ett korrekthetsbevis eller ett enklare bevis som visar att det fungerar? 

Teacher commented 16 November 2015

Hej Aleksandar! Under dom närmaste föreläsningarna och övningarna kommer vi att beskriva och exemplifiera hur NP-fullständighetsbevis ser ut.

commented 21 November 2015

Hej,

Vi har ett c++ program som mha cin och cout läser och skriver input/output. När vi läst en rad så skriver vi ut en rad, typ. När vi kör programmet lokalt på våra datorer så får vi förväntad output, men när vi kör det på kattis så får vi "kunde inte läsa antal roller i en scen". Finns det något konstigt som kattis gör, eller går det inte att läsa och skriva ganska blandat (alltså måste vi läsa in allt och spara det innan vi kan skriva ut något)? Detta är första gången jag försöker med ett c++ program till kattis.

commented 21 November 2015

Ah, nvm, det visade sig bara att vi var korkade och inte kunde grundläggande matte (såsom att 11 != 9)

commented 4 January 2016

Finns det någon bokning till redovisningen av extralabben eller det drop-in?

Teacher commented 4 January 2016

På extralabbsredovisningen är det som vanligt Qwait som används för kön. Redovisningar av extralabben har förtur. Bland dessa är det dom som har tenta som börjar klockan 14 som har förtur (skriv då detta i kommentaren i Qwait).

commented 4 January 2016

Tack så mycket!

Michel Postigo Smura removed his/her comment
commented 7 January 2016

Jag lyckas inte hitta var redovisningen håller hus?

Teacher commented 7 January 2016

Redovisningen 8 januari 2016 blir i Spelhallen.

 
December 2015
under HT 2015 adk15

Viggo Kann created page 20 August 2015

commented 14 December 2015

Kommer man kunna redovisa/få hjälp med någon av labbarna på kursen Algoritmer och Komplexitets labbtillfällen, eller måste man vänta till i juni om man inte hann redovisa idag?

Teacher commented 14 December 2015

Lisa, närmaste möjlighet för labbredovisning är vid extralabbsredovisningstillfället  8 januari 2016 kl 13-16. I mån av tid kan också övriga labbar redovisas då.

Det går också bra att redovisa ADK-labbarna på labbtiderna i DD2352 Algoritmer och komplexitet i period 3-4, förutsatt att det finns någon labbass som behärskar ADK-labbarna (labb 1 och 3 i ADK ingår inte i DD2352), men det brukar dom göra.

Nästa tillfälle blir labbveckan i juni.

 
November 2015
Teacher Viggo Kann posted 23 November 2015
commented 23 November 2015

Dokumentet komplexitetsmotivering på http://www.csc.kth.se/utbildning/kth/kurser/DD1352/adk13/komplexitetsmotivering.pdf verkar det vara något skumt med. Den slutar aldrig ladda.

Teacher commented 23 November 2015

Daniel, problemet med att vissa PDF-filer inte laddas beror på webbservern. Det går dock att spara filen som länken pekar på och sen titta på den. Men nu har jag lagt upp alla PDF-filerna från komplexitetsdelen av detaljschemat som dokument i Social, så då ska det fungera att titta på PDFerna direkt.

commented 24 November 2015

Kommer uppg. 1 gås igenom idag den 24e eller imorgon enl. ovan? Idag är väl egentligen den närmaste, tänker jag.

Teacher Viggo Kann edited 24 November 2015

Mästarprov 2 finns nu tillgängligt på kurswebben.

Uppgifterna kommer att gås igenom på dom tre närmaste föreläsningarna (uppgift 1 den 254/11, uppgift 2 den 275/11, uppgift 3 den 1/12).

Det kommer att anordnas ett ommästarprov för mästarprov 1 i slutet av kursen (läggs upp 18 december och redovisas i omtentaveckan i januari) där den som inte är godkänd på mästarprov 1 kan redovisa för betyg E och den som har fått betyg E eller D på mästarprov 1 kan redovisa för betyg C. Det kommer också att vara en munta i tentaveckan i januari då vilket betyg som helst i kursen kan höjas. Det betyder att den som vill satsa på högt betyg i ADK fortfarande har alla möjligheter att få det. Så gör så många uppgifter du kan på mästarprov 2!

Lycka till!

Viggo och Stefan

Teacher commented 24 November 2015

Tack för påpekandet Peter! Datumen för genomgångarna denna vecka blev fel. Nu har jag korrigerat dom. Jag går igenom uppgift 1 idag.

Teacher commented 24 November 2015

I uppgift 1 på mästarprov 2 fanns det två olika indata som hette n, vilket inte var meningen. Jag har korrigerat lydelsen nu.

n ska stå för antalet platser i boendet och m ska stå för för antalet flyktinggrupper.

 
Teacher Viggo Kann posted 10 November 2015
 
October 2015
under HT 2015 adk15

Viggo Kann created page 20 August 2015

commented 24 September 2015

En av uppgifterna i teorin till labb 2 är att "Visa att tidskomplexiteten för Distance(w1, w2) är Omega(2^max(n,m)) i värsta fallet".
Funktionen har 3 rekursiva anrop: (n-1,m), (n-1,m-1) och (n,m-1) och returnerar när någon av {n,m} är 0.
Men för naiva fallen att en av n > 1 och m = 0 är det uppenbart att den inte "växer minst lika snabbt" som Omega(2^max(n,m)) eftersom funktionen kommer returnera utan några rekursiva anrop. Vidare för fallet där någon av n > 1 och m = 1. Då kommer bara den "vänstraste grenen" (n-1,m) att gå djupare medan för varje nivå så kommer båda de andra rekursiva anropen med m-1 att returnera direkt. Då blir alltså komplexiteten Omega(3*n) då n>1 och m = 1.
För n > 1 och m > 1 är det som jag kan komma fram till med kunskap från föreläsningarna än så länge bara att den har komplexiteten lilla omega: omega(3^(m+n-2)). Men det är ju grovt överräknat, men jag vet inte hur jag annars ska kunna täcka att  trädet ju kan växa ner till en nivå av m+n-2 men många grenar kommer att terminera innan dess.

Av Viggo fick jag på mejl svaret: "Det är värsta fallet. Du får själv välja förhållandet mellan n och m.". Jag förstod dumt nog inte det här svaret, finns det någon annan som förstår och kan förklara hur  Omega(2^max(n,m)) "i värsta fall", kan vara rätt?

commented 2 October 2015

Fick svaret på förra lektionen. Tack för det. Den växer minst så fort i värsta fallet.

 
Teacher Viggo Kann posted 2 October 2015
 
Feedback News