Till KTH:s startsida Till KTH:s startsida

Mästarprov

Mästarprov 1

Mästarprov 2

Here you can book a time slot.

Tryck här för att hämta bokningslistor:

Johan Karlander skapade sidan 9 januari 2017

kommenterade 25 januari 2017

Hej Johan! Tidigare stod det att MAS 1 skulle publiceras den 12 feb och lämnas in senast 26 feb. Går det att byta tillbaka/skjuta upp aktuell publiceringsdatum,  så att man för lite mer tid på att lära sig kurmaterialet innan MAS 1? Mvh, Sohof

En användare har tagit bort sin kommentar
Lärare kommenterade 8 februari 2017

Jag tror det är bäst att hålla fast vid planen 8 feb - 22 feb.

kommenterade 9 februari 2017

On problem 2, if x_{k-1}, x_k is not a flat sequence, do we consider FL(k) to be 1 or 0? I would assume 0, but it seems to be easier to formulate the recursion if we call it 1.

kommenterade 13 februari 2017

Hej.

Finns det någon enkel talföljd till hands för problem 2 i mästarprov 1 som man kan använda sig av till testning? 

Lärare kommenterade 13 februari 2017

Det borde vara ganska enkelt att tänka ut en sådan själv tycker jag.

Lärare kommenterade 13 februari 2017

A sequence of length 1 can be considered flat (by definition).

kommenterade 16 februari 2017

Kan man inte maila in Mästerprovet via mail? om inte, skall vi bara skriva ner vårat "program" till uppgift 2 - i mitt  fall - i en PDF fil? 

kommenterade 17 februari 2017

On problem 2, we have only defined flat sequences beginning at 1. I assume that we are free to generalize this definition to a sequence x_i, ..., x_j by changing the range of s and k, right?

kommenterade 17 februari 2017

Vad menas med program i formuleringen "When you have stated your algorithm, write a program that solves the problem in dynamic programming-style"?

Ska vi skriva fungerande kod eller pseudokod och hur noggrant beskrivet ska det vara?

En användare har tagit bort sin kommentar
Assistent kommenterade 18 februari 2017

Jag skulle tro att det menas med att ni endast ska skriva pseudokod. Jag kan dock inte svära på det då jag inte pratat med Johan om det. Rent generellt så ska det vara så pass detaljerat att man kan analysera tidskomplexiteten. Som beskrivet i lösningarna till övningarna (https://www.kth.se/social/course/DD2352/subgroup/vt-2017-277/page/exercises-65/) eller i boken.

Assistent kommenterade 18 februari 2017

You are given a sequence x = x1, ..., xn. Your task is to find a recursion formula FL(k) that gives the length of the longest (sub)sequence ending at xk and that is flat. For instance, xi, ..., xk, where 1 ≤ i ≤ k is (sub)sequence ending at xk. This (sub)sequence can be renamed as xi, ..., xk = y1, ..., ym = y. In the problem definition it is stated what requirements the (sub)sequence y must satisfy in order to be considered as flat: For all k, s such that 1 ≤ k ≤ m and 1 ≤ s < k, we have 0 < (yk − ys)/(k − s) < 1.

kommenterade 18 februari 2017

I uppgift 2, är det krav på att funktionen FL endast har en indata FL(k) eller kan man modifiera det till en funktion av 2 variabler? ex. FL(a,b).

kommenterade 18 februari 2017

What happens when k = 1, what will s be? Shouldnt it be so that k can only be 2 ≤ k ≤ n? 
If k comes down to 1, should x1 be included in the subsequence?

Assistent kommenterade 18 februari 2017

@Alexander Silasson: Indata till FL ska vara endast en variabel k. FL(k) ska då ge längsta sekvensen som är "flat" som slutar i xk.

@Clarissa Hedenqvist: Consider the definition of a flat sequence: A sequence x1, ..., xn is flat, if for all k and s, where 1 ≤ k ≤ n and 1 ≤ s < k, then 0 < (xk − xs)/(k − s) < 1 holds. What happens with the part 1 ≤ s < k in the if-condition ("for all k and s, where 1 ≤ k ≤ n and 1 ≤ s < k") when k = 1? What must the sequence satisfy if the if-condition is true? What must the sequence satisfy if the if-condition is false?

The answers to these questions also support Johan's comment above: "A sequence of length 1 can be considered flat (by definition)."

Assistent kommenterade 18 februari 2017

Just to be clear. Before the problem definitions, it is stated that for all problems you should give an analysis of the time complexity of your algorithm and be able to argue for the correctness of the algorithm.

Don't forget this.

kommenterade 18 februari 2017
Is it ok for us to use someone else's implementation of an algorithm as long as we source it and describe why we used this particular algorithm?
Assistent kommenterade 18 februari 2017

Since that is not stated in the instructions, and I have not spoken to Johan about it, I don't know. But it seems very reasonable that you are allowed to do so. My guess is that it is ok, but to be on the safe side you better ask Johan.

Lärare kommenterade 19 februari 2017

I am not sure what you mean. You cannot take another student's solution, if that is what you mean. 

En användare har tagit bort sin kommentar
kommenterade 19 februari 2017

@Johan, Jonas

I assume it's okay to use known theorems already proven in the course book by just referring to them? 

If you use a known data structure, is it okay to use them without showing their inner-workings? Suppose I want to use a stack, then I should not need to state everything that goes into implementing one, right? In addition, since it's a know data structure, their calls have known time-complexity which is okay to use in time-complexity analysis?

Lärare kommenterade 19 februari 2017

Yes, it is ok to use known tjeorems and data structures as long as you can refer to the course book or some other source.

En användare har tagit bort sin kommentar
kommenterade 20 februari 2017

In the last problem, it says the algorithm must be polynomial in n, m, k. Does it mean the time complexity?

kommenterade 20 februari 2017

In the assignment document,  it says that the assignment should be presented orally. However, I couldn't find any schedule for time slots. Did I misunderstand something? 

Assistent kommenterade 20 februari 2017

@Jun: There are time slots allocated at February 27th and 28th for master test presentations (https://www.kth.se/social/course/DD2352/calendar/).

@Yutong: Yes, it is the time complexity.

kommenterade 20 februari 2017

In case you cannot be present during those slots, will there be another allotted timeslot?

kommenterade 20 februari 2017

Regarding presentations, are we supposed to book times for this somewhere? 

kommenterade 20 februari 2017

I uppgift 3, behöver man skriva pseudokod eller räcker en detaljerad beskrivning av algoritmen?

kommenterade 20 februari 2017

How will the presentations be handled in terms of timing?

kommenterade 20 februari 2017

In the question 2, if the sequence a,b,c,d is flat;

1) Does this mean only d and c, d and b, d and a satisfy the formula? or

2) Should  d and c, d and b, d and a / c and b, c and a / b and a satisfy the formula also?

