Instructions:
You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set turned back to you.

1. (1.5)
   Say we had a "black box," which takes two numbers as input and outputs their sum. See Figure 1.7a in the Textbook. Say we had another box capable of multiplying two numbers together. See figure 1.7b. We can connect these boxes toghether to calculate p * (m + n). See Figure 1.7c. Assume we have an unlimited number of these boxes. Show how to connect them together to calculate:
   1. ax+b
   2. The average of the four input numbers w, x, y, and z
   3. a² + 2ab + b² (can you do it with one add box and one multiply box?)


2. (1.14)
   Suppose we wish to put a set of names in alphabetical order. We call the act of doing so sorting. One algorithm that can accomplish that is called the bubble sort. We could then program our bubble sort algorithm in C, and compile the C program to execute on an x86 ISA. The x86 ISA can be implemented with an Intel Pentium IV microarchitecture. Let us call the sequence "Bubble Sort, C program, x86 ISA, Pentium IV microarchitecture" one transformation process.
   Assume we have available four sorting algorithms and can program in C, C++, Pascal, Fortran, and COBOL. We have available compilers that can translate from each of theses to either x86 or SPARC, and we have available three different microarchitectures for x86 and three different microarchitectures for SPARC.
   1. How many transformation processes are possible?
   2. Write three examples of transformation processes.
   3. How many transformation processes are possible if instead of three different microarchitectures for x86 and three different microarchitectures for SPARC, there were two for x86 and four for SPARC.
3. (2.3)
   1. Assume that there are about 400 students in your class. If every student is to be assigned a unique bit pattern, what is the minimum number of bits required to do this?
   2. How many more students can be admitted to the class without requiring additional bits for each student's unique bit pattern?
   
   
4. (2.13)
   Without changing their values, convert the following 2's complement binary numbers into 8-bit 2's complement numbers.
   1. 1010
   2. 011001
   3. 1111111000
   4. 01


5. (2.22)
   Create two 16-bit 2's complement integers such that their sum causes an overflow.


6. (2.37) This problem has been postponed. It will apear on a future Problem Set.
   If n and m are both 4-bit 2's complement numbers, and s is the 4-bit result of adding them together, how can we determine, using only the logical operations described in Section 2.6, if an overflow has occurred during the addition? Develop a "procedure" for doing so. The inputs to the procedure are n, m, and s, and the output will be a bit pattern of all zeros (0000) if no overflow occurred and 1000 if an overflow did occur.


7. (2.40 a,b,c) This problem has been postponed. It will apear on a future Problem Set.
   Write the decimal equivalents for these IEEE floating point numbers.
   1. 0 10000000 00000000000000000000000
   2. 1 10000011 00010000000000000000000
   3. 0 11111111 00000000000000000000000


8. (2.42)
   A computer programmer wrote a program that adds two numbers. The programmer ran the program and observed that when 5 is added to 8, the result is the character m. Explain why this program is behaving erroneously.


9. (2.50 b,d) This problem has been postponed. It will apear on a future Problem Set.
   Perform the following logical operations. Express your answers in hexadecimal notation.
   • xABCD OR x1234
   • x00FF XOR x325C


10. (2.54) This problem has been postponed. It will apear on a future Problem Set.
    Fill in the truth table for the equations given. The first line is done as an example.
    Q1 = NOT (NOT(X) OR (X AND Y AND Z))
    Q2 = NOT ((Y OR Z) AND (X AND Y AND Z))



X Y Z	Q1 Q2
0 0 0	0 1



11. (2.55 a-d)
    We have represented numbers in base-2 (binary) and in base-16 (hex). We are now ready for unsigned base-4, which we will call quad numbers. A quad digit can be 0, 1, 2, or 3.
    
    1. What is the maximum unsigned decimal value that one can represent with 3 quad digits?
    2. What is the maximum unsigned decimal value that one can represent with n quad digits (Hint: your answer should be a function of n)?
    3. Add the two unsigned quad numbers: 023 and 221.
    4. What is the quad representation of the decimal number 42