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

January 2017
under HT 2016 adk16

Viggo Kann created page 19 August 2016

Teacher Viggo Kann changed the permissions 19 August 2016

Kan därmed läsas av lärare och ändras av lärare.

Teacher Viggo Kann changed the permissions 31 October 2016

Kan därmed läsas av alla och ändras av lärare.
commented 4 November 2016

När kommer problem-id för Graffärgning och Hamiltonsk cykel?

commented 7 November 2016

^

Dessutom, vad betyder "Inga monologer får förekomma."?

One user removed his/her comment
commented 7 November 2016

Teorifråga 5:

Antalet skådespelare som behövs borde rimligtvis vara relaterat till vilken probleminstans det är frågan om. Tänker jag fel eller är frågan felställd?

commented 7 November 2016

"Inga monologer får förekomma" betyder gissningsvis att en uppsättning inte får innehålla någon scen med endast en skådespelare.

commented 7 November 2016

@Mikael Min tanke också, men har den ingen riktig funktion så borde den istället förekomma som indatakrav (annars tillförd den bara meningslös "komplexitet"). Därav tänkte jag att det kanske var något annat.

Tack för svar ;)

Teacher commented 7 November 2016

Som Mikael beskrev betyder "Inga monologer" att varje scen måste ha minst två roller.

Teorifråga 5 är korrekt ställd.

Jag vet inte när Kattisproblemen kommer upp men förhoppningsvis inom ett dygn. Problemen är klara och behöver bara läggas upp av en Kattisadministratör.

commented 8 November 2016

Tiden rinner iväg och det går inte att testa mot kattis. Känner mig stressad.

Teacher commented 8 November 2016

Robin, inom några dagar ska Kattisuppgifterna vara uppe. Det är fortfarande 10 dagar kvar till bonusdatumet för labben, så ta det lugnt!

commented 8 November 2016

I graffärgningsproblemet påverkar inte eventuella dubbelkanter färgningen på något sätt, eller?

Tack på förhand :)

One user removed his/her comment
commented 10 November 2016

Någon som behöver labbpartner på denna? Skicka mig ett pm så kan vi labba :)

commented 12 November 2016

Att (kontinuerligt) hålla på och smyga in ändringar i labblydelsen så här nära inpå deadline är inte OK. Det är riktigt otrevligt och bestraffar oss som är ute i god tid.

Dessutom gäller enligt kursens labbassistenter inte alls "Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte". Jag var inte ensam om att slösa många timmar av måndagen pga detta. Oseriöst.

One user removed his/her comment
Teacher commented 13 November 2016

Hej Johan! Labbuppgiften har inte ändrats. I tisdags gjordes ett förtydligande av  labblydelsen, nämligen att varje roll i uppsättningen måste förekomma i minst en scen, vilket jag hoppas ingen tycker är konstigt. Igår förmiddags la jag in länkar till dom utlovade Kattisproblemen i labblydelsen. Jag är ledsen att Kattisproblemen las upp bara en vecka före bonusdatumet för labben. Vi ville vara säkra på att den nyskrivna specialdomaren och dom nya testfallen skulle fungera, och det tog några dagar längre än planerat.

Meningen om att man kan få redovisa utan att Kattis godkänt lösningen syftar på fallet då lösningen inte har accepterats av Kattis på grund av att reduktionen gett en så komplicerad probleminstans att Kattis inte hunnit kontrollera den inom rimlig tid. Kattis är ju tvungen att lösa ett NP-fullständigt problem för att kontrollera svaret!

commented 13 November 2016

Hej Viggo! Tack för snabbt svar (målet var dock att belysa missförhållanden snarare än diskussion).

Labbuppgiften har ändrats. Huruvida det senaste kravet är konstigt eller inte påverkar inte det faktum att vi behöver skriva om hela vår tidigare lösning (som var skräddarsydd efter tidigare kravspec, något som ofta behövs i adk:n för att klara tidskravet). Detta kombinerat med den korta tidsfristen och att vi inte alls fick redovisa vår reduktion i fredags har mördat min planering och jag tycker lite självkritik vore på sin plats.

commented 13 November 2016

Så man får alltså redovisa trots att Kattis godkänner vissa testfall för att sedan få time limit exceeded (i vårt fall korrekta lösningar fram till testfall 33/36 då vi får resultatet "time limit exceeded") så länge man kan bevisa att reduktionen är korrekt?

Teacher commented 14 November 2016

David, du beskriver just det fallet då reduktionen skapar en instans som Kattis inte klarar av att lösa inom den uppsatta tidsgränsen. Då är det tillåtet att redovisa och vid redovisningen bevisa att reduktionen är korrekt (inklusive att den är polynomisk!). Men att Kattis får time limit exceeded tyder på att reduktionen är onödigt komplicerad, så det kan ändå vara en bra idé att försöka förenkla den.

Marcus Dicander edited 30 November 2016

