Till KTH:s startsida Till KTH:s startsida

Laboratory work

This page will be updated soon

Each lab assignment consists of a set of theory excercises and a programming assignment. If they are done in time they will give give one bonus credit each to the written exam. Thus you can get up to 4 bonus credits.

Lab 1 (Updated now)

Lab 2

Johan Karlander skapade sidan 11 januari 2016

kommenterade 27 januari 2016

When will the first lab be published?

Anmäl missbruk
Lärare kommenterade 27 januari 2016

Probably at the end of this week.

Anmäl missbruk
Lärare kommenterade 29 januari 2016

Lab 1 is now published.

Anmäl missbruk
kommenterade 31 januari 2016

Hi,

Are the labs supposed to be done individually or are we allowed to talk about solutions with other students?

Anmäl missbruk
Lärare kommenterade 31 januari 2016

You can do them in groups of two. The answers to the theory questions should be written individually and given to the lab assistent. Except from working two and two on the code, you should not collaborate.

Anmäl missbruk
kommenterade 2 februari 2016

Hi,

Some of the links in the document is not working. I also think some of the information might be outdated. For example it says algokomp14. 

Anmäl missbruk
Lärare kommenterade 3 februari 2016

I have made an update now.

Anmäl missbruk
kommenterade 4 februari 2016

I still can't find algokomp16 on Kattis though...? (the only course offering listed is algokomp15)

Anmäl missbruk
Lärare kommenterade 4 februari 2016

Should be fixed now.

Anmäl missbruk
kommenterade 8 februari 2016

Just for clarification, are the theory questions worth 1 point and submitting a working solution to kattis worth 1 point as well? So it is possible to earn 2 points total in lab 1?

Anmäl missbruk
Lärare kommenterade 8 februari 2016

Yes, that is correct. But it is not enough just to submit your solution to kattis. You have to present it to a lab assistent.

Anmäl missbruk
Lärare kommenterade 8 februari 2016

The first lab should be done in Java. I think I have said something else before but this is what is stated in the problem formulation. More precise, you should modify an existing Java program and make algorithmic improvements. Here are some more comments (in Swedish):

Anledningen till att Java krävs i labb 1 är att uppgiften handlar om att
snabba upp ett existerande Javaprogram med algoritmiska förbättringar. Att
skriva om hela programmet i ett snabbare språk tränar inte samma
färdigheter och skymmer de algoritmiska skillnaderna mellan programmen,
vilket kan göra redovisningen svårare. Dessutom kan man nog undvika att
göra någon av de algoritmiska förbättringarna om man skriver om
programmet i C++.

Anmäl missbruk
kommenterade 9 februari 2016

OK Got it,

Follow up question - Are the theory questions due on the 12th and the programming due on the 19th? Or can they both be presented on the 19th?

Anmäl missbruk
Lärare kommenterade 10 februari 2016

If the assistents have time, you can present them both on Feb 12th.

Anmäl missbruk
kommenterade 10 februari 2016

But is it possible to present the theory questions as well on the 19th and still get the bonus point? It is a bit unclear.

Anmäl missbruk
Lärare kommenterade 10 februari 2016

No you have to present them on the 12th.

Anmäl missbruk
kommenterade 10 februari 2016

ok thanks :)

Anmäl missbruk
kommenterade 11 februari 2016

Question 6 states "Show with pseudocode how the recursion can be calculated by using dynamic programming, ie how a matrix M can be created." (emphasis mine). However, on one exercise session it was claimed that part of the definition of dynamic programming is that it is iterative rather than recursive. What is the task really?

Anmäl missbruk
Lärare kommenterade 11 februari 2016

The idea with dynamic programming is that we have a recursion formula (the recursion referred to above) and with the help of this formula we can iteratively compute "later" values in terms of "earlier" values. So there is no contradiction here.

Anmäl missbruk
kommenterade 12 februari 2016

Are you going to extend the deadline for the theory part of lab1? Qwait is not open and there's more than 40 people that written their names on the white board queue with just one assistant here.

Anmäl missbruk
Lärare kommenterade 12 februari 2016

Anytime today is ok.

Anmäl missbruk
kommenterade 19 februari 2016

Are there going to be any more lab sessions than the two after the one today? I feel that it could be problematic if you get stuck since there is very little time to get assistance.

Anmäl missbruk
kommenterade 21 mars 2016

In laboration 1 the theory questions was optionally, is it the same on laboration 2?

Anmäl missbruk
Lärare kommenterade 21 mars 2016

Yes!

Anmäl missbruk
kommenterade 22 mars 2016

In lab2: "No monologues are allowed". Does this mean that all scenes must have at least 2 roles in them?  Or is it just the equivalent of "Each actor may have only one role in each scene." It says a little further down that "the number of roles is between 1 and n", suggesting that a scene may contain only 1 actor after all.

