Nyhetsflöde

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

^

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

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?

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

@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 ;)

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.

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

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

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

Tack på förhand :)

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

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.

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!

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.

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?

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.

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? 

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.

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

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.

Hej, 

Var bokar man sig för att munta? 

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

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

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.

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

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?

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.

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?

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.

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?

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.

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.

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.

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?

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

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

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.

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

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.

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.

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? 

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

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.

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

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.

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?

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.

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å?

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.

Vilken länk bokar man mästarprovet?

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

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.

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

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

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

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å?

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? 

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? 

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!

På fråga 3, Konstruktion av Schema

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

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

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

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

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

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

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?

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?

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.

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

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.

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

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

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?

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

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

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")?

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.

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?

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.

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.

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.

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?

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

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? 

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

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

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

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?

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.

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

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

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? 

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.

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?

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

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?

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

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!

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.

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

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.

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

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.

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.

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

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?

Sara, jag håller med om din tolkning.

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?

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.

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!

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?

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.

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

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

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?

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.

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

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: 

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

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.

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

• 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?

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

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

/ Alfrida

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

Ä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?

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.

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

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

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.

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.

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!

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

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.

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?

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.

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?

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

Hej, söker en labbpartner:)

När kommer labb 4?

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

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

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.

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

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

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.

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.

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

Tack på förhand!

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.

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.

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

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

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.

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

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

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?

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.