NP-fullständighetsreduktioner - Rollbesättning Om du redovisar labben senast den 18 november får du en bonuspoäng på tentan. Labbteoriuppgifterna nedan kan redovisas för en bonuspoäng till tentan, och detta görs på övningen den 10 november (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom.

Ansvarig för castingen på ett filmbolag behöver koppla ihop rätt skådespelare med rätt roller. Samma person kan spela flera roller, men samma roll kan endast innehas av en person. Manus anger vilka roller som är med i samma scener. Inga monologer får förekomma. Varje skådespelare får bara ha en roll i varje scen. Varje roll måste förekomma i minst en scen.

Dessutom är divorna p1 och p2 garanterade att få (minst) en roll var (och de rollerna ska självklart delta i åtminstone en scen var). Detta medför extraarbete eftersom de båda inte tål varandra och rollerna ska besättas så att de aldrig spelar mot varandra. Rollbesättningsproblemet är att avgöra ifall alla roller kan besättas med de skådespelare som finns till hands. Ingående parametrar är alltså: Roller r1, r2,... , rn Skådespelare p1, p2,... ,pk Villkor typ 1 (till varje roll): rt kan besättas av p1, p2, p6 Villkor typ 2 (till varje scen): i su medverkar r1, r3, r5, r6 och r7

IndataformatDe tre första raderna består av talen n, s och k (antal roller, antal scener och antal skådespelare, n≥1, s≥1, k≥2), ett tal per rad. 

De följande n raderna representerar villkoren av typ 1 och börjar med ett tal som anger antalet efterföljande tal på raden, följt av de möjliga skådespelarnas nummer (mellan 1 och k, kursiverade i exemplen nedan). De sista s raderna är villkor av typ 2 och börjar ett tal som anger antalet efterföljande tal på raden, följt av tal som representerar de olika rollerna som är med i respektive scen. Varje roll förekommer högst en gång på varje sådan rad, så antalet roller på en rad ligger mellan 2 och n.

Fråga: 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?

Exempel på godkända indata

nej-instans: 55 3 3 1 2 3 2 2 3 2 1 3 1 2 3 1 2 3 2 1 2 2 1 2 3 1 3 4 2 3 5 3 2 3 5        ja-instans: 654 3 1 3 4 2 2 3 2 1 3 1 2 4 1 2 3 4 2 1 4 3 1 2 6 3 2 3 5 3 2 4 6 3 2 3 6 2 1 6 UppgiftI den här laborationen ska du visa att rollbesättningsproblemet är NP-svårt genom att reducera ett känt NP-fullständigt problem, som finns inlagt i Kattis. Din reducerade instans kommer att granskas och lösas av Kattis. Du får välja mellan att reducera problemen Graffärgning (problem-id kth.adk.npreduction1) och Hamiltonsk cykel (problem-id kth.adk.npreduction2). Indataformat för dessa problem beskrivs nedan. Din uppgift är alltså att implementera en reduktion, inte att lösa problemet.

Kattis testar om din reduktion är korrekt, men du måste naturligtvis kunna bevisa att den är det vid redovisningen. Kattis svar är egentligen avsedda att vägleda dig i arbetet med beviset och påpeka om du glömt något viktigt specialfall. Vid redovisningen kommer handledaren också att fråga varför problemet ligger i NP och vad komplexiteten är för din reduktion.

Vid rättningen utnyttjas en lösare för instanser av ett (annat) NP-fullständigt problem inom rimliga storleksgränser. Av tekniska skäl har Kattis en maximal tillåten storlek på instanserna. Du får bara meddelanden om den ifall du skickar in en för stor instans. Du får redovisa din reduktion om du kan bevisa att den är korrekt, oavsett om Kattis har godkänt den eller inte.

GraffärgningIndata: En oriktad graf och ett antal färger m. Isolerade hörn och dubbelkanter kan förekomma, inte öglor.

Fråga: Kan hörnen i grafen färgas med högst m färger så att inga grannar har samma färg?

Indataformat: Rad ett: tal V (antal hörn, tex:\displaystyle 1 \leq V \leq 300) Rad två: tal E (antal kanter, tex:\displaystyle 0\le E\le 25000) Rad tre: mål m (max antal färger, tex:\displaystyle 1\le m\le 2^{30}) En rad för varje kant (E stycken) med kantens ändpunkter (hörnen numreras från 1 till V)

Hamiltonsk cykelIndata: En riktad graf.

Fråga: Finns det en tur längs kanter i grafen som börjar och slutar på samma ställe och som passerar varje hörn exakt en gång?

Indataformat: Rad ett: tal V (antal hörn, tex:\displaystyle 1\le V\le 200) Rad två: tal E (antal kanter tex:\displaystyle 0\le E\le 5000) En rad för varje kant (E stycken) med kantens starthörn och sluthörn (hörnen numreras från 1 till V)

Teoriuppgifter
* Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
* Visa att rollbesättningsproblemet ligger i NP.
* Förändra nej-instansen i exemplet på indata till en ja-instans. Hur många skådespelare behöver du lägga till i just detta fall?
* Vilken är den minsta möjliga produktion som uppfyller indatakraven för rollbesättningsproblemet och som går att sätta upp? Skriv upp indata för denna produktion!
* Tänk dig en instans där rollerna är indelade i två grupper, ungefär som i matchningsproblemet, där rollerna aldrig förekommer i samma scener som roller ur samma grupp. Hur många skådespelare behövs då?
* Anta att film a innehåller en scen med rollerna 4, 7 och 12 medan film b har tre scener med rollerna 4 och 7, 7 och 12 samt 4 och 12. Om alla övriga villkor är identiska mellan filmerna - kommer svaren då att bli likadana? Varför/varför inte?
Extrauppgift Frivillig extrauppgift som redovisas på ett särskilt redovisningstillfälle den 10 januari 2017 kl 14-17 och då kan ge betyg A eller B på lärandemålet om hantering av problem med hög komplexitet (och då behöver man inte examineras på det lärandemålet på muntan). Uppgiften görs individuellt. För att få redovisa extrauppgiften måste du vara godkänd på momentet TEN1 (dvs teoritentan).

Du ska välja att implementera valfri heuristik som löser konstruktionsproblemet: Vilka skådespelare ska ha vilka roller för att lösa rollbesättningsinstansen med så få skådespelare som möjligt? Indataformatet för rollbesättningsproblemet är detsamma som tidigare. Divorna är 1 och 2.

Utdataformat: Rad ett: antal skådespelare som fått roller En rad för varje skådespelare (som fått roller) med skådespelarens nummer, antalet roller skådespelaren tilldelats samt numren på dessa roller

Problemet ska lösas enligt villkoren som specificerats för rollbesättningsproblemet, dvs divorna måste vara med men får inte mötas, ingen roll får spelas av flera personer, och ingen skådespelare får spela mot sig själv i någon scen. Bättre heuristik (dvs färre skådespelare) ger bättre betyg. 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+1, k+2, ... Varje superskådis kan spela vilken roll som helst, men kan bara spela en enda roll.

Några testfall att testa ditt program med finns på /info/adk16/labb4/testfall/

Skriv en kort rapport (omkring en sida) där du dels beskriver vilka heuristiker din lösning använder och dels reflekterar över hur du arbetat med uppgiften och hur du möjligen kunnat arbeta annorlunda. Skriv namn på rapporten och lämna den till labbassistenten vid redovisningen.

Problemet heter (KOMMER SENARE) ikth.adk.castingheuristic på Kattis. Kattis summerar antalet använda skådespelare i testfallen och returnerar summan. För betyg B krävs ett resultat bättre än 560. För betyg A krävs 460 eller bättre. För betyg A krävs också att algoritmen använder simulated annealling, tabusökning eller annan sofitistikerad lokalsökningsheuristik. Bara den som är godkänd på teoritentan får redovisa extralabben.

I Kattis testfall är antalet roller aldrig större än 600, antalet scener aldrig större än 4000 och antalet skådespelare aldrig större än 400.

One user removed his/her comment
commented 9 December 2016

Om man satsar på B finns det något övrig krav (för extrauppgiften), eller räcker det med Kattispoängen och att man kan förklara hur man tänkt? 

Teacher commented 9 December 2016

Rebecca, det är kraven som står ovan som gäller, till exempel att uppgiften ska göras individuellt, att en rapport på en sida ska lämnas in etc.

commented 31 December 2016

Vad skiljer en sofistikerad lokalsökningsheuristik från en icke-sofistikerad sådan? 

Teacher commented 31 December 2016

Kristian, två exempel på sofistikerade lokalsökningsheuristiker är simulated annealing och tabusökning. Det är också tillåtet att använda andra heuristiker som bygger på lokalsökning men som inte bara gör enkel lokalsökning med fast djup. Du får i så fall själv vid redovisningen och i den korta rapporten tala om i vilken mening som den lösning du valt är sofistikerad.

One user removed his/her comment
 
Teacher Viggo Kann posted 2 January 2017
commented 2 January 2017

Om man planerar munta 2 moment, räcker det att boka 1 pass?

Teacher commented 2 January 2017

Ja, man bokar en tid, oavsett hur många betyg man muntar upp. Vid muntan får man en uppgift för varje betyg. 

 
under HT 2016 adk16

Viggo Kann created page 19 August 2016

One user removed his/her comment
commented 2 January 2017

Hej, 

Var bokar man sig för att munta? 

Teacher commented 2 January 2017

Kristian, information om muntabokning finns nu i nyhetsflödet för adk16 och i vänstermenyn på kurswebben.

 
December 2016
under HT 2016 adk16

Viggo Kann created page 19 August 2016

One user removed his/her comment
commented 28 September 2016

Kan vi anta att n är givet i första uppgiften?

Teacher commented 28 September 2016

Uppgiften säger bara att "Indata är en lista med par av studenter som känner varandra" så ni får själva bestämma hur indata ska representeras. Det är både tillåtet och rekommenderat att välja en representation som gör det lätt att läsa och tolka indata.

commented 28 September 2016

Får man skriva mästarprovet för hand eller måste man använda sig av något i stil med latex ?

commented 28 September 2016

Uppgift 1: Måste vi även skapa en algoritm för hur vi skapar grafen eller räcker det med en förklaring av detta i ord?

Teacher commented 28 September 2016

Kristoffer: Det går utmärkt att skriva lösningarna för hand, men ta då en kopia eller fota av lösningarna innan du lämnar in dom så att du kan kolla på dom före muntliga redovisningen.

Alexander: Algoritmen ska ges i pseudokod. Men lyd Stefans råd att välja en representation av indata som gör det enkelt att tolka indata och skapa grafen.

commented 28 September 2016

Ledsen att vara jobbig men svaret hjälper mig inte. Enligt uppgiftlydelsen ska vi bara presentera en algoritm som löser problemet. Min fråga är: ingår det i problemet att maskinellt tolka indata och konstruera sin graf eller räcker det med utifrån en graf(och valt sätt att representera den) presentera en algoritm som löser 2 provs problemet?

Teacher commented 28 September 2016

Alexander:

1. Algoritmens indata är inte en graf utan en lista av par.
2. Algoritmen ska beskrivas med pseudokod.

Därmed bör frågan vara besvarad.

commented 29 September 2016

Om man i en lösning vill använda någon generisk algoritm i stil med sökning eller sortering, måste denna algoritm då implementeras eller räcker det med att skriva att den görs?

Teacher commented 29 September 2016

Alice: Algoritmer från kurslitteraturen kan användas (anropas) i pseudokoden i dina lösningar. Du måste då noga referera till algoritmen (inklusive sidnummer). Det går också bra att hänvisa till kurslitteraturens tidskomplexitetsanalys och korrekthetsmotivering (med sidnummer) för en anropad algoritm.

commented 29 September 2016

Viggo, ditt svar till Alice gör mig en smula konfunderad.

Visst måste det vara ok att hänvisa till "allmänt kända" algoritmer (och datastrukturer för den delen), såsom görs i tidigare lösningsförslag? Exv "Sort(data)" och sedan förklara att med sorteringsalgoritm X blir det tidskomplexitet Y.

Teacher commented 29 September 2016

Johan, problemet är att "allmänt kända algoritmer" inte är väldefinierat. Om du hänvisar till algoritmer i kurslitteraturen är du på den säkra sidan. Mergesort finns till exempel i kursboken Kleinberg-Tardos på sida 224-225/130-131.

commented 29 September 2016

När jag tittade på tidigare års mästarprov för att få en bra uppfattning om vad som krävdes såg jag att man åtminstone i adk15 behövde skriva sina lösningar på engelska eftersom det fanns ickesvenskspråkiga assistenter som tog emot redovisningar.

Vilka språk är tillåtna för lösningarna till mästarproven den här kursomgången?

Teacher commented 29 September 2016

Martin, det var bara på ommästarprovet förra året där engelska behövdes. 

För årets mästarprov rekommenderar vi att ni skriver på svenska (för att träna på att föra algoritmiska resonemang på svenska - i masterprogrammen får ni träna på att föra dom på engelska).

commented 30 September 2016

Får algoritmer, datastrukturer och tidskomplexitetsanalyser från föreläsningsanteckningarna användas (med hänvisning, givetvis) om de ej förekommer i kurslitteraturen?

Teacher commented 30 September 2016

Alice, detta är inte en så enkel fråga som man kan tro. I vetenskapliga sammanhang ska man inte hänvisa till föreläsningsanteckningar och andra dokument som inte har genomgått granskning och publicering. Även om jag tror att det som står i föreläsningsanteckningarna är korrekt så är det alltså inte god sed att hänvisa till såna dokument. Jag tycker därför att du inte ska göra det. Du kan förstås ändå skriva ner och använda en algoritm från föreläsningsanteckningarna i din lösning (med referens så det inte blir plagiat), men du kan inte hänvisa till föreläsningsanteckningarnas analys av algoritmen utan måste göra analysen av den algoritm du skrivit ner själv.

commented 30 September 2016

Om man refererar till litteraturen - ska man då ta med sig kursboken till den muntliga presentationen för att kunna svara på frågor?

Teacher commented 2 October 2016

Haris, det är meningen att man vid den muntliga redovisningen ska kunna svara på frågor om den lösning man lämnat in. Vissa brukar ta med egna anteckningar och figurer för att visa upp när man förklarar hur algoritmerna fungerar, vilket är okej, men vi vill inte att ni drar upp kursboken för att leta efter svar på assistentens frågor om den inlämnade lösningen.

commented 3 October 2016

Har jag förstått det rätt om arrayen P[i] i uppgift 2 avser antalet pokestops som ligger exakt efter i kilometer. Bara så det inte är de man passerat också. Känns som en dum fråga, men blev osäker.

commented 3 October 2016

Jag har en fråga angående P listan i uppgift 2. I uppgiftslydelsen står det följande "Listan har punkter för 2 km in i vandringen, 4 km in i vandringen, 5 km in i vandringen osv". Om antalet pokestop efter 2km kommer att förekomma på index 0 i P, kommer antalet pokestop vid 3km (som inte är möjligt att nå) finnas representerad på index 1 i P följ av antalet pokestop vid 4km på index 2? Eller kommer antalet pokestop vid 4km kommer direkt efter antalet pokestop efter 2km i P? 

commented 3 October 2016

Kan man anta i uppgift 1 att grafen som bildas av vänskapsparen är sammanhängande?

Teacher commented 3 October 2016

Mikael och Jakob: P[i] beskriver antalet pokestopp som kan nås i km in i vandringen. Värdet P[3] ska alltså inte användas av algoritmen.

Teacher commented 3 October 2016

Arvid, man kan inte anta att grafen som bildas av vänskapsparen har någon speciell egenskap (utöver vad som följer av uppgiftslydelsen). 

commented 5 October 2016

I alla problem får man en viss input, t.ex. i form av tuplar '(a1,b1),(a2,b2), etc'. När man ska beräkna komplexiteten, måste man ha med den tid det tar att läsa in tuplarna, eller kan man anta att dessa är redan i minnet i en optimal datastruktur?

T.ex. problem säger att vi får indata som tuplar '(a1,b1),(a2,b2)'. Antingen behöver jag O(n) för att läsa in indata eller så antar jag att det är i minnet som t.ex. en hashmap, etc.

commented 5 October 2016

Om det för bästa möjliga tidskomplexitet är vitalt att en viss datastruktur (eller algoritmimplementation) används, ska det då uttryckas i pseudokoden eller i analysen av tidskomplexiteten?

Teacher commented 5 October 2016

Artem, hur man beräknar tidskomplexiteten beror på vilken beräkningsmodell man använder. I vissa modeller (som RAM-modellen) kan man indexera till ett specifikt element i indata, i andra (t ex Turingmaskinen) måste man läsa in indata steg för steg. Om det är relevant i din algoritm får du specificera vilken av dessa beräkningsmodell du använder i analysen. 

Alice, om en viss datastruktur behöver användas måste det synas i både pseudokoden och analysen.

commented 5 October 2016

I upg 3 står det att "Bokningen av klassrummen görs terminsvis". Kan man då utgå från att det finns ett tidigast startdatum (början av termin) och senast slutdatum (slutet av termin) som man kan boka klassrummen på?

Teacher commented 6 October 2016

Kristian, datumen och tiderna representeras i indata av positiva heltal. Kopplingen till verkliga datum och tider är inte relevant för uppgiften. Lägsta möjliga positiva heltal är förstås 1,  men det finns ingen högsta gräns som är given på förhand.

commented 6 October 2016

Vilken länk bokar man mästarprovet?

commented 6 October 2016

Borde då inte problembeskrivningen ändras? För om en högsta gräns inte existerar, så kan icke-terminsvisa tidsbokningar ske. 

Teacher commented 6 October 2016

Mästarprovsbokningarna kommer att göras från denna sida, men länksidan är inte publicerad ännu. Förhoppningsvis får Stefan upp den under dagen. 

Kristian, en högsta gräns behöver inte finnas i uppgift 3, för precisionen i tidsangivelserna är inte given. Med högre precision krävs större heltal för att representera en start- eller sluttid under den aktuella terminen. 
Men det är okej att använda enhetskostnad för att analysera tidskomplexiteten i uppgift 3.

commented 21 October 2016

När kommer facit ut till provet någon?

Teacher commented 28 October 2016

Nu finns lösningsförslagen till mästarprov 1 upplagda.

commented 22 November 2016

I uppgift 1 står att kantvikterna kan vara godtyckliga heltal. Betyder det att de kan vara icke-positiva eller till och med negativa?

commented 22 November 2016

I uppg 1, står det:

Därför kan indata representeras som en oriktad graf där vägskälen är hörn och kantvikterna, som kan vara godtyckliga heltal, anger väglängder.

Betyder det att indata även kan representeras som riktad graf också?

commented 22 November 2016

Får det finnas dubbel-, trippel-... och så vidare kanter, det vill säga två eller fler vägar från ett vägskäl som leder till samma vägskäl/hörn? Hur representeras dessa i indata i sånt fall? Måste vi bevisa att Hamiltion stig är np-fullständigt, eller räcker det med att hänvisa till beviset i övning 9? 

One user removed his/her comment
commented 22 November 2016

Mästarprov 2:

I lydelsen till uppgift 1 står det "Visa att problemet är NP-svårt genom att reducera problemet Hamiltonsk stig.". Vilket problem menas då? Är det att avgöra om det är möjligt att vinna ett specialpris? 

One user removed his/her comment
One user removed his/her comment
Teacher commented 23 November 2016

Abdallah, kantvikterna i uppgift 1 kan vara godtyckliga positiva heltal.

Joni, banan kan representeras som en oriktad graf och du behöver inte diskutera vad som skulle hända om man istället väljer en riktad graf.

Sonja, uppgift 1 handlar om en graf (och inte en multigraf) så det finns alltså högst en kant mellan två hörn.

Alfrida, "Är det att avgöra om det är möjligt att vinna ett specialpris?". Ja!

commented 24 November 2016

På fråga 3, Konstruktion av Schema

Är en lösningen polynomisk i längden av den längsta lektionen OK?

Teacher commented 25 November 2016

@Johan: Nej, lösningen ska vara polynomisk i indatas storlek. En algoritm som har polynomisk tidskomplexitet i talen i indata (dvs exponentiell i indatas storlek) kallas pseudopolynomisk. En pseudopolynomisk reduktion i uppgift 3 kan möjligen räknas som "mindre fel". Det är något vi lärare och assar kommer att bestämma när vi gör den detaljerade bedömningsmallen inför mästarprovsredovisningarna.

One user removed his/her comment
commented 25 November 2016

Kan man anta att alla vägskäl har en valens större än 2, dvs. tex:\displaystyle \forall\delta(v)\ge3? För om valensen är 2, så är det inte ett vägskäl?

commented 25 November 2016

Har grafen som ges som indata till Hamiltonstig-problemet kanter med kantvikter?

Teacher commented 25 November 2016

Artem, det går bra att anta att minst tre vägar utgår från varje vägskäl. Men det går också bra att tillåta att vägskäl har en eller två utgående vägar. I verkligheten förekommer det vändplaner i slutet på återvändsgränder (kan tolkas som vägskäl med en väg) och vägar som svänger plötsligt och kraftigt (kan tolkas som vägskäl med två vägar). Något som inte har någon verklighetskoppling är väl vägskäl med noll vägar, så det ska inte förekomma i indata.

Jakob, du kan anta att indata till Hamiltonstigproblemet är en oriktad oviktad graf (se övning 9).

commented 25 November 2016

Får man anta att maratonproblemet innehåller en parameter för storleken på specialpriset?

commented 25 November 2016

På fråga 3, Konstruktion av Schema, "Analysera tidskomplexiteten för din reduktion"

Krävs en tight övre gräns eller är det ok att vara frikostig så länge komplexiteten är polynomisk?

commented 25 November 2016

I uppgift 1, så om man har en graf med en Hamilton-stig, så ska man reducera den till ett maraton-problem där den stigen väger minst lika mycket som hälften av alla kantvikter tillsammans?

Teacher commented 25 November 2016

Artem: Maratonproblemet är att avgöra ifall det är möjligt att vinna ett specialpris eller inte. Storleken på priset är inte relevant i problemet och är därför inte indata.

Erik: Bara frågor om uppgiftsformuleringen får ställas, inte frågor om hur uppgiften kan lösas.

Johan: Ingen jättetight tidskomplexitet behöver visas. Det viktiga är att den visas vara polynomisk. Om tidskomplexitetsanalysen är för vidlyftig kommer du att behöva diskutera den vid den muntliga redovisningen.

commented 25 November 2016

Jag menar om man skall reducera ett Hamilton-stig problem till ett "man kan vinna specialpris"-problem?

Teacher commented 25 November 2016

Erik, i uppgiften står "Visa att det är NP-fullständigt att avgöra om det är möjligt att vinna ett specialpris. Visa att problemet är NP-svårt genom att reducera problemet Hamiltonsk stig (se övning 9 för definition)."

Med problemet i andra meningen avses problemet som nämns i första meningen.

commented 26 November 2016

Kan grafen som ges som indata till Hamiltonstig-problemet ha öglor? 

commented 26 November 2016

Antar att den inte kan det, eftersom den inte är en multigraf!

commented 27 November 2016

Vid analys av algoritmernas tidskomplexitet, är det valfritt att använda antingen modellen för enhetskostad eller bitkostnad eller ska man kunna redogöra för båda?

Teacher commented 28 November 2016

Mailfråga: Är det i uppgift 1 tillåtet att använda en polynomisk Turingreduktion?

Svar: Nej, det måste vara en Karpreduktion.

commented 29 November 2016

Kan man i problem 3 (och då även 2) anta att inga paradoxala krav förekommer (ex "lektion a måste ske efter lektion b" och "lektion b måste ske efter lektion a")?

Teacher commented 29 November 2016

Alice, det kan finnas krav i indata som inte kan uppfyllas. Det är till och med vanligt i schemaläggning i verkligheten.

Om det finns krav som inte kan uppfyllas så finns det ingen lösning, så då ska algoritmen svara att det inte finns någon lösning.

commented 30 November 2016

Uppgift 2. "Skolan vill optimera så att den lektion som slutar sista slutar så tidigt som möjligt" Måste vi ha med det i den polynomiska verifieringen? Alltså att föreslagna schemaläggningen är "Optimalt" i och med att dagarna slutar så tidigt som möjligt med indata?

Teacher commented 30 November 2016

Alexander, jag kan inte svara på frågor om hur man ska lösa problemet. Men observera att det ingår i uppgift 2 att formulera optimeringsproblemet som ett beslutsproblem.

commented 30 November 2016

Ok, samma uppgift. Vad menas med "Beslutsproblemet har dessutom ett mål timelimit som indata"? Är det maximala tiden som algoritmen får utföra beräkningar för att få fram en lösning eller är det maximala tiden in i framtiden som får allokeras till lektionerna?

I och med att det står mål känns det som något man ska pricka in inte komma under. T.ex. om det är maximala tiden in i framtiden så vill vi hamna på precis timelimit och inte under.

Teacher commented 30 November 2016

Alexander, läs om beslutsproblem och optimeringsproblem i avsnitt 8.1 i kursboken eller i föreläsningsanteckningarna för föreläsning 20 och 27.

One user removed his/her comment
commented 1 December 2016

Jag blev fundersam på en definition gällande hamiltonsk stig. Är en graf med endast ett hörn en ja-instans eller en nej-instans till problemet hamiltonsk stig?

Teacher commented 2 December 2016

@Gabriel Det påverkar inte komplexiteten för hamiltonstigproblemet eller svårigheten hos mästarprovsuppgiften, så välj själv ja eller nej. Själv skulle jag nog luta åt att en graf med bara ett hörn har en hamiltonstig.

commented 2 December 2016

Kan inte komma åt bokningslistan ("Sidan är behörighetsskyddad"), är det jag som gör något fel eller är det något annat som knasar? 

Teacher commented 2 December 2016

Darja, nu har du fått behörighet till sidan.

commented 2 December 2016

I uppgift 2 och 3 finns det någon övre gräns på tiden en lektion kan pågå?

Teacher commented 2 December 2016

Rebecca, det finns ingen övre gräns på tiden en lektion kan pågå.

commented 2 December 2016

Taget från bedömningskriterier för mästarprov 2:

"Anger tidskomplexitet i föreskrivna variabler."

Vilka är dem föreskrivna variablerna för uppgift 1?

Teacher commented 3 December 2016

Johannes, det stämmer att det inte finns några variabler som anger storleken i uppgiftslydelsen. Jag har nu ändrat "föreskrivna" till "lämpliga" i kriteriet. I det fall att det finns föreskrivna variabler är det naturligtvis dom som är lämpliga.

One user removed his/her comment
commented 5 December 2016

Är det bara antal anrop man ska ta hänsyn till i 3an eller spelar det också roll hur stor indatan är?

Teacher commented 5 December 2016

Mikael, i uppgift 3 ska man konstruera en polynomisk turingreduktion och analysera tidskomplexiteten för den. Mer kan jag inte säga.

commented 5 December 2016

Taget ur bedömningskriterierna för mästarprov2:

"Beskriver reduktionen övergripande i ord och ev. i bild - måttliga"

Raden under står det:

"Beskriver reduktionen tydligt - Ja "

Ska reduktionen beskrivas måttligt eller tydligt

Teacher commented 5 December 2016

Joni, för uppgift 1 och bedömningsgrunden "Beskriver reduktionen övergripande i ord och ev. i bild" är kraven måtttliga, medan det är krav på bedömningsgrunden "Beskriver reduktionen tydligt".

Det innebär att en tydligt beskriven reduktion krävs i den skriftliga redovisningen, men det behövs ingen övergripande beskrivning som beskriver reduktionen i stora drag i den skriftliga redovisningen. Däremot måste man vid den muntliga redovisningen kunna beskriva reduktionen övergripande någorlunda väl.

commented 19 December 2016

Hej, det står på detaljschemat följande:

Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.

Kommer ommästarprovs uppgifterna upp ikväll eller?

Samt så undrar jag när lösningsförslagen för mästarprov 2 kommer upp?


commented 19 December 2016

Hur går man tillväga för att boka muntliga tentan?

commented 20 December 2016

Testar igen...Hej, det står på detaljschemat följande:

Ommästarprov för mästarprov 1 och mästarprov 2 offentliggörs 19 december och redovisas skriftligt och muntligt i omtentaveckan i januari.

När kommer ommästarprovs uppgifterna upp?

Samt så undrar jag när lösningsförslagen för mästarprov 2 kommer upp?

Teacher commented 21 December 2016

Både ommästarprovsuppgifterna och lösningsförslagen till mästarprov 2 är nu upplagda.

commented 21 December 2016

Det står följande på ommästarprovs dokumentet:

Du ska lämna in den skriftliga lösningen som en PDF-fil på kurswebben för adk16 senast 6 januari 2017 klockan 24.00.

Sedan står det under länken till ommästarprovsuppgiften:

Lämna in din uppgift i brevlådan utanför CSC-skolans expedition senast 6 januari 2017

Vilket alternativ gäller? Om alternativ två gäller, vart ligger CSC-skolans expedition?

Tack!

Teacher commented 21 December 2016

Tack Joni för att du noterade dom dubbla budskapen om inlämningsplats. Jag har nu lagt upp en inlämningsuppgift med namnet ommästarprov adk16 på kurswebben. Använd den för inlämning av mästarprovet!

Jag vill också passa på att förtydliga att n är en indataparameter i uppgift 1 på ommästarprovet.

commented 23 December 2016

Halloj.

Har hittat lite olika formuleringar på kappsäcksproblemet. Vilken är det som gäller? Är det okej att anta "0-1 kapsack problem"? https://en.wikipedia.org/wiki/Knapsack_problem

commented 23 December 2016

Med reservation för att jag inte företräder kursen tror jag det är ett säkert kort att utgå från definitionen i anteckningarna till föreläsning 21.

commented 23 December 2016

Det framgår ju inte ifall man får välja fler av ett föremål, eller har jag missuppfattat något?

commented 23 December 2016

Jag (gör inte ommästarprovet, men) har förutsatt att varje unikt föremål endast kan förekomma 0 eller 1 gånger i kappsäcken.

Teacher commented 23 December 2016

Victor, det finns bara ett exemplar av varje föremål som man kan stoppa i kappsäcken i kappsäcksproblemet. Varianterna av problemet med flera exemplar som förekommer i Wikipedia kallas inte för bara kappsäcksproblemet, så om man menar en sån variant måste man förtydliga namnet.

commented 23 December 2016

Tack för svar! Ha en riktigt god jul :)