I am confused about the definition of "flat" by those reasons.

En användare har tagit bort sin kommentar
kommenterade 20 februari 2017

In question 4, what is considered a polynomial time-complexity in \(n,m,k\)?

Is for example \(\mathcal{O}(k^{z_1}m^{z_2}n^{z_3})\) polynomial time complexity, where \(z_1, z_2, z_3 \in \mathbb{N}_0\)?

kommenterade 21 februari 2017

I have 2 questions:

1. On 22th of Feb, where we have to hand in the Homework 1? Is it possible to send it via email?

2. Should we select time slot for presentation on 27 or 28th?

Assistent kommenterade 21 februari 2017

Regarding the schedule for the master test presentations, I think more information will be given by Johan. So wait for a little while and see what happens.

Also, during the master test presentations make sure that you can describe your algorithms properly and motivate its correctness and time complexity in detail. So you can convince us that what you have done is correct.

@Alexander: Pseudocode can contain sentences. For instance

Dijkstra’s Algorithm (G, l)
Initially S = {s} and d(s) = 0
While S = V
    Select a node v ∈ S with at least one edge from S for which d(v) = min e=(u, v):u∈S d(u) + l_e is as small as possible
    Add v to S and define d(v) = d'(v)
EndWhile

@Hesam: It means that n, m nor k shall appear as an exponent. So yes, k^z1 · m^z2 · n^z3 is a polynomial in n, m and k.

@Elaheh: You can send it via e-mail if you can't come and hand it in (that is, if you have a good reason to not come here and hand it in; it is written in the instructions of the Mästarprov 1 where you can hand it in).

kommenterade 21 februari 2017

There does not seem to be a mailbox for Algorithms and Complexity. Are we supposed to submit the reports in the box labelled ADK instead, or do you want them in your personal mailboxes?

Assistent kommenterade 21 februari 2017

You can put it in my or Johan's mailbox.

kommenterade 21 februari 2017

Will you check the "ADK mästarprov" box as well? I left my report there.

Assistent kommenterade 21 februari 2017

Yes. I can do that.

kommenterade 21 februari 2017

On problem 4, does the train always stop at station \(s_0\) and \(s_n\), regardless of the choice of \(h_1, \ldots, h_k\)?

Assistent kommenterade 21 februari 2017

