Till KTH:s startsida Till KTH:s startsida

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?

Anmäl missbruk
Lärare kommenterade 17 februari 2015

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

Anmäl missbruk
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?

Anmäl missbruk
Lärare kommenterade 23 februari 2015

It is on floor 4 at the CSC expedition.

Anmäl missbruk
kommenterade 23 februari 2015

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

Anmäl missbruk
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

Anmäl missbruk
En person gillar kommentaren
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)?

Anmäl missbruk
En person gillar kommentaren
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."?

Anmäl missbruk
kommenterade 27 april 2015

When will the Mästarprov 2 presentations be? 

Anmäl missbruk