University of Waterloo
CS240 Spring 2022 Assignment 5 Post-Mortem
This document goes over common errors and general student performance on the assign- ment questions. We put this together using feedback from the graders once they are done marking. It is meant to be used as a resource to understand what we look at while marking and some common areas where students can improve in.
Question 1 [5 Marks]
• Many students who got this question wrong obtained an incorrect recurrence relation and hence the wrong runtime bound.
• Some students did not recognise that x and y comparisons alternate, starting (by default) with the x coordinate.
Question 2 [2+3 = 5 Marks]
• For part (a), most students who obtained incorrect tries used the wrong tie-breaking techniques.
• For part (b), some students encoded mississauga with T1 instead of massasagua.
• For part (b), some students gave the size of the alphabet of the string being encoded, not the size of the alphabet that was used to construct the Huffman trie (particularly T1 ).
• For part (b), a few students forgot to take the ceiling of log |Σ| when calculating the compression rate.
Question 3 [2+1+3+2 = 8 Marks]
• For part (a), some students stated that the sequential progression of characters (e.g.: 0 → 1 → 2 → 0 → …) could be preserved, but did not give a suitable explanation for how it could work (by representing runs of length 0).
• For part (d), some students did not provide their compressed string or forgot to give the final compression ratio.
Code Help, Add WeChat: cstutorcs
Question 4 [3+4+4 = 11 Marks]
• For part (a), some students who lost marks did not indicate which coordinate the main and associate trees were with respect to.
• For part (a), students did not write the entire coordinates in the nodes – only either the x or y values. No deductions were applied for this.
• For part (b), answers that did not receive full credit were not justified enough (for either correctness or runtime).
Question 5 [3+4 = 7 Marks]
• For part (a), some students did not obtain the correct failure array – the most common incorrect answer was [0, 0, 0, 1, 2, 3, 1] instead of the intended array, [0, 0, 0, 1, 2, 3, 4].
• For part (b), some students who lost marks here did not clearly indicate where character mismatches were occurring.
• For part (b), some answers skipped one or two steps (i.e. some rows were missing). Question 6 [1+3+3+3+5 = 15 Marks]
• For part (b), some answers that lost marks placed brackets in locations where there should not have been any. Brackets are meant to denote an implied match, but this cannot always be guaranteed if we have already seen and moved past the last occurrence of a character in the pattern.
• For parts (c) and (d), some incorrect answers did not generalize for any n and/or m. The most common incorrect solution was to just use a pattern length of 1.
• For part (e), some students provided invalid counterexamples which were usually off by 1 index.
CS Help, Email: tutorcs@163.com