@Patrik: Yes.

kommenterade 22 februari 2017

Where is the ADK mailbox exactly? In E huset? Which level? 

kommenterade 22 februari 2017

@Hesam I think it's the 4th floor in the E-building! :) 

Lärare kommenterade 22 februari 2017

The CSC-expedition is closed now. You can find me in room 1523 if you want to hand in Mas 1.

kommenterade 22 februari 2017

Where is that?

Assistent kommenterade 22 februari 2017

Floor 5 between the D and E buildings: https://www.kth.se/places/room/id/dc4c9b61-26f9-4c81-80a8-dda27fcc2155?l=en

kommenterade 24 februari 2017

Alla tider för att redovisa mästarprovet är bokade. Det är långt ifrån alla som har fått en plats.

När släpps nya tider?

kommenterade 24 februari 2017

Undrar samma som Clarissa!

Assistent kommenterade 24 februari 2017

Alla kommer få redovisa. Det kommer komma upp nya tider fram tills dess att alla har fått redovisa. Kolla lite då och då.

kommenterade 24 februari 2017

Kommer dessa tider också vara på måndag eller tisdag? Eller andra dagar? 

Assistent kommenterade 24 februari 2017

Andra dagar.

kommenterade 24 februari 2017

What format will the presentation have?

Should we prepare power-point slides or will you just ask us questions we should answer?

/Joar

kommenterade 24 februari 2017

Får man veta om uppgifterna som man har lämnat in  godkända innan man gör en muntlig redovisning ?(jag antar att det är så)  isåfall får man ett besked per mail eller liknande vilka uppgifter man har blivit godkänd på?

Assistent kommenterade 24 februari 2017

@Joar: We just ask you some questions. Don't prepare any slides.

@Alexandr: Det beror nog på assistenten.

kommenterade 24 februari 2017

Apparently all the time slots to present Mästarprov 1 are full. Will you publish new slots?

Lärare kommenterade 24 februari 2017

We are right now trying ti recruit some more assistents. There will probably be some more time slots at the end of next week. As Jonas said, evereryone will get a chance to present solutions. Hopefully, the situation will get clearer this weekend.

Assistent kommenterade 24 februari 2017

Yes, there will be additional slots. New slots will show up as soon as we know when assistants are available.

kommenterade 26 februari 2017

Where can I find information on where we are supposed to do the presentations? I have a time slot tomorrow.

Assistent kommenterade 26 februari 2017

It is written in the booking list next to the time information.

kommenterade 26 februari 2017

Is it ok to assume that we can show up in any of these 2 rooms, or it has to be a specific one ? 

Also, are we going to get any feedback before the examination?

Assistent kommenterade 26 februari 2017

No, you must go the room that is associated to the booking list you signed up on. No, you will not get any feedback before the examination.

kommenterade 26 februari 2017

now it shows that all the time slots to present Mästarprov 1 are full, and I'm a little bit nervous about that, will more slots will be published?

Assistent kommenterade 26 februari 2017

Yes more slots will be published.

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
Lärare kommenterade 27 februari 2017

There are some more times now.

kommenterade 28 februari 2017

Hello,

they are full again. Can you add some more, please?

Assistent kommenterade 28 februari 2017

We will add more slots as soon we found more TAs.

kommenterade 28 februari 2017

I also need a time to present my solutions

kommenterade 28 februari 2017

Same here

kommenterade 28 februari 2017

Where can I find "sal 1523." ?

kommenterade 28 februari 2017

It is on the 5th floor e building

kommenterade 28 februari 2017

Hello, all the time slots are full. Can you please add some more?

Assistent kommenterade 28 februari 2017

More time slots will be added when we have found more TAs. Everybody will get a chance to present. It will be announced.

kommenterade 9 mars 2017

When will there be more added time slots?

Lärare kommenterade 10 mars 2017

More time slots are added now.

kommenterade 17 mars 2017

When will the results be reported to rapp?

En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
Assistent kommenterade 27 mars 2017

Those of you who have not presented your master test can contact me via e-mail (which you can find by clicking on my name) and we can arrange a time for your presentation. I am available at the following times:

  • Tuesday March 28: 11:00-14:00
  • Wednesday March 29: 10:00-12:00 and 15:00-16:00
  • Thursday March 30: 10:00-12:00
  • Friday March 31: 10:00-14:00.
Assistent kommenterade 3 april 2017

Still some students haven't presented their master tests. Send me an e-mail when you would like to present. The sooner the better.

kommenterade 3 april 2017

when will you rapportera in resultatet för master tests to rapp? 

