Till KTH:s startsida Till KTH:s startsida

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

Mer information och instruktioner hittar du i nyheten: Gruppwebben som samarbetsyta stängs 1 oktober 2026.

Mästarprov

The first set of problems (Mas 1) will be published Feb 12. They should be handed in Feb 26 (latest

Lärare Johan Karlander skapade sidan 31 januari 2016

Johan Karlander flyttade sidan från Algoritmer och komplexitet (DD2352) 31 januari 2016

kommenterade 13 februari 2016

When should we present Mas 1 orally?

Anmäl missbruk
kommenterade 15 februari 2016

Regarding task 2: Can we assume that the receivers are sinks in the graph and no flow can pass through them?

Anmäl missbruk
kommenterade 16 februari 2016

Also regarding task 2: Can make any assumptions wether the graph is directed or not?

Anmäl missbruk
Lärare kommenterade 16 februari 2016

You can assume that it is directed. (It really doesn't matter that much, as far as I can see.)

Anmäl missbruk
Lärare kommenterade 16 februari 2016

The question about the receivers I am not sure if I should answer. It depends on how you solve the problem.

Anmäl missbruk
kommenterade 16 februari 2016

Okey, so there could be flow leaving the receivers?

Anmäl missbruk
Lärare kommenterade 16 februari 2016

Maybe you want to reconstruct the flow problem. Then maybe...

Anmäl missbruk
kommenterade 16 februari 2016

I'm sorry I do not understand. Let me rephrase my question. Can we assume that the graph given in task 2, there is no flow leaving the receivers. In other words, are all edges connected to a given receiver directed towards it?

Anmäl missbruk
Lärare kommenterade 16 februari 2016

In the graph given there is no flow at all, that is for you to construct. But, to make things simple we can assume that the receivers only have inflow edges. (In a way, this is not quite necessary but it makes things easier.)

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 21 februari 2016

For Mästarprov question 3, are the figures supposed to be consecutive or is any sub-sequence of figures that satisfy the property given in the question OK? 

Anmäl missbruk
kommenterade 22 februari 2016

Is there a deadline for the oral part of MAS1?  I'm unable to find it, and a bit worried that the deadline is during next week when there is "sportlov".

Anmäl missbruk
Lärare kommenterade 24 februari 2016

I will present a schedule for booking times soon.

Anmäl missbruk
kommenterade 24 februari 2016

By "mailbox" do you mean sending the solutions to miksa@kth.se or do you mean some physical mailbox? Myself and others will not be able to hand in a physical copy this Friday.

Anmäl missbruk
kommenterade 24 februari 2016

Mästarprov task 2: Is the symbol v different for every node? I.e. does every receiver node v have its own potentially distinct flow demand d_v and every non-reciever node v have a potentially distinct flow limit a_v? Or are all a_v equal and all d_v equal?

Anmäl missbruk
kommenterade 24 februari 2016

MAS1 task1: This might be a pretty dumb question to ask... The problem states "We are allowed to split studies on several different days". Does that mean that any combination of subjects is valid given as long as the deadlines are met? (I think so, I only want to make sure I am not misunderstanding anything and taking "shortcuts" by making the problem too easy...)

Given for example:

K=2 and N=3, and two subjects M(aths) and E(english) and \(t_M = 3\), \(t_E = 2\), \(d_M= d_E = 3\)

All of the following schedules would be valid answers, right?

Schedule 1 Hour 1 Hour 2 Schedule 2 Hour 1 Hour 2 Schedule 3 Hour 1 Hour 2
Day 1 Math Math Day 1 Math English Day 1 English English
Day 2 Math English Day 2 Math English Day 2 Math Math
Day 3 English Day 3 Math Day 3 Math

Anmäl missbruk
kommenterade 25 februari 2016

MAS1 task2: From the problem description it seems that the graph should be interpreted as undirected. Is this correct?

Anmäl missbruk
kommenterade 13 april 2016

Hi!

Question about MP2 task 1:

Can a column be empty and still be part of a winning position?

Anmäl missbruk
Lärare kommenterade 13 april 2016

Yes, it is possible.

Anmäl missbruk
kommenterade 13 april 2016

Ok, thank you!

Anmäl missbruk
kommenterade 14 april 2016

Can we assume that it is an instance of subset sum with only positive integers?

Anmäl missbruk
Lärare kommenterade 15 april 2016

Yes, you can.

Anmäl missbruk
kommenterade 18 april 2016

In the description of MAS2 it says that MAS1 is mandatory, but nothing about MAS2. Does this mean that MAS2 is not mandatory?

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 18 april 2016

In question 3, does group membership say anything about the connectivity among the members of the group (connected, fully connected)?

Anmäl missbruk
kommenterade 19 april 2016

It seems probable that the vertices in a group are connected but, as far as I can see, connectedness isn't part of the problem (nor of the solution).

Anmäl missbruk
Lärare kommenterade 22 april 2016

I agree.

Anmäl missbruk
Lärare kommenterade 22 april 2016

To answer a previous question: Yes, MAS 2 is mandatory.

Anmäl missbruk
kommenterade 22 april 2016

Where exactly are the mailboxes where MAS 2 should be handed in on monday?

Anmäl missbruk
kommenterade 24 april 2016

I believe they're in the CSC Reception office in E. The office closes at 4pm though.

Anmäl missbruk
Lärare kommenterade 21 april 2017

From 16.00 you can come to my office 1523 and give me your mästarprov.

Anmäl missbruk