COS 111   Fall 1999 
Solutions to Problem Set 9
Grader:  Elena Oranskaya

Problem 1.
a)
	if (x == 0)
	  z = y + w;
	else
	  z = y + x;
	  
b)

	Suppose that the variable x, y, z, w are correspondingly stored
	in memory locations 50, 51, 52, 53.
	
	Also assume that the program starts at memory location 10.
	
	
10	1150		load x into register 1
12	1251		load y into register 2	
14	2000		load 0 into register 0
16	B11C		If (x == 0) jump to 
18	5312		add x and y and place the value in register 3
1A	B020		jump to the store instruction
1C	1153		load w into register 1 (we don't need x any more)
1E	5312		add y and w and place the value in register 3
20	3352		store the contents of register 3 into z, i.e. memory
			location 52
22	C000		halt

The above Java and machine code are not unique. There are many ways 
of writing down the correct answer.


Problem 2.
It is necessary to declare the types of variables for a few reasons:
1. Different variable types occupy various amounts of memory. For example,
a character is usually 8 bits, and a floating point number - 32 bits. Therefore
it is necessary to know the data type in order to preperly allocate the memory
for the variables.
2. Any instruction set contains different instructions to perform the same 
operation om different data types. As we see from the language of a machine in
Appendix C, it has 2 distinct add op codes for an integer and for a floating
point number. To apply the correct op code the machine needs to know the types
of the variables.
3. The compiler can perform type checking in order to prevent errors if it is 
informed about the variable data types. For example, a function such as square
root can not be applied to a string variable. Such errors will be detected at 
compile time, since the data types were provided.


Problem 3.
Call 	"The next statement is true" s1, statement 1;	
	"The previous statement is false" s2, statement 1;	
	
If we suppose that s1 is true, then s2 is true. But the truth of s2 implies 
that s1 is false. Contradiction!

If we suppose that s1 is false, then s2 is also false. But that implied that 
s1 is true. Contradiction again!

We conclude that there does not exist a valid truth assignment for these two
statements. We arrive at a contradiction just like in the proof of 
uncomputability of the halting problem. In programmable terms, this is not a 
self terminating program, and so it can not be computed by a Turing machine.


Problem 4.
The basic algorithm is as follows
	
	Given number N we want to test its primality
	i will be the possible divisors
	
	(for i = 2 to i = N-1) {
		if ( N modulo i) == 0 then
			declare N composite and terminate
		else
			go to next iteration of the loop, 
			i.e. set i = i + 1;
	}
	
	Since N did not divide any numbers between 2 and N-1, we 
	declare it prime.
	
	
	Note: the above algorithm is written in pseudo-code, i.e.
	it will not compile in any language.
	
	There are many improvements that can be made to the algorithm. A couple
	obvious ones are:
	1. Test if N is even as a separate case. If it is - N is not prime
	  (excluding the case of N == 2). If not, we can start i at 3 and
	  increment it by 2 (skipping all the even divisors).
	2. Run the loop only up to square root of N (i.e. greatest integer, 
	  which is less than square root of N).
	  
	  
	Though these improvements will affect the actual running time of the
	algorithm, they will not affect its asymptotic complexity. So, we 
	might as well analize the basic algorithm presented at the beginning.
	
	The loop iterates N-2 times, i.e. proportional to N. Inside the loop
	we only have a modulation operation which takes a constant amount of 
	time. So, our algorithm runs on the order of O(N), linear in N.
	However, the analysis should be done in terms of size of N.
	To represent N, we need log N bits, i.e. size(N) = log N.
	Now we need to express the complexity in terms of log N.
		N = 2 ^ log N , ^ denoting power.
	So, our algorithm runs of the order of (2 ^ size of input), i.e. it is
	exponential in the size of input.