For each sample of code given below, indicate precisely how many times each line
ID: 3858422 • Letter: F
Question
For each sample of code given below, indicate precisely how many times each line runs in terms of the variables given. Sometimes, you will be able to give an exact integral answer, like "10". Other times, your answer will be in terms of n or some other variable or combination of variables. If the snippet of code is a method, you do not have to write the number of times the top line (the method declaration itself) is executed
Q1.
double sum_triples(double array[], int n) {//n: size of the array. Assume n is divisible by 3
double sum=0;
for (int i=0; i<n; i=i+3)
sum = sum + array[ i ];
return sum;
}
Q2.
double sum_exponentials(int n){ //n is a power of 3, i.e., n=3^k or k=log n base 3
int sum=0;
for (int i=1; i<n; i=i*3)
sum = sum + i;
return sum;
}
Q3.
for (int i=0; i<n; i++) {
for (int j=n; j>=i; j--)
cout << i << “,” << j <<endl;
}
Q4.
for (int i=0; i<n; i++) { //assume n is divisible by 2 => n = 2*k
for (j=n/2; j>i; j--)
sum = i+j;
}
Q5.
//matrix multiplication of A[m][n] and B[n][p]. The product is saved into C[m][p].
void mult_matricies( double A[][n], double B[][p], double C[][p], int m, int n , int p ){
for (int i=0; i<m; i++) {
for (int j=0; j<p; j++){
C[i][j] = 0;
for ( int k=0; k<n; k++) {
C[i][j] += A[i][k] * B[k][j];
}//for-k
}//for-j
}//for-i
}
For each sample of code given below, indicate precisely how many times each line runs in terms of the variables given. Sometimes, you will be able to give an exact integral answer, like "10". Other times, your answer will be in terms of n or some other variable or combination of variables. If the snippet of code is a method, you do not have to write the number of times the top line (the method declaration itself) is executed.
You are welcome to submit your responses as a PDF file.
Q1.
double sum_triples(double array[], int n) {//n: size of the array. Assume n is divisible by 3
double sum=0;
for (int i=0; i<n; i=i+3)
sum = sum + array[ i ];
return sum;
}
Q2.
double sum_exponentials(int n){ //n is a power of 3, i.e., n=3^k or k=log n base 3
int sum=0;
for (int i=1; i<n; i=i*3)
sum = sum + i;
return sum;
}
Q3.
for (int i=0; i<n; i++) {
for (int j=n; j>=i; j--)
cout << i << “,” << j <<endl;
}
Q4.
for (int i=0; i<n; i++) { //assume n is divisible by 2 => n = 2*k
for (j=n/2; j>i; j--)
sum = i+j;
}
Q5.
//matrix multiplication of A[m][n] and B[n][p]. The product is saved into C[m][p].
void mult_matricies( double A[][n], double B[][p], double C[][p], int m, int n , int p ){
for (int i=0; i<m; i++) {
for (int j=0; j<p; j++){
C[i][j] = 0;
for ( int k=0; k<n; k++) {
C[i][j] += A[i][k] * B[k][j];
}//for-k
}//for-j
}//for-i
}
Explanation / Answer
1) Line 1: double sum_triples(double array[], int n){
Line 2: double sum=0;
Line 3: for (int i=0; i<n; i=i+3)
Line 4: sum = sum + array[ i ];
Line 5: return sum; }
Number of time line will execute
Line 1: 1 time
Line 2: 1time
Line 3: n/3 times(as i is incremented by 3 everytime and n is multiple of 3 )
Line 4: n/3 times(as i is incremented by 3 everytime and n is multiple of 3)
Line 5: 1 time
2)
Line 1 : double sum_exponentials(int n){
Line 2 : Int sum=0;
Line 3 : for (int i=1; i<n; i=i*3)
Line 4 : sum = sum + i;
Line 5 : return sum; }
Number of time line will execute
Line 1: 1 time
Line 2: 1 time
Line 3: (log n base 3) times (as i is incremented by factor of multiple 3 and n is some power of 3 so equating that we get this)
Line 4: (log n base 3) times (as i is incremented by factor of multiple 3 and n is some power of 3 so equating that we get this)
Line 5: 1 time
3)
Line 1 : for (int i=0; i<n; i++) {
Line 2 : for (int j=n; j>=i; j--)
Line 3 : cout << i << “,” << j <<endl;}
Number of time line will execute
Line 1: n times( as loop start from 0 to n)
Line 2: since it is nested loop so its iteration differ according to i
If i=0 this line will execute n times
If i=1 this line will execute n-1 times
If i=2 this line will execute n-2 times
And so on.
Line 3: since it is nested loop so its iteration differ according to i
If i=0 this line will execute n times
If i=1 this line will execute n-1 times
If i=2 this line will execute n-2 times
And so on.
4)
Line 1 : for (int i=0; i<n; i++) {
Line 2 : for (j=n/2; j>i; j--)
Line 3 : sum = i+j;}
Number of time line will execute
Line 1: n time
Line 2: since it is nested loop so its iteration differ according to i
If i=0 this line will execute n/2 times
If i=1 this line will execute (n/2)-1 times
If i=2 this line will execute (n/2)-2 times
And so on.
Line 3: since it is nested loop so its iteration differ according to i
If i=0 this line will execute n/2 times
If i=1 this line will execute (n/2)-1 times
If i=2 this line will execute (n/2)-2 times
And so on.
5)
Line 1 : void mult_matricies( double A[][n], double B[][p], double C[][p], int m,
int n , int p ){
Line 2 : for (int i=0; i<m; i++) {
Line 3 : for (int j=0; j<p; j++){
Line 4 : C[i][j] = 0;
Line 5 : for ( int k=0; k<n; k++) {
Line 6 : C[i][j] += A[i][k] * B[k][j];
Line 7 : }//for-k
Line 8 : }//for-j
Line 9 : }//for-I
Line 10 : }
Number of time line will execute
Line 1: 1 time
Line 2: m times(as value of i change from 0 to m)
Line 3: p times(as value of j change from 0 to p)
Line 4: p times(as value of j change from 0 to p)
Line 5: n times(as value of k change from 0 to n)
Line 6: n times(as value of k change from 0 to n)
Line 7: n times(as value of k change from 0 to n)
Line 8: p times(as value of j change from 0 to p)
Line 9: m times(as value of i change from 0 to m)
Line 10: 1 time
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.