Question
Issue letter
Deduction
Issue description
1
A
12
More than 3 functions in the wrong rank
B
8
Less than 3 functions in the wrong rank
C
8
No satisfactory explanation (= D & E & F & G)
D
2
Explanation missing/wrong re: polynomials vs exponentials. We know that polynomials grow slower than exponentials, and the exponentials are ordered by their basi
E
2
Explanation missing/wrong re: polynomials ordering. For polynomials fi and fj, we know that fi and fj can be ordered by comparing the highest exponent on any term i to the highest in fj.
F
2
Explanation missing/wrong re: log(n) vs n. We know that log(n) grows slower than n (hence why n^8 is more significant than n^7*log(n^3)).
G
2
Explanation missing/wrong re: log(n^c). We know that log(n^c) = c*log(n), therefore constant c doesn’t factor in to order. It suffices to show that log(n^5) = 5log(n).
H
1
Minor incorrect point in explanation.
2x
I
1
Missing/wrong best-case discussion when necessary
J
1
Missing/wrong worst-case discusion when necessary
K
2
Missing/wrong running time
L
2
Missing/unsatisfactory running time explanation
2x & 3x
M
1
Minor incorrect/missing point (e.g. giving an upper bound when a tight one is possible, or missing the reasoning for a tight bound (like the presence of for loops))
3x
N
4
Wrong answer given.
3a
O
3
Missing/Unsatisfactory: from statement 1 we know running time is ¦¨(n^4) which implies that it is ¦¸(n^4), since a tight bound implies an upper and lower that are the same.
3b
P
2
Missing/Unsatisfactory: incompatible with statement 1 which gives a tight bound ¦¨(n^4) implying running time is O(n^4) and ¦¸(n^4)
Q
2
Missing/Unsatisfactory: in order to be ¦¨(n^3), running time would have to be O(n^3) and ¦¸(n^3). You can’t have a lower bound ¦¸(n^4) and an upper O(n^3)
3c
R
2
Missing/Unsatisfactory: from statement 2 we know that the running time is bounded by O(n^6), which is compatible with the tight bound
S
2
Missing/Unsatisfactory: none of the other statements preclude the possiblilty that the running time is also ¦¸(n^6). Which is necessary for the tight bound. Statement 3 doesn’t say that it’s best case is ¦¨(n), it simply states a lower bound of ¦¸(n)
3d
T
2
Missing/Unsatisfactory: not compatible with statement 4, since any algorithm solving P (according to 4) has a lower bound of ¦¸(n^3)
U
2
Missing/Unsatisfactory:. No algorithm could be both ¦¸(n^3) and O(n^2), because the former says the algorithm must grow at least n^3, whereas the latter says less than or equal to n^2.
3e
V
1
Missing/Unsatisfactory: must show that algorithm B is both O(n^3) and ¦¸(n^3)
W
2
Missing/Unsatisfactory: O(n^3) is compatible with statement 2 since an O(n^6) can be a O(n^3). No other contradictions with this upper bound
X
2
Missing/Unsatisfactory: Algorithm being ¦¸(n^3) is compatible with both statements 3 and 4.
4a
YA
2
Pseudo-code not detailed enough to be implementable, or not presentable enough to be understood well.
YB
2
Small efficiency issue e.g.
i: shouldn’t do multiple calls to substring() on same tokens
ii: should do token length-check earlier to avoid calls to substring()
iii. should use while loop to break earlier
iv. should adapt comparison outside of loop to reduce number of times it’s executed
YC
4
Medium efficiency issue e.g.
i: builds a heap then performs n removals. That’s O(n * log(n) * k) instead of O(n * k) where k is the run time of all the substring matching.
ii. Unnecessary extra loops (e.g. for transferring tokens to another sequence, or storing up candidate tokens and iterating through them again later). iii. Performs an O(n*log(n)) or O(n^2) sort when you could just step through tracking the max length t as you go.
YD
10
Large efficiency issue (Usually the complexity class is drastically worse than O(n * k) where k is the run time of all the substring matching per t.
s. n fi
YE
2
Correctness issue, e.g.
i: Due to loop constraint, does not loop over all elements necessary
ii: Substring arguments wrong way around
iii. Not incrementing loop index
iv. Loop index is not reset, so non-existent array indices are queried
v. boolean not reset, so loops no longer function properly
vi. Using the wrong index to index an array (e.g. using the L indices to index into D, or indexing from 0 instead of 1 as defined in question) vii. Undefined variables in use
viii. Variable never updated
YF
11
Major correctness issue, e.g. after any minor issues fixed:
i: doesn’t find longest t. You may continue iterating after finding the longest t, or break too early when finding the first t that is a substring of all L, or even return all candidate t instead of just the longest
ii: doesn’t find a t that is a substring of all words in L. You may update your return variable before establishing that t is a substring oafll w in L.
iii. Only checks whether the longest token in t is a substring of words in L (i.e. doesn’t try the next longest, and the next, etc.)
YG
20
No algorithm provided, or algorithm makes no attempt to relate D and L in any way.
YH
1
Very minor issue
4b
ZA
7
Overral run time majorly incorrect
ZB
3
Overral run time minorly incorrect
ZC
2
Wrong/Missing asympotic bounds* e.g.
i. Worst & best case should be listed separately as tight bounds if this run time always happens in best/worst case (even if the algorithm in general does not). ii. Gave a tight bound for an algorithm that was already given different upper and lower bounds / best/worse cases.
iii. Missing upper/lower bound for overall algorithm (perhaps only stated worst/best case tight bounds)
ZD
1
Minor incorrect/missing explanatory point* e.g.
i. Slightly wrong run time for a part of the algorithm
ii. Not explained: substring() in best case constant time (when length of first argument is greater than second, making it impossible to be a substring). So in best case running and failing once per t in constant time doesn’t increase the run time from O(n).
iii. Not explained: substring(w,w’) is generally O(length(w’)) (e.g. Knuth-morris-pratt algorithm). It’s O(length(w)*length(w’)) in the naive case, so this is also a fine assumption. It’s not O(length(w)).
iv. Missed if true: in worst case each t is found to be larger than the last and a substring of all L
v. Length of each string is its own value; they aren’t all equal to some fixed value k/n/p/q/w/L (e.g. max/average). So instead of saying something like O(nmk) we coul say O(nk) where k = sum of the lengths of all words in L
vi. For an outer loop running n times, and an inner loop with the definition “1 to m”, the candidate says something like “inner loop runs m times” in total, instead of “m times for each iteration of outer loop”.
vii. Slightly wrong/incompete best/worse case scenario description.
ZE
3
Major incorrect/missing explanatory point* e.g.
i. explanation in no way matches run time given
ii. Wrong best/worst case scenario leading to wrong upper/lower bound
iii. No/wrong best & worst case discussion
iv. No explanation of how loops and other constructs affect run time. Talk about iterations, and why nesting changes things. v. No explanation of the scenario that produces best/worse case. E.g. what input causes the loop to break early?
ZF
15
No explanation provided (stating running times in words is not an explanation, must explain why that is the run time).
ZG
10
No overall running time provided. Perhaps only listed running time of components of the algorithm.
ZH
2
No/wrong explanation of substring(). Constant time when length(w)>length(w’). Grows proportional to length(w’). Proportional to length(w)*length(w’) is allowable.
d