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.

All questions relate to the prg1 documentation.

Question 1

A place must have

a unique integer identifier (id)

a unique string identifier (id)

height

location coordinates (x, y)

a name

a unique emoji

a type

Question 2

Place ..

has a unique location where no other places can exist

has coordinates that are used to calculate Manhattan distance from the origin for sorting

has coordinates that are used to calculate Euclidean distance from the origin for sorting

can have coordinates containing decimals (NO_COORD does not count)

can be added to only one area

Question 3

An area has

a unique integer identifier (id)

a unique string identifier (id)

a coordinate list (x, y)

a name

year of establishment

height

places (at the moment when the area is added to the data structure)

Question 4

An area

can have many subareas (children)

can have only one subarea (child)

can have many parents

can have many ancestors

finding the closest common ancestor is an ambiguous task

Question 5

How many subareas can a single area have?

a minimum of 0 and a maximum of 9.

a minimum of 0 and no maximum limit.

a minimum of 1 and a maximum of 9.

a minimum of 1 and no maximum limit.

Question 6

What are good choices for storing a place data?

struct

class

vector

function

unsorted map

Question 7

How can you change the working directory in Qt Creator?

Press the run button and hope for the best

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

You cannot 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 all_places

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 all_places

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

Next couple of questions consider the perftest output below

> perftest 10*all_places 10 100;1000;10000;100000
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
all_places

     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,    0.5000000 ,  1.000000000 ,    1.5000000
  1000 ,     1.000000 ,   2.00000000 ,     3.000000
 10000 ,      5.00000 ,    4.0000000 ,      9.00000
100000 , ADD Timeout!
>

Question 6

What function is being perftested?

all_places

get_places_alphabetically

all_areas

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_place and/or add_area performance

functon which is being tested timed out

the program crashed

Next couple of questions consider the perftest output below

> perftest 10*all_places 20 100;1000;10000;100000
Timeout for each N is 20 sec (for ADD and test functions).
For each N perform command(s):
all_places

     N ,    add (sec) ,   cmds (sec) ,  total (sec)
   100 ,  0.500000000 ,     3.000000 ,     3.500000
  1000 ,   1.00000000 ,      6.00000 ,      7.00000
 10000 ,    5.0000000 ,      12.0000 ,       17.000
100000 ,    8.0000000 , 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 data (places and/or areas) took too long

Running all_places 10 times took too long

Program crashed

Next couple of questions consider the perftest output below

> perftest 10*get_place_name 10 5;10;50;100
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
get_place_name

      N ,    add (sec) ,   cmds (sec) ,  total (sec)
      5 ,   2.9655e-05 , 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_place_name, most likely the code is not checking for unordered_map key validity

Perftest was successful, program works as it should

Adding the data (places and/or areas) took too long

Running all_places 10 times took too long

Next couple of questions consider the perftest output below

> perftest 10*all_places 10 100;1000;10000;100000
Timeout for each N is 10 sec (for ADD and test functions).
For each N perform command(s):
all_places

     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 all_places 10 times, when there are 10000 places?

Question 13

How long did it take in total to execute the case from the previous question, including the time spent on adding the test data in addition to the time used for executing the commands? (in seconds, the same format as in the output)

Question 14

What is the command count when adding 1000 places among other data?

Question 15

What is the total command count when adding AND running all_places 10 times when the number of places (N) is 100000?

Question 16

What can be said by reading the perftest output:

all_places is for sure asymptotically constant

running all_places 10 times is slower when there are more places (greater N)

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

Posting submission...