SE250:April 24:Test

Question One

1a

• Answer required a piece of code with a loop with at least 10,000 iterations
• A million iterations was a good number for sensible results
• Answer need to explain how to interpret the output as well as how to get results
  • e.g. Comment out bits of code, run the loop several times, etc.

1b

• While the hypothesis sounds reasonable, they were all false under certain circumstances
  • Just stating "fa;se" without qualification was not sufficient as they were generally true
• Need to reference the lab results in explanation

1c

• Answer should include idea that it is not possible to get an accurate measure for runtime by breaking a programme down to its constituents - performance measurement is not reductive

Question Two

2a

• Answer was

1	4
4	4
4	4
5	8

• However it should be noted that the second part of the answer may vary with compiler

2b

• Generally well done
• Ambiguous statement for allocating memory was not accepted
  • i.e. cannot use "int x = 0" for everything, need to be specific about their differences

2c

• Part a) requires understanding to be shown about memory for stack being reused resulting in garble
• Common errors include
  • Claims to char* not being returned (it was)
  • s not being initialised (it was)
• Two possible solution to part b)
  • Allocate memory to s with malloc - however this may result in memory leaks in the programme as it is not obvious who should be responsible for freeing the memory after it is used
  • Making string a static variable - however, every time the function is called the previous value of s will be overwritten

Question Three

3a

• Parameters include
  • Initial capacity
  • Growth factor
• Resizing factor has the greatest effect on performance
• This was well justified

3b

• Growth factors around 10 was not accepted as they were too big
• Diminishing returns could be seen in performance graph
  • i.e. Going from 4 to infinity has a smaller gain than going from 1.5 to 2
• No strong case can be made for growth factors greater than 4
• Model answer would be 1.5ish up to 4
• The shape of the graph is linear with growth factor being inversely proportional to the slope, but with diminishing returns

3c

• People either had this question completely right or wrong - no middle grounds
• The code returns the address in memory of the function interpreted as an integer
  • Not the number of elements in the list
• It was suggested that if people needed convincing, they could write the code themselves
• In order to get the number of elements in the list, the call needs to be

arraylist_size(AL); //where AL is the array list

Question Four

4a

• Diagram was generally well done
• Need to show the self reference of the nil cell in order to get full marks
• Common mistake including making a new chain for ys instead of using the existing cells in xs

4b

• Fairly well done as most has seen a shorter version of this code
• Common mistake was using the code

Cons* zero_one = cons( 0, cons( 1, zero_one ) );

• However, in the above code zero_one is unintialised when called
• An additional step is needed

zero_one->tail->tail = zero_one;

4c

• Reasonably well done
• Common errors include
  • Not stepping ys
• Solution

void sumlist( Cons* xs, Cons* ys ) {
	for( ; xs != nil; xs = xs->tail, ys = ys->tail )
		xs->head += ys->head;
}

• Note that the check ys != nil is insignificant

Question Five

5a

• The question was somewhat ambiguous as theory vs practise could either be considered as statistic vs results or low entropy vs high entropy
  • People are welcome to bring script to John for remark - at the risk of being marked down
• Answer required justification
  • e.g. each statistic test result for buzhash points to random
• Rand was not accepted as an answer
  • This is not an actual hash function
• Two possible solutions for best performing hash function in practise
  • Buzhash for being closest to expected value
  • Java Int for having shortest chains

5b

• H1 can be disproved by either Java Str or Java Int - both of which are superior in practise but poor in theory
• H2 can be disproved by Java Str - which performed better with a low entropy source
• A handful of people pulled examples supporting the hypothesis

5c

• Most had the answer right ("no") but provided no explanation
• Explanation could include
  • Hashing even numbers will result in half the table being empty
  • The function is "fragile" and will "[go] to custard" with certain kinds of data