commented 27 December 2016

Hej Viggo, till ommästarprov komplexitet har jag gjort tolkningen att det är ett krav att varje student ska redovisa exakt en gång, varken mer eller mindre. Är det en korrekt tolkning?

Teacher commented 27 December 2016

Sara, jag håller med om din tolkning.

commented 27 December 2016

Ommästarprov 2 Komplexitet:

"Algoritmens uppgift är att tilldela tider så att den sammanlagda prioriteten för de studen-
ter som får redovisa blir så liten som möjligt, samtidigt som den totala kostnaden för passen inte får överstiga M".

Min fråga lyder:

Är det ett krav att konstruera en algoritm enligt ovan för ett E i lösningen? Eller räcker det med en reduktionsomvandling av instanserna?

Teacher commented 27 December 2016

Joni, i uppgift 2E ska man inte konstruera en algoritm som löser problemet utan bara formulera problemet som ett beslutsproblem och visa att det är NP-fullständigt.

commented 28 December 2016

Ommästerprov 2E

Ang indatan, ska man anta att listan med n redovisningspass är en trippel med indata, en för tid, plats och kostnad?

Ang indatan med m listor, ska man även där anta att det är ett talpar med listor, en för student och prioritet? 

Tack på förhand!

commented 28 December 2016

Ommästerprov 2E