Assistent kommenterade 3 april 2017

When all students have presented.

kommenterade 7 april 2017

har ni glömt att publicera MP2 ?eller är det jag som har missat att den ligger ute någonstans?

Assistent kommenterade 7 april 2017

7:e april är inte över än... ;)

En användare har tagit bort sin kommentar
kommenterade 10 april 2017

Hej! Vilken formulering av "the CLIQUE problem" ska man använda i fråga 1 Mas2? Som jag förstått det spelar det en stor roll då man ibland ska anta vissa egenskaper hos de "cliques" som eftersöks.

Lärare kommenterade 10 april 2017

Tycker inte att det kan tolkas på mer än ett sätt. Det som avses är beslutsproblemet att givet G och K, avgöra om G har en klick/clique (komplett delgraf) av storlek K eller inte.

kommenterade 10 april 2017

Okej, tack då vet jag!

kommenterade 10 april 2017

If we are given a graph G=(V,E) and we do the assignment some_variable := |V|, should we count the time complexity of this operation as O(1) or e.g. O(log |V|)?

Assistent kommenterade 10 april 2017

I would count it as O(1).

kommenterade 10 april 2017

Ok, thanks for the info!

En användare har tagit bort sin kommentar
Assistent kommenterade 10 april 2017

My feeling is that you need to read up on this topic. I think you should find the relevant material in the course book yourself.

kommenterade 12 april 2017

