Exam 1: Midterm

Solutions and Commentary

Part of the homework for 22C:60 (CS:2630), Fall 2011
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distributions

Exam 1

                                 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

Machine Problems 1 and 2

                                         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

Homeworks 1 to 6

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

Total of the above

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

Solutions

  1. Fill in the following table; values in the blanks in each column derive from the given values in that column, all values in each row are derived from the given values using the same rules. (4 points)
    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.

  2. Translate the following brief useless SMAL code to a sequence of bytes loaded in memory. The spaces to the right are labeled with a word and byte in word addresses; fill in the hexadecimal value that goes in that byte; leave uninitialized bytes blank. The result of assembling the first lines are given. (2 points)
        . = 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
    
  3. a) A small Hawk subroutine is given below to the right. Assemble this into the halfword memory locations given to the left below. The first instruction is worked for you. (1.5 points)
        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.

  4. The following SMAL Hawk code is related to MP3. The comments are correct. The program was somewhat optimized and it worked before parts of it were carefully cut out and replaced by blanks. Fill in the missing parts. (2 points)
            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.