|
Physics
5  Computer Science I Spring ’11 Midterm 1 Name_________________________
Write
your responses to the following on separate paper.
1. Perform each of the following
conversions:
a.
Convert the binary number 1000001 to decimal.
b.
Convert the decimal number 99 to to binary.
c.
Convert the hexadecimal number FAFA to decimal.
2. Suppose x = 7. What
will each of the following code fragments print to the console?
a.
if ( x
== 7 && x <= 8 ) cout << "blue"; else cout
<< "green";
b.
cout << (x ==
7 || x > 8 ? "blue" : "green");
c.
x == 7 && x
> 7 ? cout << "blue"; : cout << "green";
d.
if(x != 7 || x != 8) cout << "blue";
: cout << "green";
3.
Farmer John wants to write some code to reduce his
herd of 9 cows down to 4 cows, so he cobbles together the following (he’s a
beginner, so he’s made some mistakes):
|
int four == 4, 9cows == 9;
While (int 9cows =! four);
9cows -= 4;
if 9cows = four
cout << "9cows
= ", four;
|
a.
Find all the syntax mistakes.
b.
Farmer John also has a logic error in his design, what
is it?
c.
Fix the code to meet what you think Farmer John’s
intentions might be.
4.
Consider the code fragment below:
|
int n = 10, j = 5;
while(n<70) {
j *= n;
n += 10;
}
cout
<< "n = " << n
<< "j
= " << j;
|
a.
What will this code print to the console? Justify your answer by making a table of
values for the variable values as the programs instructions are executed.
b.
Rewrite the code as an equivalent for loop.
5.
Consider the code shown below:
|
// An implementation of the
Collatz algorithm
#include <iomanip> // defines
setiosflags() and setw()
#include <iostream>
using namespace std;
int main()
{
setiosflags(ios::right); // right-justify the output
int n;
cout << "Enter
a positive integer: ";
cin >> n;
int count
= 0;
do
{ if (n%2
== 0) n /= 2;
else n
= 3*n + 1;
cout << setw(6) << n; // use a field
of 6 columns per number
++count;
if
(count%10 == 0) cout << endl; // prints 10
numbers per line
} while
(n > 1);
cout << "\nThat
sequence has " << count << "
terms.\n";
}
|
a.
If the user inputs 1, what will be printed to the
console?
b.
If the user inputs 13, what will be printed to the
console?
6.
Consider the following complete program:
|
// An implementation of pass by
reference
#include <iostream>
using namespace std;
void swapNums(int &, int &);
int main() {
int a =
10; int b = 20;
swapNums(a, b);
cout << "a
is " << a << " and
b is " << b << endl;
return 0;
}
void swapNums(int &i, int &j) {
int temp
= i;
i = j;
j = temp;
}
|
a.
Describe the parameter list for the function
swapNums.
b.
What does this program print to the console?
c.
Since swapNums() doesn’t return anything, how is
it that the numbers are swapped?
7.
What is the output of the following code?
|
#include <iomanip>
#include <iostream>
using namespace std;
void f(int &, int &);
int main() {
int a
= 124, b = 76;
cout << "\na%b
= " << a%b << "
and b%(a%b) = " << b%(a&b) << endl;
f(a,b);
cout << "\na%b
= " << a%b << "
and b%(a%b) = " << b%(a&b) << endl;
}
void f(int &u, int &v) {
u = u/v;
v = (float)v/u;
cout << "\nu
= " << u << " and
v = " << v << endl;
//u = v/u;
u = (float)v/u;
}
|
8.
Consider the pseudocode for BubbleSort shown
below. Rewrite the code as a C++
function using proper C++ syntax so that a main() function could call BubbleSort(a,8) where a is the array {5,3,1,9,8,2,4,7} and when it’s
done a is the array {1,2,3,4,5,7,8,9}.
BubbleSort(int
a[], int n)
Begin
for i = 1 to n-1
sorted = true
for j = 0 to n-1-i
if a[j] > a[j+1]
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
sorted = false
end for
if sorted
break from i loop
end for
End
9. Consider
the program whose complete code is given below:
|
#include <iostream>
#include <ctime>
using namespace std;
int main() {
clock_t start, end;
long double duration;
int k;
start = clock();
for(int i = 0;i < 100000; i++)
for(int j = 0; j < 100000; j++)
k = i+j;
end=clock();
duration = (long
double)(end-start)/CLOCKS_PER_SEC;
cout << "Ellapsed
time: "<<duration<<endl;
start = clock();
for(int i = 0;i < 100000; i++)
for(int j = 0; j < 100000; j++)
k = i*j;
end=clock();
duration = (long
double)(end-start)/CLOCKS_PER_SEC;
cout << "Ellapsed
time: "<<duration<<endl;
cin.get();
return
0;
}
|
The output of this program, when run on a Dell Optiplex 745 using an
Intel Core2 CPU at 2.13GHz with 3.25 GB of RAM is as follows:
|
Ellapsed time: 9.751
Ellapsed time: 9.719
|
Note: by contrast, running the same code on an Intel Core2Duo CPU E8400 @
3.00 GHz, 3.00 GB of RAM is
|
Ellapsed time: 28.562
Ellapsed time: 28
|
What does this suggest about the time required to do a required to do
a single addition and the time required to do a single multiplication?
10. Write
a program that prompts the user for the radius of a circle and then calls a
function to compute the area and another function to compute the circumference. Use pass by reference. The following template may help:
|
#include <iostream>
using namespace std;
void compute_area(double, double &);
void compute_circumference(double,
double &);
int main() {
// fill in
body here
}
void compute_area(/* enter
parameter list here */) {
// fill in
body here
}
void compute_circumference(/* enter
parameter list here */) {
// fill in
body here
}
|
Physics 5 Computer Science I Spring ’11 Midterm 1 Solutions
1. Perform each of the following
conversions:
a.
Convert the binary number 1000001 to decimal.
SOLN: 26 + 20 =
64 + 1 = 65
b.
Convert the decimal number 99 to binary.
SOLN: 99%2, 49%2, 24%2, 12%2, 6%2,
3%2, 1%2 = 11000112
= 26+25+21+20
= 64+32+2+1 = 99.
c.
Convert the hexadecimal number FAFA to decimal.
SOLN: 15*163+10*162+15*161+10*160
= 15*212+10*28+15*24+10 = 15(212+24)+10(28+1)
= 15(4096+16)+10(65) = 15(4112)+650 = 61680+650 = 62330
2. Suppose x = 7. What
will each of the following code fragments print to the console?
a.
if (
x == 7 && x <= 8 ) cout << "blue"; else
cout << "green";
SOLN: blue
b.
cout << (x ==
7 || x > 8 ? "blue" : "green");
SOLN: blue
c.
x == 7 && x
> 7 ? cout << "blue" : cout << "green";
SOLN: green
d.
if(x != 7 || x != 8) cout <<
"blue" : cout << "green";
SOLN: As it
is, it would be a syntax error which you could fix by changing the colon to a
semicolon, in which case the output would be
bluegreen
3.
Farmer John wants to write some code to reduce his
herd of 9 cows down to 4 cows, so he cobbles together the following (he’s a
beginner, so he’s made some mistakes):
|
int four == 4, 9cows == 9;
While (int 9cows =! four);
9cows -= 4;
if 9cows = four
cout << "9cows
= ", four;
|
a.
Find all the syntax mistakes.
SOLN: (1) The comparison operators “==” in the first line should be changed
to an assignment operators. (2) The
variable name “9cows” is not allowed because it starts with a number. “While”
should not be capitalized in the second line (3) where, also, the “not equal”
sign is backwards (4).
The if statement that starts on line 4 is missing parentheses around the
condition (5), which should use the comparison operator “==” rather than the
assignment operator (6). There is a
comma instead of a stream operator symbol on the last line (7).
b.
Farmer John also has a logic error in his design,
what is it?
SOLN: The while condition will never
be met, so it is an infinite loop.
|
Fix the code
to meet what you think Farmer John’s intentions might be.
int four = 4, cows = 9;
While (int cows != four);
cows -= 1;
if (cows == four)
cout << "9cows
= " << four;
|
4.
Consider the code fragment below:
|
int n = 10, j = 5;
while(n<70) {
j *= n;
n += 10;
}
cout
<< "n = " << n
<< "j
= " << j;
|
|
a.
What will this code print to the console? Justify your answer by making a table of
values for the variable values as the programs instructions are executed.
SOLN: The output is
n = 70j = -694967296,
but who would have thought? The
values of n and j are tabulated at right, and it’s not until the very end
that output is shown and at this point, 3600000000 > 232 = 2147483648, the largest
value for an int that the
compiler allows. The output is
predictable since 232 3600000000 = 694967296
|
|
n
|
j
|
|
10
|
5
|
|
20
|
50
|
|
30
|
1000
|
|
40
|
30000
|
|
50
|
1200000
|
|
60
|
60000000
|
|
70
|
3600000000
|
|
b.
Rewrite the code as an equivalent for loop. SOLN:
|
int n,
j;
for(j
= 5, n = 10; n < 70; j *= n, n+= 10) {};
cout << "n
= " << n
<< " j =
" << j << endl;
|
5.
Consider the code shown below:
|
// An implementation of the
Collatz algorithm
#include <iomanip> // defines
setiosflags() and setw()
#include <iostream>
using namespace std;
int main()
{
setiosflags(ios::right); // right-justify the output
int n;
cout << "Enter
a positive integer: ";
cin >> n;
int count
= 0;
do
{ if (n%2
== 0) n /= 2;
else n
= 3*n + 1;
cout << setw(6) << n; // use a field
of 6 columns per number
++count;
if
(count%10 == 0) cout << endl; // prints 10
numbers per line
} while
(n > 1);
cout << "\nThat
sequence has " << count << "
terms.\n";
}
|
a.
If the user inputs 1, what will be printed to the
console? SOLN:
|
Enter a positive integer: 1
4 2 1
That sequence has 3 terms.
|
b.
If the user inputs 13, what will be printed to the
console? SOLN:
|
Enter a positive integer: 13
40 20 10
5 16 8
4 2 1
That sequence has 9 terms.
|
6.
Consider the following complete program:
|
// An implementation of pass by
reference
#include <iostream>
using namespace std;
void swapNums(int &, int &);
int main() {
int a =
10; int b = 20;
swapNums(a, b);
cout << "a
is " << a << " and
b is " << b << endl;
return 0;
}
void swapNums(int &i, int &j) {
int temp
= i;
i = j;
j = temp;
}
|
a.
Describe the parameter list for the function swapNums().
SOLN:
The parameter list for swapNums() consists of the addresses of two int.
b.
What does this program print to the console?
SOLN: a is 20 and b is 10
c.
Since swapNums() doesn’t return anything, how is
it that the numbers are swapped?
SOLN: The value of the first is put in
a temporary memory location, then the value of the second is assigned to the
memory location of the first. Thirdly,
the value of the first is copied from the temporary memory location to the
memory location of the second.
7.
What is the output of the following code?
|
#include <iomanip>
#include <iostream>
using namespace std;
void f(int &, int &);
int main() {
int a
= 124, b = 76;
cout << "\na%b
= " << a%b << "
and b%(a%b) = " << b%(a%b) << endl;
f(a,b);
cout << "\na%b
= " << a%b << "
and b%(a%b) = " << b%(a%b) << endl;
}
void f(int &u, int &v) {
u = u/v;
v = (float)v/u;
cout << "\nu
= " << u << " and
v = " << v << endl;
u = v/u;
u = (float)v/u;
}
|
SOLN: Let’s thread through the
operations to see what happens.
The int variables a and b are
initialized to 124 and 76, respectively. Since 124 = 1*76+48 and 76 = 1*48 +
28, the output of the second line of the main() function is
a%b = 48
and b%(a%b) = 28
At
this point the values of a
and b are still 124
and 76, respectively, and these values are passed by reference to the
function f which renames
them u and v,
respectively. Then the contents of
memory location at u are replaced
with 124/76 = 1 and contents of the memory location at v are replaced with
(float)v/u = (float)76/1 = 76, so the output at the next line would be
u = 1 and v = 76
The next two lines replace the contents of the memory location of u with v/u = 76 which is repeated with a cast to
float, leading to the value, u = (float)v/u = 76/76 = 1 (so the cast doesn’t matter…) and we’re back to u = 1 and v = 76 . These are the values stored in the memory
locations of a and b when control
returns to the main() function. So a%b = 1%76 = 1 and b%(a%b) asks for the remainder when 76 is
divided by 1, which is 0. So the output of the program is
|
a%b = 48 and b%(a%b) = 28
u = 1 and v = 76
u = 1 and v = 76
a%b =
1 and b%(a%b) = 0
|
8.
Consider the pseudocode for BubbleSort shown
below. Rewrite the code as a C++
function using proper C++ syntax so that a main() function could call BubbleSort(a,8) where a is the array {5,3,1,9,8,2,4,7} and when it’s
done a is the array {1,2,3,4,5,7,8,9}.
BubbleSort(int
a[], int n)
Begin
for i = 1 to n-1
sorted = true
for j = 0 to n-1-i
if a[j] > a[j+1]
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
sorted = false
end for
if sorted
break from i loop
end for
End
SOLN: This can be accomplished through a slight
modification of the template functions swap() and sort() from
FCC++ . Note that bool sorted is
not really needed here, but it may add some efficiency. Also, there are variations on this that
shift indices.
|
template <class T>
void swap(T& x, T& y)
{ T
temp = x;
x = y;
y = temp;
}
template<class T>
void sort(T* a, int n)
{ bool
sorted;
for (int i=1; i < n; i++) {
sorted = true;
for
(int j=0; j < n-i; j++) {
if
(a[j] > a[j+1]) {
swap(a[j],
a[j+1]);
sorted = false;
}
}
if(sorted)
break;
}
//
Invariant: the i largest elements are in the correct locations.
}
|
Similar
syntax explicit for working with an array of int would look like this:
|
void swap(int& x, int& y)
{ int
temp = x;
x = y;
y = temp;
}
void sort(int a[], int n)
{ bool
sorted;
for (int i=1; i < n; i++) {
sorted = true;
for
(int j=0; j < n-i; j++) {
if
(a[j] > a[j+1]) swap(a[j], a[j+1]);
sorted = false;
}
if(sorted)
break;
}
//
Invariant: the i largest elements are in the correct locations.
}
|
So the sequence of arrays is
{5,3,1,9,8,2,4,7}
{3,5,1,9,8,2,4,7}
{3,1,5,9,8,2,4,7}
{3,1,5,8,9,2,4,7}
{3,1,5,8,2,9,4,7}
{3,1,5,8,2,4,9,7}
{3,1,5,8,2,4,7,9}
{1,3,5,8,2,4,7,9}
{1,3,5,2,8,4,7,9}
{1,3,5,2,4,8,7,9}
{1,3,5,2,4,7,8,9}
{1,3,2,5,4,7,8,9}
{1,3,2,4,5,7,8,9}
{1,2,3,4,5,7,8,9}
9. Consider
the program whose complete code is given below:
|
#include <iostream>
#include <ctime>
using namespace std;
int main() {
clock_t start, end;
long double duration;
int k;
start = clock();
for(int i = 0;i < 100000; i++)
for(int j = 0; j < 100000; j++)
k = i+j;
end=clock();
duration = (long
double)(end-start)/CLOCKS_PER_SEC;
cout << "Ellapsed
time: " << duration << endl;
start = clock();
for(int i = 0;i < 100000; i++)
for(int j = 0; j < 100000; j++)
k = i*j;
end=clock();
duration = (long
double)(end-start)/CLOCKS_PER_SEC;
cout << "Ellapsed
time: " << duration << endl;
cin.get();
return
0;
}
|
The output of this
program, when run on a Dell Optiplex 745 using an Intel Core2 CPU at 2.13GHz
with 3.25 GB of RAM is as follows:
|
Ellapsed time: 9.751
Ellapsed time: 9.719
|
Note: by contrast,
running the same code on an Intel Core2Duo CPU E8400 @ 3.00 GHz, 3.00 GB of
RAM is
|
Ellapsed time: 28.562
Ellapsed time: 28
|
Not sure what to make of the contrast in operating hardware , but what does
this suggest about the time required to do a required to do a single addition
and the time required to do a single multiplication?
SOLN: Since the operations take place
within nexted for loops, each of which
will do 105 iterations,
there are 1010 operation performed in each nested loop, meaning the
average time per operation is between 9.7 and 9.8 times 10-10 seconds per
operation, or approximately 10-9 seconds per operation, or looking at it from
the reciprocal point of view, approximately 1 billion operations per seconds.
10. Write
a program that prompts the user for the radius of a circle and then calls a
function to compute the area and another function to compute the
circumference. Use pass by
reference. The following template may
help:
|
#include <iostream>
using namespace std;
void compute_area(double, double &);
void compute_circumference(double,
double &);
int main() {
double
radius, area, circumference;
cout << "\nEnter
the radius of a circle: ";
cin >> radius;
compute_area(radius, area);
compute_circumference(radius,
circumference);
cout << "\nThe
area of the cricle is " << area;
cout << "\nThe
circumference of the circle is " << circumference;
cin.get();
return
0;
}
void compute_area(double r, double & A) {
A = 3.14159*r*r;
}
void compute_circumference(double
r, double & C) {
C = 6.28318*r;
}
|
|