Enligt uppgiftslydelse står följande:

...så att den sammanlagda prioriteten för de studenter som FÅR redovisa blir så liten som möjligt.

Om jag uppfattar det rätt, så får inte alla studenter redovisa?

Teacher commented 28 December 2016

Jag har just uppdaterat lydelsen för uppgift 2E på ommästarprovet (den gamla uppgiften var fel) så att man ska maximera (och inte minimera) prioritetssumman. Den nya lydelsen finns i pdf-filen ovan.

commented 28 December 2016

@Abdel-Hakim Rahmani Jag har tolkat frågan som att alla inte får redovisa. Eftersom om två elever bara anger en tid som är likadan så får den eleven med, nu efter ändringen, högst prioritet den tiden. Eftersom den andra eleven ej anget en annan tid så blir den utan redovisningspass. 

commented 28 December 2016

@Victor Kesten Tack så mycket! Jag förstod det efter att Stefan hade uppdaterat lydelsen. 

commented 29 December 2016

Efter uppdateringen av mästarprovet och tidigare studenters frågor blir jag osäker på om Viggos svar på min fråga fortfarande gäller. I uppgiftslydelsen står det "Algoritmens uppgift är att tilldela tider, högst en per student", det tolkar jag som att kravet är att varje student får redovisa 0 eller 1 gång. Vad gäller?

