Exam 1: MidtermSolutions and Commentary
Part of
the homework for 22C:60 (CS:2630), Fall 2011
|
X Mean = 6.39 X Median = 6.3 X X X X X X X X X X X X X _________X_X_X___X_X_X_X_X_X_X_X_X_X_____ 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
X X X X X X Mean = 8.36 X X Median = 9.0 X X X X X X X X X X X X ___________X___X___X_______X___X___X___X_ 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10
Mean = 11.60 Median = 11.2 X X X X X X X X X _______X_________________X___X_X_X___X_X_X_X___X_X_X_X___X_X_X_X_X_X_____ 1 . 2 . 3 . 4 . 5 . 6 . 7 . 8 . 9 . 10. 11. 12. 13. 14. 15. 16. 17. 18
Mean = 26.35 X X X X Median = 27.2 X X X X X X X X _____________X_X_____X_X_________X___X_X___X_X___X_X___X_X_X_X_X_____ 6 . 8 . 10. 12. 14. 16. 18. 20. 22. 24. 26. 28. 30. 32. 34. 36. 38 F D C B A
Bit Pattern x 100011 001110 101000 100001 010110 Unsigned decimal ___35___ ___14___ ___40___ ___33___ ___22___ 1's complement of x _011100_ _110001_ _010111_ _011110_ _101001_ (binary) 2's complement of x _011101_ _110010_ _011000_ _011111_ _101010_ x as a 1's comp num __-28___ ___14___ __-23___ __-30___ ___22___ (signed decimal) x as a 2's comp num __-29___ ___14___ __-24___ __-31___ ___22___
Commentary: Almost 2/3 did perfect work here and only 1/10 made large numbers of errors. Negative numbers cause problems for a significant number of students.
. = 0 || Address 3 2 1 0 B #10,#32 || |----|----|----|----| A: W #7654 || 000000: | 76 | 54 | 32 | 10 | ; solved to here || |----|----|----|----| ALIGN 2 || 000004: | 00 | 08 | 00 | 00 | B: H C || |----|----|----|----| C: B #C || 000008: | | | | 0C | ALIGN 4 || |----|----|----|----| D: B #D,"D" || 00000C: | | | 44 | 0D | ALIGN 4 || |----|----|----|----| H A,B,C,D || 000010: | 00 | 06 | 00 | 02 | END || |----|----|----|----| || 000014: | 00 | 0C | 00 | 08 | || |----|----|----|----|
Commentary: Only 1 did perfect work. 1/2 earned more than half credit, and 1/4 earned no credit. The hardest problems for many students involved the values of the labels A, B, C and D, and the distinction between, for example, C and #C (the identifier versus the hexadecimal number) and D and 'D' (the identifier versus the character constant).
Just for fun, here's what happens when you throw the code into the SMAL assembler:
2 . = 0 00000000: 10 32 3 B #10,#32 00000002: 00007654 4 A: W #7654 5 ; solved to here 6 ALIGN 2 00000006: 0008 7 B: H C 00000008: 0C 8 C: B #C 9 ALIGN 4 0000000C: 0D 44 10 D: B #D,"D" 11 ALIGN 4 00000010: 0002 0006 0008 12 H A,B,C,D 00000016: 000C 13 END
Addr: Val || 1000: ___01D4___ || . = #1000 || FUNCT: 1002: ___E3F0___ || LIS R4,1 || FUNLP: 1004: ___0302___ || TESTR R3 || BZS FUNXT 1006: ___CF13___ || ADDSI R3,-1 || ADD R4,R4,R4 1008: ___4434___ || BR FUNLP || FUNXT: 100A: ___FB00___ || MOVE R3,R4 || JUMPS R1 100C: ___F4F3___ || || 100E: ___B1F0___ ||
Only 1/14 did perfect work here. This exercise invites clerical errors, so this is not a surprise. What is of greater concern is that 1/3 earned little or no credit, despite the fact that there were several homeworks that announced that this problem or one very like it would be on the exam.
The hardest problem on this question involved displacements for the branch instructions. Many counted from the wrong zero point, or gave displacements in bytes instead of halfwords. A few had trouble with negative displacements.
Just for fun, here is how the SMAL assembler responds to the above code.
3 . = #1000 4 FUNCT: 00001000: D4 01 5 LIS R4,1 6 FUNLP: 00001002: F0 E3 7 TESTR R3 00001004: 02 03 8 BZS FUNXT 00001006: 13 CF 9 ADDSI R3,-1 00001008: 34 44 10 ADD R4,R4,R4 0000100A: 00 FB 11 BR FUNLP 12 FUNXT: 0000100C: F3 F4 13 MOVE R3,R4 0000100E: F0 B1 14 JUMPS R1
b) It is a subroutine. Calling FUNCT with with the integer value i in R3 returns what function of i in R3? (The answer is very short.) (0.5 points)
____it computes f(i) = 2i_______________
about 1/5 did well and 4/5 earned no credit. Of the latter, 3/5 worked very hard, many writing at length while expressing little understanding. In fact, this little bit of code is directly relevant to MP3, where the length of the diagonal of an order-n H-tree is computed using this function.
SUBTITLE "H-tree size routine" ; activation record ;RETAD = 0 ; return address N = 4 ; n, the order of the tree ARSIZE = 8 HSIZE: ; compute the left (p) and right (q) diagonal size of an H tree ; expects R3 = n, the order of the H tree ; returns R3,R4 = (p,q) the sice of the order n tree STORES R1,R2 ; save return address _STORE___R2,R3,N_ ; save parameter n LIS R4,0 ; q = 0 TESTR R3 ; if (n != 0) { _BZS_____HZSQT___ ADDSI R3,-1 ADDI R2,R2,ARSIZE JSR R1,HSIZE ; (p,q) = hsize(n-1) _ADDI____R2,R2,-ARSIZE LOAD R5,R2,N BITTST R5,0 BBS HZSODD ; if (n is even) { _ADD_____R3,R3,R3 ADDSI R3,2 ; p = 2p + 2 BR HZSEIF HZSODD: ; } else { ADD R4,R4,R4 ADDSI R4,2 ; q = 2q + 2 HZSEIF: ; } HSZQT: ; } _LOADS___R1,R2___ JUMPS R1 ; return (p,q)
There were no perfect scores, but 1/2 earned more than half credit, and 2/5 earned more than 2/3 credit.
The initial STORE R3,R2,N instruction was difficult. Only 1/4 got it right, while the vast majority understood that some kind of store instruction operating on R3 was required, but either used the wrong index register or the used a STORES.
1/2 got the BZS HZSQT instruction correct. 3/4 understood that it should be a BZS (or BEQ) but used the wrong label, usually HZSODD.
Almost 1/2 got the ADDI instruction right, while the remainder were evenly split between leaving it blank or filling in apparently random instructions. This is dissapointing, because the ADDI is a standard part of the Hawk calling sequence, and this predicts that half of the class will have difficulty coding function calls.
Almost 1/2 got the ADD instruction correct, while just over 1/3 left it blank or did something bizarre. Of the remainder, many tried to do something relevant and missed, earning partial credit in the process.
Almost 1/2 got the final LOADS right, while as many earned no credit, frequently leaving it blank. Again, this was dissapointing, as this instruction is part of the Hawk standard return sequence, suggesting that half of the class will have difficulty writing working subroutines.
Note: This code is relevant to MP3, but using this recursive algorithm is not a sensible way to find the largest H-tree that will fit on the screen. It would be far more sensible to write the code iteratively.