Assignment 7, due Oct 17

On every assignment, write your name legibly as it appears on your University ID card! Homework is due on paper Homework is due on paper at the start of class on the day indicated (usually Friday). Late work must be turned in to the TA's mailbox (ask the CS receptionist in 14 MLH for help). Never push homework under someone's door!

1. A Problem: Consider this poorly commented SMAL Hawk code for a string compare subroutine:

   S:      ; given:   R3 = s1, pointer to null-terminated string 1
           ;          R4 = s2, pointer to null-terminated string 2
           ; returns: R3 = result of comparing strings 1 and 2
           LOADS   R5,R3
           EXTB    R5,R5,R3
           LOADS   R6,R4
           EXTB    R6,R6,R4
           BZS     Q
           CMP     R5,R6
           BNE     Q
           ADDSI   R3,1
           ADDSI   R4,1
           BR      S
   Q:      SUB     R3,R5,R6
           JUMPS   R1
   

   a) For strings s1 and s2 of equal length, what return value (or range of values) indicates that s1 comes before s2 in alphabetical order? (0.2 points)

   b) For strings s1 and s2 of equal length, what return value (or range of values) indicates that s1 is the same as s2? in alphabetical order. (0.2 points) c) For strings s1 and s2 of equal length, what return value (or range of values) indicates that s1 comes after s2 in alphabetical order? (0.2 points)

   d) For strings s1 and s2 of different lengths where the text of the strings is the same up to the end of the shortest, what return value (or range of values) indicates that s1 is longer than s2. (0.2 points) d) For strings s1 and s2 of different lengths where the text of the strings is the same up to the end of the shortest, what return value (or range of values) indicates that s1 is shorter than s2.

2. Background: Here is the truth table for a randomly selected Boolean function of 3 variables:

   inputs   output   a   b   c   f (a, b, c)  0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

   a) Give the algebraic sum of products representation of this function, using a notation comparable to f(x,y)=xy+y (0.5 points)

   b) Draw the logic circuit for this function, using the notion of an and-array and an or-array described in Chapter 8 of the notes. Neatness counts! (0.5 points)

3. Background: Look at the adder modified to perform logic given near the end of Chapter 8.

   Assignment: Make a truth table for the modified adder with 8 rows selected by inputs a_i, b_i and c_i, and with 4 different groups of output columns. Each group of output columns should give c_i+1 and s_i for one of the combinations of f₁, f₂ and f₃ that are mentioned in the notes. (1.0 points)

   Note: For reference, here are the 4 combinations that the notes discuss. You may use the labels normal, xor, or and and to label your column groups.

   f1   f2   f3   use  1 1 0 normal 1 0 0 xor 1 0 1 or 0 0 1 and