Till KTH:s startsida Till KTH:s startsida

Gruppwebben som samarbetsyta stängs 1 oktober 2026. Du som administratör behöver nu exportera gruppens innehåll och/eller radera gruppen.

Observera: Från och med den 1 oktober 2026 kommer delar av gruppwebben som inte längre används, successivt att stängas ned, exempelvis gruppwebbar som redan har flyttats eller varit inaktiva under en längre tid.

Mer information hittar du i nyheten: Gruppwebben och Social stänger den 1 oktober 2026. Stöd och instruktioner för hur du exporterar en gruppwebb finns i: Gruppwebben som samarbetsyta stängs 1 oktober 2026..

Mästarprov

Lärare Johan Karlander skapade sidan 9 februari 2015

Johan Karlander flyttade sidan från Algoritmer och komplexitet (DD2352) 9 februari 2015

kommenterade 17 februari 2015

I have a question about mas1 question 3.

Do we only count the positive flow (X to Y) of the cut or can we subtract flow entering X. 

Example: a cut consists of X -> 3 -> Y and X -> 2 -> Y and Y -> 1 -> X 

Is the value of the cut 3 + 2 = 5 or is the value of the cut 3 + 2 - 1 = 4?

Lärare kommenterade 17 februari 2015

The capacity of the cut is 5. You can read about this in the lecture notes.

kommenterade 22 februari 2015

I have a question about where the peronal mailbox of Johan is located. Is it on Osquars backe 2, floor 5?

Lärare kommenterade 23 februari 2015

It is on floor 4 at the CSC expedition.

kommenterade 23 februari 2015

The expedition closed at 16 but i take it that the CSC mailbox will suffice?

En användare har tagit bort sin kommentar
kommenterade 30 mars 2015

When are we going to be given Mästarprov 2 and the second laboration assignments? I am afraid it has already been handed out but that I haven't found it. /Ola

kommenterade 22 april 2015

I have a question regarding mästarprov 2 task 4, "Finding vertex covers". The task states that "...we have an algorithm F such that it, given a graph G, computes the size of a minimal vertex cover of G." and that "... the time-complexity of F is T(n) where n is the size of the input...". Since no specifics are given regarding F, does this mean that our algorithm F' should work for any algorithm F which computes the size of a minimal vertex cover of G in time T(n)?

kommenterade 22 april 2015

Perhaps with "...we have an algorithm F such that it, given a graph G, computes the size of a minimal vertex cover of G." you meant "...we have an algorithm F such that it, given a graph G, computes the size of a minimum vertex cover of G."?

kommenterade 27 april 2015

When will the Mästarprov 2 presentations be?