Teacher commented 29 December 2016

Det stämmer Sara. I den uppdaterade uppgiftslydelsen står "högst en per student" vilket betyder 0 eller 1. Det är det som gäller.

 
under
HT 2016 adk16
Scheduling staff created event 21 December 2016
Teacher commented 21 December 2016

Extra redovisningstillfälle av den frivilliga betygshöjande extralabben till labb 4. Enbart för den som inte kan delta vid ordinarie tillfället 10 januari. Föranmälan till detta tillfälle görs till viggo@kth.se senast 5 januari.

Scheduling staff edited 15 January 2018

5O1Spe (Spelhallen)6fd6bf98-7e86-4b60-b069-24f2cb451af7

Scheduling staff edited 29 May 2020

['TSVDK_CSC_3', 'TIEMM_CSCJ_1', 'CINTETSVDK_CSC_3', 'TSVDK_ALDA_3', 'TIDAB_DPUBCINTE_3', 'CDATE_3', 'TIDAB_DPUB_3']

Scheduling staff edited 16 November 2020

['TIEMM_CSCJ_1', 'TSVDK_CSC_3', 'TSVDK_ALDA_3IEMM_CSCJ_1', 'CINTE_3', 'CDATE_3', 'TSVDK_ALDA_3', 'TIDAB_DPUB_3']

