Nyhetsflöde

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

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.

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

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.

Kommer info om tentakomplettering bara man väntar?

Ja. 

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

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

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

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.

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

Mvh
Daniel

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.

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

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.

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.

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.

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

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.

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

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!

När kommer de upp?

Nu!

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

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.

Okej, tackar!

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

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.

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

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

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

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

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

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.

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!

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

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

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!

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?

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.

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.

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

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

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.

På fråga 1.

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

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

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

Alexander T: Ja, annars vore problemet trivialt.

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

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

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.

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.

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.

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.

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

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!

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.

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

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

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

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

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?

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

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? 

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? 

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

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.

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

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

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

Tack så mycket!

Jag lyckas inte hitta var redovisningen håller hus?

Redovisningen 8 januari 2016 blir i Spelhallen.

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?

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.

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?

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