thanks, Olof K

Anmäl missbruk
kommenterade 22 mars 2016

EDIT: [...] only 1 role after all.

Anmäl missbruk
kommenterade 28 mars 2016

Hello I am having difficulty with understanding the 4th theory question

  • "Which is the smallest possible production that satisfies all input constraints for the casting problem and is possible to stage. Specify the input for this production."

What do you mean by "production"? Do you minimum number of actors? Or roles? Or simply an instance?

Also what do you mean by "is possible to stage"? What do you mean by "stage" in this context?

Anmäl missbruk
kommenterade 30 mars 2016

Hi, is there a possibility to present lab2 theoritic work on a day other than the 14th of april? I have to fly back to my homecity that day. Thank you in advance!

Anmäl missbruk
kommenterade 30 mars 2016

I have the same question as above (present lab2 theory on another day than 14th April)

Anmäl missbruk
kommenterade 3 april 2016

My interpretation of exercise 4 is that the "smallest possible production" is the production that requires the least amount of actors and/or scenes. Is that correct? 

By "stage" I think it's meant to be able to perform the play on stage with the given constraints. 

I also have a question about the 5th exercise. Is the number of actors, which is asked for, the number of actors that produces that "smallest possible production" or is it something else?

Anmäl missbruk
Lärare kommenterade 3 april 2016

If you can not attend the session on April 14 you can give your theory solutions to Mladen at any earlier date.

Anmäl missbruk
kommenterade 8 april 2016

In lab 2, are we only supposed to reduce the graph coloring problem to the casting problem or also solve it?

What should the output be? Similar to the instances in the description?

Anmäl missbruk
kommenterade 10 april 2016

Hi,
Regarding Lab 2.

Should we apply the "divas" constraints when reducing one of the two NP-complete problems to the casting problem? 

Should we apply the "divas" constraints to the theory questions 4-6? It is not explicitly specified.

Anmäl missbruk
kommenterade 12 april 2016

Hello,

I was wondering, what is the input from Kattis is exactly? I've been trying to read the graph, assuming that the edges are given one line at the time as two integers separated by a space, but I continue to get a NumberFormatError. If we could get some specifications as to how the input is formatted so we can know how to read it properly that would be very helpful.

Thanks a lot!

Anmäl missbruk
En person gillar kommentaren
Lärare kommenterade 12 april 2016

An update has been made to Lab 2

Anmäl missbruk
kommenterade 12 april 2016

What exactly is the update to the lab? I've been working on the lab and I don't see any difference in the assignment.

Thank you

Anmäl missbruk
En användare har tagit bort sin kommentar
Lärare kommenterade 12 april 2016

The links are ok now.

Anmäl missbruk
kommenterade 12 april 2016

I still can't see any difference, the Kattis pages only consist of a title and a submit-page.

Anmäl missbruk
kommenterade 12 april 2016

To clarify what the task is in Lab 2: Should the output of our program be equal to the input to the casting problem, as exemplified in the instructions?

Anmäl missbruk
Lärare kommenterade 12 april 2016

It was a problem with the links to the submit-page it seems as it they didn't work for everyone.

Anmäl missbruk
Lärare kommenterade 12 april 2016

Your output should be an input to the casting problem.

Anmäl missbruk
kommenterade 13 april 2016

Does each role need to be in at least one scene for a valid casting problem? If not, does actor 1 and 2 need to be in a scene or just assigned a role?

Anmäl missbruk
kommenterade 13 april 2016

What format does Kattis input to the program have?
Will it be separated by commas or white spaces?

Anmäl missbruk
kommenterade 13 april 2016

@Oskar, it seems the Kattis input has leading whitespace

Anmäl missbruk
kommenterade 21 april 2016

16 of my test cases are accepted on Lab 2 (NP reduction 1) but then I get the error message "Output Limit Exceeded". What does this mean?

Anmäl missbruk
kommenterade 21 april 2016

I solved it. I had simply literally constructed a solution that had too much output and I was able to construct a different solution with much less. 

Anmäl missbruk
kommenterade 21 april 2016 
We are trying to reduce the Graph coloring problem, but its passes 5 tests and shows this:
The judge failed to verify your reduction.
It is possible that your reduction is correct - and that it is wrong. However, it is possible to accomplish more compact reductions, that can be verified by the judge.

What does it mean? I'm pretty sure our reduction is correct...
Anmäl missbruk
kommenterade 22 april 2016

Hi,
Another question, I presented both parts of LAB 2 last week but have not been given any points/marks for it.
Are all the presentations going to be marked after today's session?

Anmäl missbruk
Lärare kommenterade 22 april 2016

Yes.

Anmäl missbruk