Scheduling staff edited 7 May 2021

['TSVDKIEMM_CSC_3J_1', 'TIEMM_CSCJ_1DAB_DPUB_3', 'CINTE_3', 'CDATE_3', 'TSVDK_ALDA_3', 'TIDAB_DPUBSVDK_CSC_3']

 
Scheduling staff created event 7 April 2016
Teacher Viggo Kann edited 19 August 2016

TObligatorisk teoritentamen

Skrivningstiden är kl 9.00-11.00. Klockan 11.15-12.15 är det en obligatorisk tentagenomgångs- och rättningssession. Det går alltså inte att lämna tentan tidigare än 12.15.¶

Scheduling staff removed the event 2 September 2016

Scheduling staff restored the event from the trash can. 2 September 2016

Scheduling staff edited 13 December 2016

F2, Q1

Scheduling staff edited 15 January 2018

F2, Q15dc45052-b5ce-4e6c-9ca6-7e22f9eee538, 87f255a1-95f0-4932-b38e-16b6e609a8b0

Scheduling staff edited 29 May 2020

['TSVDK_CSC_3', 'TIEMM_CSCJ_1', 'CINTETSVDK_CSC_3', 'TSVDK_ALDA_3', 'TIDAB_DPUBCINTE_3', 'CDATE_3', 'TIDAB_DPUB_3']

