CS 117 Assignment: Do it, but don't hand it in.

1. Suppose you are starting with an array a[] of integers, and an integer N that tells you how many items are in the array. The following code finds the maximum distance between elements of a[] (that is, it looks at every pair a[i] and a[j], and finds the distance between the pair that is furthest apart).

   
   	int max = 0;
   	for( int i=0; i < N; i++ )
   	{
   		for( int j=0; j < N; j++ )
   		{
   			if( a[i] - a[j] > max )
   				max = a[i] - a[j];
   		}
   	}
   

   • When you execute this code, at most how many primitive operations (=, ++, <, etc.) get executed?
   • If this code takes 1 second for N = 5000, approximately how long will it take for N = 15000?
   • This code solves the problem in an extremely inefficient way. Can you come up with a better algorithm?
   
   
   
2. For each of the following positive binary integers, what is the decimal equivalent?
   • 1101
   • 1110111
   • 1
   
   
   
3. Add 11010 to 1011. Show your work (in particular, show where you get carries, and where you don't). You can check your work by translating the numbers into decimal, but I want to see you do the usual gradeschool addition algorithm in base 2 instead of base ten.
   
   
4. When you look at an integer expressed in the decimal system, it's easy to tell whether the number is divisible by 2, or 5, or 10, or 100, or 1000, or.... For example, a number is divisible by 5 if its decimal expression ends with a 5 or a 0, and a number is divisible by 100 if its decimal expression ends in two zeros.

   What sorts of divisibility are easy to see when a number is expressed in binary, and how can you see them?
   
   

5. The number 1.398 is equal to 1 + 3/10 + 9/100 + 8/1000. If we move to binary, and use a "binary point" instead of a decimal point, what will the following numbers equal? That is, what are the base ten equivalents of the following binary numbers?
   • 0.11
   • 1.011

   When you multiply a decimal number by 10, you shift the decimal point to the right one place. How can you shift a binary point to the right?
   
   

6. Rewrite the following base-ten numbers as 16-bit two's complement integers: -1, 31, -31, and 1729.
   
   
7. What does the bit pattern 01101001 represent if you interpret it as an 8-bit two's complement integer? What if you interpret it as a character using ASCII?