Nyhetsflöde

It says updated now for Lab 1 here but the dates look wrong to me. Is there going to be a lab session on Feb 12 (Sunday) ?

When can we expect to start on these labs?

You can start to work on the labs but I will make some updates.

Hello the link https://kth.kattis.com/problems/kth%3Aadk%3Aspelling to kattis adk spelling does not work. I'm also unable to register to the course in kattis since it's not listed under current courses in kattis.

Joar: I found this link on kattis: https://kth.kattis.com/problems/kth.adk.spelling 

I will try to get algokomp17 working on Kattis today.

Is there a typo in question 4? I get the feeling that it is supposed to be min(n,m) instead of max(n,m) in the exponent, since there are simple examples that shows that \(2^{max(n,m)}\) is not a lower bound for the time complexity. Or am I misinterpreting something?

Yes I have been wondering this too!

Think like this: Can you find examples where the number of steps is => 2^max(m,n) for certain words.

This I can do, but there seems to be examples where the running time is not at least 2^max(m,n), and does this not mean that the complexity is not Omega(2^max(m,n))? Like the case with one word length 1 and the other is arbitrary m. In my mind, for this special case, the complexity is O(m) (Big O, not Omega). I might of course be misunderstanding the recursion in a bad way.

I believe you need to think of the problem asymptotically, sure there might be counter-examples near the origin, but the rest of the problem space is what defines these complexities. Simple example, x^2 == x^3 for 0, but x^3 is Omega(x^2) for x>=0.

Disclaimer: I am not an assistant or anyone with qualifications, just took an algorithms class for my BSc. and this was the way it made sense to me. Grain of salt etc.

OK, now I understand how I thought about this wrongly :), so nevermind.

Do I interpret the instructions correctly if I understand that tomorrow we are free to come to the lab session to present our answers to the theoretical questions, and presentations are held on a "first-come, first-served" basis such that if you get there after enough people you won't have the opportunity to present at all, and lose out on a bonus point?

On the second lab, it says that it should be solved individually or in pairs. Does this also apply to lab 1? If done in pairs, must both persons write individual answers to the theory questions?

Tomorrow you hand in your solutions to the theory questions (and if I have time I will verify them immediately, otherwise I do that later). You don't need to present the theory solutions, just hand them in, so all of you have the opportunity to hand in the theory questions and get a bonus point. The lab session is mainly for help, so students needing help to solve the lab are prioritized first. If there is time, you can present your lab as well.

Lab 1 can be done in pairs and so also the theory questions.

