Prg1 starting exercises¶

These exercises check that you have understood the prg1 and prg1-opt instructions, help you to start working for the prg1, and verify that you know how to test locally your code.

PRG1 instructions¶

All questions concern prg1 instructions.

Question 1

Affiliation in this project must always have …

a unique integer id

a unique string id

coordinates (x,y)

a name

a foundation year

a title

a list of workers

Question 2

Publication in this project must always have …

a unique integer id

a unique string id

coordinates (x,y)

a name

a publication year

a title

a list of authors

Question 3

What are the limits on how many publications can one affiliation be associated with?

minimum 0, maximum 16

minimum 0, no maximum.

minimum 1, maximum 16.

minimum 1, no maximum.

Question 4

What are the limits on how many affiliations can be associated with a single publication?

minimum 1, maximum 10

minimum 1, no maximum

minimum 0, no maximum

minimum 0, maximum 10

Question 5

Which of the following is true for publications?

a publication can only be referenced by one other publication

a publication can only reference one other publication

a publication can be referenced by 0 or more publications

a publication can reference 0 or more publications

Cyclic references with publications are not allowed.

Publications form a tree structure

Question 6

Which of the following holds true for associative containers?

You can reference to some value with some type of unique id.

It is not possible to iterate throught all the values.

It is possible to sort the container to different orders.

Removal of elements invalidates references to elements other than the removed one.

Question 7

Which of the following ones are good choices for storing information about a single affiliation?

a struct

a class

a vector

a function

an unordered map

Question 8

How do you change the working directory in Qt Creator?

Press the run button and hope for the best

Go to the project settings, and set the working directory under the run configuration accordingly

You can’t change the working directory from Qt Creator

PRG1 instructions on testing¶

All questions concern prg1 instructions on testing. The perftest outputs later in this exercise are not real data, the data should not be used for comparison with your own implementation.

Question 1

Functionality test can be run with

test command

with testable function name as a parameter such as get_all_affiliations

testread command

with -in.txt and -out.txt files as parameters

perftest command

with a command name, timeout value, repeat count value and N values as parameters

Question 2

Performance test can be run with

test command

with only the testable function name as a parameter such as get_all_affiliations

testread command

with -in.txt and -out.txt files as parameters

perftest command

with a command name, timeout value, repeat count value and N values as parameters

Question 3

Functionality tests show differences, what to do now?

nothing, the functionality test might show some differences due to runtime variation

find out why there are differences and fix the code in datastructures.cc and datastructures.hh

Question 4

What is important to note when running perftests?

Perftest output does not give the asymptotic performance of the code

Perftest will give different time and command counts on different hardware and operating system

It is important to check if the functionality is correct before optimizing

Question 5

What is said about using command counters as a measure of performance?

Command counters measure the performance with less variation compared to time from other programs running on the computer

Command counters have a tendency to crash the program

It is impossible to use command counters if one doesn’t own a linux computer

You can use tie-tiraka.it.tuni.fi to test with command counters if your computer doesn’t support them

Next couple of questions consider the perftest output below

> perftest get_all_affiliations 10 10 100;1000;10000;100000
Timeout for each N is 10 sec.
For each N perform 10 random command(s) from:
get_all_affiliations
     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,      0.50000 ,    1         ,      1.50000
  1000 ,       1.0000 ,    2         ,       3.0000
 10000 ,      5.00000 ,    4         ,       9.0000
100000 , ADD Timeout!
>

Question 6

What function is being perftested?

get_all_affiliations

get_affiliations_alphabetically

get_all_publications

Question 7

Did the perftest time out/ fail? If so, why?

Perftest finished and did not time out or fail

Add timed out, it would be good idea to improve add_affiliation and add_publication performance

functon which is being tested timed out

the program crashed

Next couple of questions consider the perftest output below

> perftest get_all_publications 20 10 100;1000;10000;100000
Timeout for each N is 20 sec.
For each N perform 10 random command(s) from:
get_all_publications
     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,      0.50000 ,    1         ,      1.50000
  1000 ,       1.0000 ,    2         ,       3.0000
 10000 ,      5.00000 ,    4         ,       9.0000
100000 ,      8.00000 , Timeout!
>

Question 8

What is the timeout (in seconds) used for the perftest?

Question 9

How many times the command to be tested is run for each N?

Question 10

Why did the command print Timeout!?

Adding the affiliations and publications took too long

Running get_all_publications 10 times took too long

Program crashed

Next couple of questions consider the perftest output below

> perftest get_affiliation_name 10 10 5;10;50;100
Timeout for each N is 10 sec.
For each N perform 10 random command(s) from:
get_affiliation_name
      N ,    add (sec) ,   cmds (sec) ,  total (sec)
      5 ,      0.00004 , terminate called after throwing an instance of 'std::out_of_range'
  what():  unordered_map::at
Aborted (core dumped)

Question 11

What happened in the perftest?

Program crashed during the execution of get_affiliation_name, most likely the code is not checking for unordered_map key validity

Perftest was successful, program works as it should

Adding the affiliations and publications took too long

Running get_all_publications 10 times took too long

Next couple of questions consider the perftest output below

> perftest get_all_affiliations 10 10 100;1000;10000;100000
Timeout for each N is 10 sec.
For each N perform 10 random command(s) from:
get_all_affiliations
      N ,    add (sec) ,  add (count) ,   cmds (sec) , cmds (count) ,  total (sec) , total (count)
    100 ,  0.000112247 ,       280203 ,   3.5244e-05 ,        43740 ,  0.000147491 ,       323943
   1000 ,  0.000116914 ,       569395 ,   3.8864e-05 ,        74040 ,  0.000155778 ,       643435
  10000 ,   0.00051654 ,      2740514 ,   8.6724e-05 ,       317460 ,  0.000603264 ,      3057974
 100000 ,  0.000976794 ,      5443984 ,  0.000131009 ,       619420 ,    0.0011078 ,      6063404
>

Question 12

What is the command count for running get_all_affiliations 10 times, when there are 10000 affiliations and publications?

Question 13

How long it took to execute that? (in seconds, the same way as the output)

Question 14

What is the command count for adding 1000 affiliations and publications?

Question 15

What is the command count on adding 100000 publications and affiliations AND running get_all_affiliations 10 times?

Question 16

What can be said by reading the perftest output:

get_all_affiliations is for sure asymptotically constant

running get_all_affiliations 10 times is slower when there are more affiliations and publications

addition is asymptotically \(\Theta(n)\) (linear)