When you are doing a Bare Bones program, feel free to use the following Bare Bones functions whenever it reduces your work:
COPY(X, Y) places the value of X into the value of Y without changing the value of X.
MOVE(X, Y) places the value of X into the value of Y and changes the value of X to 0.
It might be interesting and useful for you to try to write two Bare Bones programs that do these functions. That’s not part of this assignment, but it might be a good review for your final exam to do that. Yes, I think it would be.
A. Write a Bare Bones program that takes as input a value for X and places 4 times the valueof X into the value of Z. The value of X should be unchanged at the end of theprogram. Note that your program should NOT place a value into X to start. You mayassume that the value of X has already been set just before your program runs.
B. Write a Bare Bones program that takes as input two variables X and Y. (Again, assume these values are set before your program begins to execute.) Your program shouldplace a 0 in the variable Z if the variable X is less than or equal to Y, and yourprogram should place a 1 in the variable Z if the variable X is greater than Y.
C. Write a Bare Bones program that takes as input a variable X. (Again, you don’t set thatvalue. It’s just there when you start.) Your program should place into the variable Z thesum of all the integers from 1 to X. You may assume that X is greater than or equal to 1.
D. Here is a Bare Bones program. Using English, tell briefly what this program does. Thatis, describe the function of X and Y that this program calculates and places into Z. Besure to discuss any special cases that may occur.
copy X to Z;
copy Y to W;
while W not 0 do;
decr Z;
decr W;
end;
E. Is the following Bare Bones program self terminating? Remember carefully thedefinition of self terminating.
while X not 0 do;
end;
F. Explain why the following sentence is false: "We don’t know if the problems in NP aresolvable."
G Name a function that is both in P and in NP. (HINT: this problem is easier than you might think.)
H. Is every problem in P practical to solve on a computer? Why or why not?
I. Here are three functions of N. Assume that x^y means x raised to the yth power.
(4*N) + 1
(N^4)
(4^N)
First, tell which of those three functions is considered polynomial.
If you let N be any non-negative integer, any one of these three functions could be larger. Give a value of N for which each of these functions is larger than the others. (Be sure to label your answers clearly.) That is, give a value for N that makes the first function bigger than the other two. Then give a value for N so that the second function bigger than the other two. Finally, give a value for N so that the third function is bigger than the other two.
As N becomes larger, one of the functions begins to grow more quickly than the other two; as N becomes larger and larger, which one of the three is going to be the biggest by far? (Note: feel free to use a spreadsheet or a small program to help you find the answer to this question.)