For the lab session tomorrow, if you need help or want to present, put yourself in the queue at queue.csc.kth.se and click on Algokomp, and write whether you want to present or get help. The computer rooms are gul (https://www.kth.se/places/room/id/daa4b32a-c7a1-4a65-a94f-e918d88a3ab6) and brun (https://www.kth.se/places/room/id/d873230a-c0a9-4395-b32f-0b227d17e26f).

Jonas Haglund (TA).

Do we need to come present our Labs or is it enough to just submit them on Kattis?

You must come and present your lab.

I reported my lab last week, but have not seen any result reported on Rapp. When can I expect the results to be reported?

Hopefully today. Otherwise on Monday.

I have reported your results from lab 1 and the theory questions in rapp (rapp.csc.kth.se), except for a few people that were not registered in rapp (which I have e-mailed).

@Martin Andersson, I didn't find your e-mail address so you have to send me an e-mail when you are registered in rapp so I can report your result.

Is there supposed to be one record? I currently only have Labb 1 (matchning) set, without the teori part or the overall Lab1 part. I did hand in the theory part on the deadline.

To get a bonus point, the solutions must be "reasonably" correct:

"A correct solution of these gives a bonus point on the exam." (http://www.csc.kth.se/~karlan/AoK/Lab_1_ny.html)

If the theory 1 field is blank in rapp (no grade), it is because I didn't accept some answer(s).

I would like to start with lab2, Is it up to date? 

An update has been made in Lab 2. There is a small change in the input format and new links.

The links still gives 404 error, not found.

Corrected now.

In the programming part of lab 2 the instructions for the Kattis problems are unclear. The given instructions only describes what kind of input Kattis will give, it does not state what kind of output Kattis expects. Say for example you are trying to solve the graph coloring problem, does Kattis only want to know whether or not it is possible, i.e. the output of your program should only be Yes/No or True/False? Or perhaps Kattis expects an example of a correct coloring or maybe Kattis expect all possible correct colorings based on a given input, in this case, how should it look?

Also, something that might be confusing for visiting students is the link at the Kattis problems. No matter if you choose the graph coloring problem or the Hamiltonian cycle problem the link will direct you here: https://www.kth.se/social/course/DD1352/subgroup/ht-2016-463/page/labb-4-16/ the instructions are in Swedish, but they are more or less exactly the same as the once found here: https://www.kth.se/social/files/58d135e3f27654100943f6fd/Lab2_17.html, except for one thing, the “Extrauppgift”. The instruction for the “Extrauppgift” states that you are supposed to solve an additional Kattis problem, alone, if you want a higher grade. I suppose that the “Extrauppgift” does not concern us since those instructions belong to a different version of this course, but for someone less familiar with our course system, this is understandably confusing. Please clarify if we can ignore the “Extrauppgift” or not.

the 2 problems to reduce are not in kattis. How should i test my code?

Alexander, the problems do exist in Kattis, here they are:

Graph Coloring: https://kth.kattis.com/problems/kth.adk.npreduction1

Input: An undirected graph and a number of colors m. Isolated vertices and double edges may exist, but no loops.

Question: May the vertices of the graph be colored using at most m colors such that no neighbors have the same color?

Input format: 
Line one: integer V (number of vertices) 

Line two: integer E (number of edges) 
Line three: goal m (max number of colors) 
One line for each of the E edges, consisting of the two endpoints of the edge (the vertices are numbered from 1 to V)

Hamiltonian Cycle: https://kth.kattis.com/problems/kth.adk.npreduction2

Input: A directed graph.

Question: Is there a tour following edges in the graph and beginning and ending in the same vertex, passing each vertex in the graph exactly once?

Input format: 
Line one: integer V (number of vertices) 
Line two: integer E (number of edges ) 
One line for each of the E edges, consisting of the start vertex and end vertex of the edge (the vertices are numbered from 1 to V)

What kind of answer Kattis expects to these problems are not stated though, thus my last post in this thread.

Thank you, I got confused. But my real question is the same as yours stated earlier. What kind of output does kattis expect?

Are there sample inputs and outputs for lab2 as there are in other kattis labs?

I have a question about theory exercise 5. Is the task to show that if we have two such groups of roles, what the minimum number of actors are, given that we can decide completely which actors can play what roles (adhering to the constraints of course)?

I interpret the questions as you do: show that if we have two such groups of roles, what the minimum number of necessary actors is, and where you are completely free to decide which roles each actor can play.

About the theory exercises: Are you supposed to actually turn them in, or just present them?

Hand them in, not present them. You can leave your hand-in in my mailbox close to CSC service center.

Lab 2 says this:

"For technical reasons Kattis has a maximal allowed size of the instances. Kattis will tell you if you send too large an instance. If you can prove the correctness of your reduction you may be examined on the lab even if Kattis has not been able to check it completely."

Does this mean that if we get a "Time Limit Exceeded" error on case 35/38, we can still pass?

No. Time limit exceeded means that your program is too slow and you should fix it. A hint is to think about the number of colors.

Does "For technical reasons Kattis has a maximal allowed size of the instances. Kattis will tell you if you send too large an instance. If you can prove the correctness of your reduction you may be examined on the lab even if Kattis has not been able to check it completely." mean "Output Limit Exceeded"?

I am entirely confused about what the output should be like.

Should we output like the positive instance given on the lab? And what about if the problem is not solvable, meaning has a negative instance?

I am getting wrong answer result from Kattis and I do not know what the exact output structure should be.

Should the output be like:

6 
5 
4
3 1 3 4
2 2 3
2 1 3
1 2
4 1 2 3 4
2 1 4
3 1 2 6
3 2 3 5
3 2 4 6
3 2 3 6
2 1 6 

I appreciate any kind of help. Thank you.

@Jun Yamada: I think so. But I think you should try to optimize your reductions so that this problem does not occur.

@Evren Ergen: You get a graph coloring instance as input and should produce a casting instance as output, such that both are simultaneously positive instances or both are simultaneously negative instances.

I am also getting a time limit exceeded on test case 35/38 . Is it because (1) my reduction algoritm is to slow?  or (2) is it that I am sending to "large Instance" (of the casting problem) and therefore get a time limit exceeded? 

if I send to large instance would i get an explicit error message saying "Output limit exceeded" ? 

I think so. Think about what happens in your reduction if the input graph is small but the number of colors is huge.

When can we present the lab next?

It will be announced later.

Lab 1 är inte inrapporterat i RAPP även fast jag har den godkänd, men lab 2 är inrapporterad. När kan den förväntas vara inrapporterad?

Du måste redovisa labben för att bli godkänd. Maila mig med tider som du kan redovisa.

jag har redan redovisat labben för marcus dicander , jag mailade honom och han mailade i sin tur Karlander , men inget har hänt sen dess.

Skulle du kunna kolla på vad problemet är

Ja.

Alexandr, du har nu ett godkänt resultat i labb 1 i rapp.

If there is no grade near the theory, does that mean we failed? Or does it mean it hasn't been marked yet? I submitted my theory for lab 2 to Jonas on April 7, but there is neither a "P" nor an "F" in rapp.

I have had no time to correct the theory questions for the second lab yet. I will do that sometime next week. I will announce here at KTH social when they are corrected.

I have corrected and reported your answers to the theory questions of Lab 2. If you passed, a P is shown, otherwise the entry is empty.

If you want to present labs you haven't finished you can do that June 7th and 9th in room Grön (https://www.kth.se/places/room/id/8ba067f1-116b-4644-9742-a993a6a28742) between 10:00 and 12:00.

Do we book a time or just show up?

Yes, you should sign up. See: KTH/KURSWEBB/LABBVECKA

How do you sign up? 

I don't know. For me its fine if you just show up, and put yourself in the queue: http://queue.csc.kth.se/#/queue/Algokomp

How is the mean value of the grades rounded? Would for example an A on the master tests and a C on the exam qualify for an A as a final grade? Since, by your conversion, the final grade would be

(5 + 5 + 3)/3 = 4.33 = A or B?

That will give B.

Hi, would it be possible for you to publish more old exams, please?

Observe that in order to get a course grade you must complete all of Mas1, Mas2, Exam and the Labs.

Does it exist more older exams??

@Karlander

Just to be sure.

.33 is rounded down as mentioned above. And .66 rounded up? E.g. 3.66 is rounded up to B?

Yes.

When is the complementary exam, Johan? @Karlander

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

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

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.

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? 

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

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

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? 

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?

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?

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.

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.

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

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?

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

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.

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.

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

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

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.

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

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? 

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

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

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

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

How will the presentations be handled in terms of timing?

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.

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

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?

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

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?

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

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

Yes. I can do that.

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

@Patrik: Yes.

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

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

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

Where is that?

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

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?

Undrar samma som Clarissa!

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

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

Andra dagar.

What format will the presentation have?

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

/Joar

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

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

@Alexandr: Det beror nog på assistenten.

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

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.

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

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

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

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?

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.

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?

Yes more slots will be published.

There are some more times now.

Hello,

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

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

I also need a time to present my solutions

Same here

Where can I find "sal 1523." ?

It is on the 5th floor e building

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

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

When will there be more added time slots?

More time slots are added now.

When will the results be reported to rapp?

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.

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

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

When all students have presented.

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

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

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.

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.

Okej, tack då vet jag!

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

I would count it as O(1).

Ok, thanks for the info!

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.

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.

"(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.

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?

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

Perfect, thanks for the clarification!

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?

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?

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.

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

Yes, it seems to be correct.

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?

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?

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.

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

Thanks.

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

@Poon

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

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.

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?

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

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

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

Will there be any repertoire later at the end of the course?

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

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

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.

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

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

@Karlander

Agreed.

@Karlander

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

You can come to my office.

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

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

När är omästarprovet?

Det kommer att annonseras.

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

Hi, yes.

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

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

When are more time slots coming?

As soon as possible...

Some more time slots are available now.

@Karlander

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

More time slots are available.

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

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!

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.

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

I failed during today's exercise to motivate that all q[b+1][c] have been computed when q[a][b] is computed for the binary string accordion fold problem. I post the motivation here.

profit computes the number of horizontal pairs where indexes b and b+1 are the folding points between a and c.
profit(p[1, ..., n], a, b, c)
    //shortest is the length of the parallel traits.
    if b-a < c-(b+1) then
      shortest := b-a
    else
      shortest := c-(b+1)

    //s is the number of horizontal 1-neighbors.
    s := 0
    for (i := 1; i ≤ shortest; i := i+1)
      if p[b-i]=1 ∧ p[b+1+i]=1 then
          s := s + 1

    return s

//protein_folding computes the maximum number of horizontal 1-pairs not next to each other in p over all possible accordion folds of p.

protein_folding(p[1, ..., n])
    //Step 1.
    for (a := 1; a ≤ n-1; a := a+1)                        //ϴ(n) iterations.
        q[a][n] := 0

    //Step 2.
    for (b := n-1; b ≥ 2; b := b-1)                        //O(n) iterations.
        for (a := 1; a ≤ b-1; a := a+1)                    //O(n) iterations.
            t := 0

            for (c := b+2; c ≤ n; c := c+1)                //O(n) iterations.
                v := profit(p, a, b, c) + q[b+1][c]        //O(n) iterations.
                if v > t then
                    t := v

            q[a][b] := t

    //Step 3.                                            //ϴ(n) iterations.
    max := 0
    for (b := 2; b ≤ n; b := b+1)
        if q[1][b] > max then
            max := q[1][b]

    return max



View q[][] as a square matrix. q[][] is computed by the following steps (marked in the algorithm above):

1. Column n is initialized to zero, except for the bottom element at row n (q[i][i] denote no trait).
2. q[a][b] = MAX(profit(p, a, b, c) + q[b+1][c]), maximized over c, b+2 ≤ c ≤ n.
   1. q is computed column-wise starting from right: b = n - 1 to b = 2 (b goes to 2 since q[a][b], b = 1, is not a trait since a must be less than b).
   2. Each column is computed downwards: a = 1 to a = b - 1 (recall that a must be less than b to form a trait).
   3. When q[a][b] is computed, q[b+1][c] must have been computed, for each c, b + 2 ≤ c ≤ n. Is this the case? Yes, which can be reasoned as follows. Since c ≥ b + 2, and columns are processed from n down to 2, column c has already been processed. When column c was processed, q[a][c] was computed for a, 1 ≤ a ≤ c - 1 (see middle for loop: 1 ≤ a ≤ b - 1), meaning that all entries in column c were computed down to row c - 1. Since c ≥ b + 2, all entries in column c were computed at least down to row c - 1 ≥ b + 2 - 1 = b + 1. Also, the rightmost column n is computed during initialization down to row n - 1. Hence, the entries at row b + 1 for columns c, b + 2 ≤ c ≤ n, q[b+1][c], have been computed when q[a][b] is computed.
3. Check maximum value of q[1][b], for 1 < b ≤ n.

i lecture 5 anteckningarna står det i: subset sum algoritmen

Else If m > a[i] and v[i-1, m-a[i]] = 1

visst måste det vara m >= a[i] ?

Hi, I have a question about homeworks, where can I find them? Thanks

Is this schedule from an earlier version of the course? I assume there won't be a lecture tomorrow 21/1.

Yes, it was an old version. Updated now.