Laboratory work

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)

Lab 2  (updated)

Johan Karlander skapade sidan 9 januari 2017

kommenterade 20 januari 2017

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?

Anmäl missbruk
Lärare kommenterade 20 januari 2017

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

Anmäl missbruk
kommenterade 31 januari 2017

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.

Anmäl missbruk
kommenterade 3 februari 2017

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

Anmäl missbruk
Lärare kommenterade 6 februari 2017

I will try to get algokomp17 working on Kattis today.

Anmäl missbruk
kommenterade 7 februari 2017

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?

Anmäl missbruk
kommenterade 7 februari 2017

Yes I have been wondering this too!

Anmäl missbruk
Lärare kommenterade 8 februari 2017

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

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 8 februari 2017

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.

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 8 februari 2017

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.

Anmäl missbruk
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 9 februari 2017

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

Anmäl missbruk
kommenterade 9 februari 2017

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?

Anmäl missbruk
kommenterade 9 februari 2017

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?

Anmäl missbruk
kommenterade 9 februari 2017

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

Anmäl missbruk
kommenterade 17 februari 2017

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

Anmäl missbruk
Lärare kommenterade 17 februari 2017

You must come and present your lab.

Anmäl missbruk
kommenterade 17 februari 2017

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

Anmäl missbruk
Assistent kommenterade 17 februari 2017

Hopefully today. Otherwise on Monday.

Anmäl missbruk
Assistent kommenterade 21 februari 2017

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.

Anmäl missbruk
kommenterade 22 februari 2017

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.

Anmäl missbruk
Assistent kommenterade 23 februari 2017

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

Anmäl missbruk
kommenterade 3 mars 2017

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

Anmäl missbruk
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
Lärare kommenterade 21 mars 2017

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

Anmäl missbruk
kommenterade 21 mars 2017

The links still gives 404 error, not found.

Anmäl missbruk
En användare har tagit bort sin kommentar
Lärare kommenterade 21 mars 2017

Corrected now.

Anmäl missbruk
kommenterade 1 april 2017

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.

Anmäl missbruk
kommenterade 1 april 2017

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

Anmäl missbruk
kommenterade 1 april 2017

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.

Anmäl missbruk
kommenterade 2 april 2017

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

Anmäl missbruk
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 3 april 2017

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

Anmäl missbruk
En användare har tagit bort sin kommentar
En användare har tagit bort sin kommentar
kommenterade 5 april 2017

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

Anmäl missbruk
Assistent kommenterade 5 april 2017

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.

Anmäl missbruk
kommenterade 6 april 2017

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

Anmäl missbruk
Assistent kommenterade 6 april 2017

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

Anmäl missbruk
kommenterade 7 april 2017

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?

Anmäl missbruk
Assistent kommenterade 10 april 2017

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.

Anmäl missbruk
kommenterade 16 april 2017

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

Anmäl missbruk
kommenterade 16 april 2017

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:



      
positive instance:

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.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            18 april 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            21 april 2017

            
        

        
            

                 
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? 

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            21 april 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            22 april 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            22 april 2017

            
        

        
            

                 
When can we present the lab next?

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            22 april 2017

            
        

        
            

                 
It will be announced later.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            8 maj 2017

            
        

        
            

                 
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?

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            8 maj 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            9 maj 2017

            
        

        
            

                 
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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            9 maj 2017

            
        

        
            

                 
Ja.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            9 maj 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            15 maj 2017

            
        

        
            

                 
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.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            15 maj 2017

            
        

        
            

                 
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.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            24 maj 2017

            
        

        
            

                 
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.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            2 juni 2017

            
        

        
            

                 
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.

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            3 juni 2017

            
        

        
            

                 
Do we book a time or just show up?

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        
En användare har tagit bort sin kommentar

    





    

        

            Lärare
            
            kommenterade
            4 juni 2017

            
        

        
            

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

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            
            
            kommenterade
            6 juni 2017

            
        

        
            

                 
How do you sign up? 

            

            

              

              
              
Anmäl missbruk

            

        
        
    





    

        

            Assistent
            
            kommenterade
            7 juni 2017

            
        

        
            

                 
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

            

            

              

              
              
Anmäl missbruk

            

        
        
    



                

            
	    

	

    




  

  

  

  

        

      

      
    

    





  

  
  



  

    Feedback
    
    Nyheter