Scheduling staff edited 16 November 2020

['TIEMM_CSCJ_1', 'TSVDK_CSC_3', 'TSVDK_ALDA_3IEMM_CSCJ_1', 'CINTE_3', 'CDATE_3', 'TSVDK_ALDA_3', 'TIDAB_DPUB_3']

Scheduling staff edited 7 May 2021

['TSVDKIEMM_CSC_3J_1', 'TIEMM_CSCJ_1DAB_DPUB_3', 'CINTE_3', 'CDATE_3', 'TSVDK_ALDA_3', 'TIDAB_DPUBSVDK_CSC_3']

 
under HT 2016 adk16

Viggo Kann created page 19 August 2016

Teacher Viggo Kann changed the permissions 19 August 2016

Kan därmed läsas av lärare och ändras av lärare.

Teacher Viggo Kann changed the permissions 1 September 2016

Kan därmed läsas av alla och ändras av lärare.
One user removed his/her comment
commented 5 September 2016

När jag kompilerar tokenizer.c får jag dessa varningar: Kompilering

När jag sedan använder mig av den kompilerade a.out och lagrar detta till en fil genom kommandot ./a.out < korpus > output så ser jag följande i output filen: Output fil

Hanteringen av ÅÄÖ är alltså inte korrekt.
Någon som känner igen problemet och kanske har en lösning?

Teacher commented 5 September 2016

Alexander, kompilatorvarningen är nog ingen fara. Du kan prova att ge väljaren 
-Wno-invalid-source-encoding
för att slippa varningen om teckenkodningen.

För att se åäö korrekt i terminalfönstret måste du ställa in terminalfönstrets teckenkodning i någon meny till terminalprogrammet. Välj ISO-8859-1 eller ISO-Latin-1.

commented 5 September 2016

Du har helt rätt Viggo, tack för hjälpen!

commented 7 September 2016
  • snabbhet (antal filläsningar och filpositioneringar per sökning)

"filpositionering" och "filpositioneringar" ger 9 resp 7 träffar på google (länkar hit inkluderade). Vad åsyftas egentligen?

Teacher commented 7 September 2016

Med filpositionering avses anrop av seek eller motsvarande funktion, se labbeskrivningen ovan.

commented 10 September 2016

Hej!
Ska användare även kunna söka efter siffror eller tecken, såsom "40" eller "@"?

/ Alfrida

Assistant commented 10 September 2016

Nej, det enda som programmen ska kunna hantera är bokstäver

commented 11 September 2016

Är tanken att vi ska använda Bob Jenkins hashfunktion för latmanshashningen av prefix (aaa, aab, aac osv)?

Vill minnas att det talades om någon hashfunktion som producerar lägre tal, och alltså skulle passa för en mindre array med bara så många index som behövs för alla prefix. Men jag kan minnas fel, eller så var tanken att vi själva skulle skriva en sån hashfunktion?

Teacher commented 11 September 2016

Ernst, det är inte bra att använda Bob Jenkins hashfunktion i detta fall. Använd en så enkel hashfunktion som möjligt som inte gör några krockar. På föreläsning 3 var det en färgfråga om detta. Tipset där var att använda en förberäknad funktion som omvandlar mellanslag till 0, a till 1, b till 2 etc och med hjälp av detta tolkar dom tre bokstäverna i prefixet som ett tal i bas 30.

commented 11 September 2016

Aha ok, ja det bör ju inte vara så svårt. Tack!

One user removed his/her comment
commented 14 September 2016

Är det ett formellt krav att vi ska använda oss av binärsökning för att hitta rätt ord inom en "prefix-grupp"? Det verkar som att linjär sökning går tillräckligt snabbt i det här fallet.

Teacher commented 14 September 2016

Ernst, är du säker på att linjär sökning är tillräckligt snabbt för alla ord? Jag vill att den som gått ADK alltid ska använda binärsökning istället för linjärsökning i tidskritiska algoritmer. Det är så enkelt att programmera binärsökning så det ska mycket till för att inte använda det.

commented 15 September 2016

Rad 48 i tokenizer.c borde ändras till
printf("%s %10ld\n", buf, startpos);
Då paddas siffrorna från tokenized med mellanslag, vilket gör att när den skickas till sort kommer den att sortera siffrorna i numerisk ordning istället för teckenordning. dvs:
a   20
a 100

istället för som det nu blir:
a 100

a 20

Det gör att sammanhangen skrivs ut i den ordningen som de faktiskt förekommer i korpus-filen. Några fel blir lättare att hitta och saker beteer sig allmänt mer som man väntar sig.

