Department of Electrical and Computer Engineering
University of Texas at Austin

EE 379K
Fall, 2000
Y. N. Patt, Instructor
TAs: Kathy Buchheit, Laura Funderburg, Chandresh Jain, Onur Mutlu, Danny Nold, Kameswar Subramaniam, Francis Tseng, Brian Ward
Problem Set 1
Due: September 18, 2000

Instructions:
You are welcome, and in fact encouraged to do the homework in groups. Remember to put your names on the solution sheet. Also remember to put the name and discussion section meeting time/day of the TA in whose discussion section you want the homework returned back to you. Good luck!!!
 
 

1. (1.12)
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 III microarchitecture. Let us call the sequence "Bubble Sort, C program, x86 ISA, Pentium III microarchitecture" one transformation process.

Assume we have available four sorting algorithms and can program in C, C++, Pascal, Fortran and COBOL, and have available compilers that can translate from each of these to either x86 or SPARC, and 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?


2. (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?


3. (2.5)
Write the representations of 7 and -7 in 1's complement, signed magnitude and 2's complement integers.
 

4. (2.8)

  1. What is the largest positive number one can represent in an eight-bit 2's complement code? Write your result in binary and decimal.
  2. What is the greatest magnitude negative number one can represent in eight-bit 2's complement code? Write your result in binary and decimal.
  3. What is the largest positive number one can represent in n-bit 2's complement code?
  4. What is the greatest magnitude negative number one can represent in n-bit 2's complement code?


5. (2.10: 1,4)
Convert these decimal numbers to eight-bit 2's complement binary numbers.

  1. 102
  2. -128


6. (2.36: 1)
Write IEEE floating point representation of the decimal number 3.75
 

7. (2.37: 4)
Write the decimal equivalent for this IEEE floating point number:
1 10000000 10010000000000000000000
 

8. (2.39)
A computer programmer wrote a program that adds two numbers. He/she ran the program and observed that when 5 is added to 8, the result is the character 'm'. Explain why the program is behaving erroneously.
 

9. (2.46: 1,3,5)
Perform the following additions. The corresponding 16-bit numbers are in 2's complement notation. Provide your answers in hexadecimal.

  1. x025B + x26DE
  2. xA397 + xA35D
  3. What else can you say about the answer to part (2)?


10. (2.47: 3,4)
Perform the following logical operations. Express your answers in hexadecimal notation.

  1. NOT((NOT(xDEFA)) AND (NOT(xFFFF)))
  2. x00FF XOR x325C


11. (2.50)
Fill in the truth table for the equations given below. The first line is done as an example.

Q1 = NOT(A AND B)
Q2 = NOT(NOT(A) AND NOT(B))
A B   Q1 Q2
0 0   1 0
         
         
         

Express Q2 another way.
 

12. (Added September 11)
How many bits are needed to represent Avogadro's number (6.02 x 1023 ) in two's complement binary representation? (6.02 x 1023 = 602,000,000,000,000,000,000,000)