T-79.240 Special Course on Computational Complexity, Autumn 2003 Home assignment points, 21.1.2004 Week Assignment Student # (last three symbols) 23K 29M 35H 35R 37P 63K 69K 71N 82A 87U 99J 37 1.4.10bcdg 2 2 2 2 - - 0.5 0.5 1.5 2 1.5 2.8.8a 1.5 2 1.5 2 - - 1 1 2 0.5 2 38 2.8.18a 2 1.5 1.5 1.5 - - 2 0.25 1.5 0.5 1 3.4.1bcg 1.5 1 1.75 2 - - 0.5 0.25 1.5 0.75 0.5 40 4.4.5 2 2 2 2 - - 2 2 2 2 2 7.4.5 2 2 1.5 2 - - 1.5 1.5 1.5 1 0.5 41 8.4.2 2 0.5 2 2 - - - 0.75 0.75 2 - 8.4.3 1.25 1.5 2 1 - - - 1 1.25 1 - 42 9.5.2 2 - 2 2 - - 2 1.5 2 0.5 - 9.5.6 2 - 1.5 2 - - - 1 2 2 - 43 9.5.7 1.5 1 2 1.5 - - 1.5 1.25 1 1.5 - 9.5.10a 2 - 2 2 - - - 1.5 2 2 - 44 10.4.13 1 - 1.5 1.5 - - - 0.25 2 1.5 - 10.4.19a 1.5 2 2 2 - - 1 1.5 2 0 - 45 11.5.14 1.25 1.5 2 2 - - - 1.25 1.5 1.5 - 11.5.16a - 1 2 1 - - - 0.75 1 0.5 - 46 12.3.9b 1.5 2 2 1.5 - - - 1.5 0.5 1.5 - 13.4.13a 2 2 2 2 - - - 0.75 2 2 - 47 14.5.5(knapsack) 1.5 2 1.5 1.5 - - - 0.75 1.5 1.5 - 15.5.9a 2 2 2 2 - - - 1.5 2 2 - 48 17.3.2ab 1.5 2 2 2 - - - 1.25 1.5 1.25 - 17.3.12 1 - 2 1 - - - 1.5 - 1.5 - 49a 18.3.6 2 2 2 2 - - - 0.25 2 2 - 19.4.5 0.5 - 2 - - - - 1.5 1.5 1.25 - 49b 9.5.18ab 2 2 - - - - - 1.5 2 1 - 9.5.34a 1.25 1.5 - 1.5 - - - 1.25 1.5 2 - B1 - - - - - - - 1.5 - - - B2 - - - - - - - 0.5 - - - B3 - - - - - - - 1.25 - - - B4 - - - - - - - 1 1.5 - - B5 - - - - - - - 1.25 - - - ------------------------------------------------------------------------------- TOTAL 40.75 33.5 44.75 42 0 0 12 33.5 41.5 35.25 7.5 23K 29M 35H 35R 37P 63K 69K 71N 82A 87U 99J GRADE 5 3 5 5 0 0 0 3 5 3 0 Grade lower bound (percentage / points) 1 50 % / 26 2 57 % / 29.64 3 64 % / 33.28 4 71 % / 36.92 5 78 % / 40.56