Teacher commented 15 September 2016

Mikael, det är en bra idé, men vi kan inte ändra labbfilerna under pågående kurs, så ändringen görs till nästa år. Tack för idén!

commented 16 September 2016

Hej, en fråga inför redovisningen: alla datorer är upptagna i spel- och sporthallen. Är det okej att redovisa på egen laptop? Vår sökning går snabbare på skolans datorer ändå.

Teacher commented 16 September 2016

Vi räknar med att den som redovisat lämnar sin dator, så därför kommer det att bli lediga datorer efterhand. Det är 7-8 labbhandledare som tar emot redovisningar parallellt, så även om kön ser avskräckande lång ut så kommer den att betas av i rask takt.

commented 8 December 2016

Jag har ännu inte fått Labb1 inrapporterad i Rapp (däremot Labb 2, 3 och 4). Normal fördröjning eller bör jag undersöka saken vidare?

Teacher commented 8 December 2016

Johan, om en labb inte har kommit in i Rapp vid det här laget så är det något fel. Var snäll och visa upp ditt påskrivna labbkvitto så för jag in resultatet i Rapp.

 
under HT 2016 adk16

Viggo Kann created page 19 August 2016

Teacher Viggo Kann changed the permissions 19 August 2016

Kan därmed läsas av lärare och ändras av lärare.

Teacher Viggo Kann changed the permissions 1 September 2016

Kan därmed läsas av alla och ändras av lärare.
commented 4 September 2016

Hej! Om man klarade några av labbarna (inte alla) förra året - är det tillåtet att göra om dem i år för att få bonuspoäng till tentan?

Teacher commented 4 September 2016

Anna-Karin, det går bra att göra om labbteorin och labbarna för att samla nya bonuspoäng.

commented 5 September 2016

Hej, söker en labbpartner:)

commented 28 October 2016

När kommer labb 4?

Teacher commented 28 October 2016

Labb 4 läggs upp under kommande vecka, förhoppningsvis på måndag 31 oktober. Vi håller på att förbättra Kattisdomaren.

commented 7 December 2016

Frågor angående labbredovisning.

1) Går det att komma in till datorsalarna utan passerkort?

2) Behöver man något speciellt konto för att logga in på datorerna? (Eller räcker det vanliga KTH.SE-kontot som används för webbsidan/Kattis?)

commented 7 December 2016
  1. Nej, men du kan förhoppningsvis beviljas åtkomst om du har ett passerkort och i ett mejl till kortexp@kth.se berättar att du läser kursen. Uppge gärna ditt personnummer och ditt passerkortsnummer för smidigare handläggning.
  2. Man använder uppgifterna för sitt KTH-konto för att logga in på CSC-skolans Ubuntu-datorer.
 
November 2016
Teacher Viggo Kann posted 22 November 2016
 
under HT 2016 adk16

Viggo Kann created page 19 August 2016

Teacher Viggo Kann changed the permissions 19 August 2016

Kan därmed läsas av lärare och ändras av lärare.

Teacher Viggo Kann changed the permissions 16 September 2016

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

Vilken algoritm syftar första teoriuppgiften till? "Jämför tidskomplexiteten för algoritmen då grafen implementeras som en grannmatris och då den implementeras med grannlistor."

Teacher commented 28 September 2016

Albin, det syftar på algoritmen för att hitta bästa bipartita matchningen, vilket man kan förstå av meningen "Uttryck tidskomplexiteten i n och m där n är totala antalet hörn och m antalet kanter i den bipartita grafen."

commented 28 September 2016

Vad är relationen mellan c[u,v] och c[v,u]? I indatan får man t.ex. att c[1,2] = 1, men det står ingenting om c[2,1] för kapaciteten går väl bara åt ett håll.

Teacher commented 28 September 2016

Abdallah, det kan finnas kapaciteter (som är olika) i båda riktningarna mellan två hörn, se föreläsningen eller boken för exempel. Om en kapacitet inte omnämns i indata så är den noll.

commented 30 September 2016

Länken till Unixhäftet funkar inte, skulle det gå att fixa?

Tack på förhand!

Teacher commented 30 September 2016

Johan, jag har uppdaterat länken, men det hjälper inte just nu eftersom det är något fel på själva PDF-dokumentet. Jag har felanmält till IT-avdelningen. Tills vidare kan du kolla på den här sidan.

One user removed his/her comment
commented 25 October 2016

Hej!

I testfallen i Kattis, i del 2 av denna labb - kan flödesgrafens kapaciteter vara större än 1? För att lösa matchningsproblemet i hela labben använder man ju annars bara ett flöde av max 1.

Teacher commented 25 October 2016

Anna-Karin, i flödesgraferna som Kattis testar i del 2 kan kapaciteterna vara större än 1.

commented 27 October 2016

I första slingan i Ford-Fulkersons algoritm, om exempelvis c(1,2) = 16, vad är då c(2,1)? Är den -16? 0?

Teacher commented 27 October 2016

c[1,2] är kapaciteten från hörn 1 till hörn 2. c[2,1] är kapaciteten från hörn 2 till hörn 1. Dessa är oberoende av varandra.

One user removed his/her comment
One user removed his/her comment
commented 2 November 2016

Hur skall man kunna introducera ett flöde mellan kanterna?

Teacher commented 3 November 2016

Jonathan, flödet går längs kanterna i flödesgrafen. I pseudokoden för Ford-Fulkerson ovan ökas flödet längs en kant på den näst sista raden (i den inre for-slingan).

commented 4 November 2016

Vilken tid öppnas queue för labben?

Vissa har seminarium i Vettig mellan 14 och 15 vilket innebär att det skulle vara trevligt att kunna redovisa inom intervallet 13-14. Märkte att kön är stängd (är förvisso ute i kanske lite väl god tid) så tänkte höra när den öppnar?

One user removed his/her comment
Teacher commented 4 November 2016

Patrick, labbkön öppnas cirka kl 11.30 idag. Men på grund av en krockande programmeringstävling så har vi färre handledare än normalt, så redovisningarna måste spridas ut ganska jämnt över hela labbtiden 13-17. Den som har krockande undervisning 14-15 rekommenderas att redovisa efter kl 15 istället.

Sylwester, matchtest ger felutskrifter om beskrivningen av den bipartita grafen inte uppfyller kraven på indata i uppgiftslydelsen: Hörnen numreras från 1 och uppåt. Om man angett a hörn i X och b hörn i Y så låter vi X = {1, 2,..., a} och Y = {a+1, a+2,..., a+b}. Y är alltså den högra partitionen.

 
Feedback News