In the super connector problem, did you mean that a group of super connectors are all adjacent to each other? Because in the current formulation it is enough that they are connected to each other, which I am fairly sure is not what you meant. Otherwise I would be able to prove that P=NP if I manage to prove that the problem (according to it's current formulation) is NP-complete.

Assistent kommenterade 12 april 2017

"(Connections are edges in the network.) A group S of super connectors is a set of super connectors all connected to each other."

I interpret adjacent as connected.

kommenterade 12 april 2017

Adjacent nodes are connected, but connected nodes are not necessarily adjacent. Do you say it's okay to interpret the problem so that the group of super connectors only counts as a group if they are adjacent?

Assistent kommenterade 12 april 2017

I interpret the problem as: A group of super connectors is a group of super connectors that are all adjacent to each other.

kommenterade 12 april 2017

Perfect, thanks for the clarification!

kommenterade 12 april 2017

On question 4 of the second mastarprov, what is meant by limited number of calls? (especially in regards to PathFinder) Likewise, what does the number of computations made as small as possible mean? Is it not enough to simply solve the problem in proper complexity?

kommenterade 14 april 2017

Q2. You write in the problem description that "[i]t is easy to see that FOURPARTITE MATCHING is in NP". Does this mean that we can skip to formally show that FOURPARITE MATCHING is in NP, or do you still want this for the solution?

kommenterade 14 april 2017

Q4. Are we allowed to use any data structure for our graph representation as long as they are explained? I ask because I get slightly different answers depending on the data structure I use.

En användare har tagit bort sin kommentar
kommenterade 16 april 2017

Q3. I have a question about what a winning strategy for A is.

Let \(A = \{1,1\}\) and \(B = \{4,4\}\). Then player A can make them the sums \(-2,0,2\) while B can make the sums \(-8, 0, 8\). Now a winning strategy for \(A\) is the assignment \(1 + 1\) since no matter how \(B\) chooses signs the sum \(-2\) cannot be attained and so \(B\) cannot make the the TOTAL sum to be 0.

However, in the case \(A = B = \{1,1\}\) there exists NO winning strategy for A. Since for each sum \(A\) can get, \(B\) has an assignment of signs such that B's sum equals A's sum. 

Is this a correct interpretation of 'a winning strategy for A'?

Lärare kommenterade 17 april 2017

Yes, it seems to be correct.

kommenterade 17 april 2017

I have some questions about the formulation of problem 4.

Could you elaborate on your definition of the complexity T?

Since you use G both for the graph given in the problem and "any" graph when defining PathFinder it is unclear to me whether T(|V|, |E|) is a function of the number of edges and nodes of the graph simply given to PathFinder, or if it's the maximum complexity only when calling PathFInder on G given in the problem.

In the first case, do we know anything about the nature of T? Would it for example be alright to assume it is an increasing function of |V| and/or |E|?

In the second case, do we know anything about the complexity of PathFinder for other graphs than G given in the problem?

kommenterade 19 april 2017

I'm in the same situation as Ryan and will reask his question:

On question 4 of the second mastarprov, what is meant by limited number of calls? (especially in regards to PathFinder) Likewise, what does the number of computations made as small as possible mean?

Is it not enough to simply solve the problem in proper complexity?

kommenterade 19 april 2017

For question 4 I was wondering if the given edges in the graph are weighted or not. Meaning, I was wondering if the longest path is the path that contains as many edges as possible? Or is it the path that has a set of edges with biggest weights in total?

Thanks for the help.

kommenterade 19 april 2017

Since 0<K<|V| is mentioned in the problem description, I think it is safe to assume they are not weighted.

kommenterade 19 april 2017

Thanks.

kommenterade 19 april 2017

what is the notation p(|V|,|E|) stand for in the problem description for question 4? tack

kommenterade 20 april 2017

@Poon

I think they mean a polynomial with variables |V| or/and |E|.

Lärare kommenterade 20 april 2017

What I mean in problem 4 is that your algorithm has to make calls to the "unknown" algorithm which has a complexity T(G). We can assume that T is large and groves with the size of G. It could happen that some extra work that does not invove T occurs so that the complexity had form q + pT where q,p is polynomial. The important thing is that p and q should be as small as possible.

kommenterade 20 april 2017

You haven't yet answered Hesam's comment from 6 days ago, and I was wondering the same so I'll ask it again here:

Q2. You write in the problem description that "[i]t is easy to see that FOURPARTITE MATCHING is in NP". Does this mean that we can skip to formally show that FOURPARITE MATCHING is in NP, or do you still want this for the solution?

Lärare kommenterade 20 april 2017

No, you don't have to do that. It is easy, though.

kommenterade 20 april 2017

I don't understand why we need to make calls to the PathFinder algorithm, can't we just solve the problem without it?

kommenterade 20 april 2017

Also, is there a starting point? Or is it just the longest path starting from any node?

En användare har tagit bort sin kommentar
kommenterade 20 april 2017
Will there be any repertoire later at the end of the course?
kommenterade 20 april 2017

Eller omästarprov i slutet av kursen för de som har missat?

Lärare kommenterade 20 april 2017

There will be an extra Mas at the end of the course for those who have failed the previous ones. It will give grade E (at most).

Lärare kommenterade 20 april 2017

About problem 3. It is probably easier than you think. Look at very special types of inputs. Think about it from player B:s perspective.

kommenterade 21 april 2017

@Karlander

Q3. If we are to think from the perspective of player B, do you agree that it would've made more sense to ask whether or not B has a winning strategy? 

Lärare kommenterade 21 april 2017

Player B has a winning strategy if and only if A has not.

kommenterade 21 april 2017

@Karlander

Agreed.

kommenterade 21 april 2017

@Karlander

Are you at your office? Or should I put in the CSC mailbox?

Lärare kommenterade 21 april 2017

You can come to my office.

kommenterade 21 april 2017

Will there be any more time slots for the MAS2 presentations, all seem to be booked now?

Assistent kommenterade 22 april 2017

Yes. There will at least be times during week 18 (2-5 of May).

kommenterade 24 april 2017

När är omästarprovet?

Assistent kommenterade 25 april 2017

Det kommer att annonseras.

kommenterade 25 april 2017

Hi, will there also be time slots for presentation during the week of May 9th (week after next week)?t ack så mycket

Assistent kommenterade 25 april 2017

Hi, yes.

kommenterade 4 maj 2017

at what address is the mästarprov-examinations held. if you search at the KTH room-search webpage there are two addresses given for the room 1523..

kommenterade 4 maj 2017

It's the one on the 5th floor in the E building.

kommenterade 4 maj 2017

When are more time slots coming?

Assistent kommenterade 4 maj 2017

As soon as possible...

Lärare kommenterade 4 maj 2017

Some more time slots are available now.

kommenterade 5 maj 2017

@Karlander

Is there a probable time frame for the extra MAS's hand-in and presentation?

Lärare kommenterade 7 maj 2017

More time slots are available.

kommenterade 7 maj 2017

@Karlander

Me, as well as some other students, never got our MAS1 grade reported to Rapp, but we have now received the grade for MAS2. When are the grades for MAS1 coming? 

kommenterade 13 maj 2017

Hi! I was wondering where can I access the solutions to these previous Mästarprov 1 and 2 ? 

Wanted to go through them before the exam. Thanks!

Assistent kommenterade 14 maj 2017

Hello. They are not published. But an old exam can be found here: http://www.csc.kth.se/utbildning/kth/kurser/DD2352/algokomp13/T-120531.pdf.

kommenterade 22 maj 2017

When can you expect the result from MAS2 (the first deadline) to be reported in Ladok? (I´m originally enrolled in the DD1352 course)