CSE 2320 - Homework 1

1
CSE 2320 - Homework 1
Total: 100 points
Topics: instruction count, time complexity for loops, good information delivery, .
Reference: ‘Time Complexity for Loops’.
Q1. (45 points) For each of the following pieces of code do all of the following:
- draw the table with these columns: iteration, value of i, values of k, iterations count for k,
values of t, iteration count for t, total repetitions due to k fork and for t loops for one i.
- write the summation (below the table, as in slides)
- write the closed form solution where required. (The summations in the cheat sheet have their
closed form. E.g. for
1 2  3... (n 1)  n
also written as

n
t
t
1
, has closed form:
2
n(n 1)
.
- dominant term (if you could find a closed form for the summation)
- write Θ (Theta) (if you can)
- Use this format:
TABLE
Summation: ……………………………………………………………………….
Closed form solution: ………………………………………………………………
Dominant term: ……………………………………………… Θ (………….)
a) (15 points) Closed form, dominant term and Θ NOT required.
Note to those interested, a closed form and Θ for this summation can be found using the approximation by integrals
(covered in Summation slides).
for(i = 1; i <= N; i=i+1)
for(k = 1; k <= i; k = 2*k)
for(t = 1; t <= N; t = 2*t)
printf("C");
b) (15 points) Closed form, dominant term and Θ required.
for(i = 1; i <= N; i=i+1)
for(k = 1; k <= S; k++)
for(t = 1; t <= i; t++)
printf("D");
2
c) (15 points) Closed form, dominant term and Θ required.
for(i = 1; i <= N; i=i+1){
for(k = 1; k <= N; k++)
for(t = 1; t <= k; t++)
printf("E");
for(k = 1; k <= M; k++)
for(t = 1; t <= k; t++)
printf("F");
}
Q2. (5 points) How many times does this loop iterate? Give the answer as a function of N (you can be off by
+,- a constant, but not by *,/ a constant). (This is NOT a detailed instruction count, but an estimation of the
count of iterations)
for(i=1; i<=N; i=i+7) ;
Q3. (13 points) Give the Theta time complexity and show your work in the best way you can. 5 points will
be given for how easy it is to understand your explanations. Keep in mind that a good explanation is brief but
clear and to the point (may involve math functions/notations, the first few values of a loop variable, a table to
organize the data…).
i = 0;
while (i<=N){
for(t=0, k=1; k<N; t=t+1, k=2*k)
printf("G");
i=i+t;
}
Q4. (15 points) Write code that has the time complexity below and after that show why it has that
complexity (that is, take your code and derive the time complexity for it). The code must have 2 nested loops
(a total of two loops, one nested inside the other) and must NOT be recursive.
T(n) = 1+3
1
+3
2
+3
3
+ … +3
n

Q5. (6 points) Find the dominant terms and write Θ for each of the functions below. (Pay close attention.)
N
3
+ 500N2
+NM + 106 = Θ(………………)
100N
3
+20N2
+15M +5N = Θ(………………)
3
Q6. (16 points) a) (12 points) Run the following pieces of code and see how long they take for N=10, N=100,
N=300. (Also try N=1000). Pay attention to the following and BRIEFLY write your observations (e.g. for each
value of N say: “it ran in less than a second”, “several seconds, minutes”, “I got tired of waiting after this
much time”,…). Remember that you are in the College of Engineering. We do not want novels, we want
information to the point. Therefore make the information stand-out: use a table, bullet points, fewer words
and more numbers. The points will be given for how well the information stands-out. (Your information
stands-out if I glance at it and I can easily see the content.)
- the runtime effect of replacing the ‘res = res+1’ with the ‘print…’ instruction for runtime_increment
and runtime_print.
- how the runtime depends on the value of N for runtime_increment
- how much faster (i.e. for smaller values of N) the runtime_pow becomes too slow.
// run for N = 10, N = 100, N = 1000
void runtime _increment(int N){
int i, k, t, res = 0;
for(i = 1; i <= N; i=i+1)
for(k = 1; k <= i; k++)
for(t = 1; t <= N; t++)
res = res + 1;
}
// run for N = 10, N = 100, N = 300, N = 1000
void runtime _print(int N){
int i, k, t;
for(i = 1; i <= N; i=i+1)
for(k = 1; k <= i; k++)
for(t = 1; t <= N; t++)
printf("A");
}
// run for N = 10, N = 15, N = 20, N = 25, N = 30
void runtime _pow(int N){
int i, res = 0;
for(i = 1; i <= pow(2.0, (double)N); i=i+1)
res = res + 1;
}
b) (4 points) Look at the program below.
Which of the three functions above (runtime_increment, runtime_print and runtime_pow) has the time
complexity ‘closer’ (or more similar) to that of the runtime_rec?
Note that you do not need to compute the time complexity. We did not cover that yet. Use other methods
(e.g. look at the actual time it takes to execute for different values of N and see to which function from above).
4
#include <stdio.h
#include <stdlib.h
#include <math.h
void runtime_rec(int N, char * str){
if (N==0) {
//printf("%s\n", str);
return;
}
str[N-1] = 'L';
runtime_rec(N-1, str);
str[N-1] = 'R';
runtime_rec(N-1, str);
}
int main(int argc, char** argv) {
int N = 0;
char ch;
char str[100];
printf("run for: N = ");
scanf("%d", &N);
str[N] = '\0'; //to use it as a string of length N.
printf("runtime_rec(%d)\n", N);
runtime_rec(N, str);
}
You are NOT required to run this code on omega, but if you choose to do so, since this code uses the math
library, you will need to link the library at compile time:
gcc -o rec main.c –lm
and then run it as usual:
./rec
Write all your answers in a pdf called hw1.pdf. Make sure you use this exact name.
Put your NAME and section at the top of the page.
You can write the answer on paper and scan the paper as a pdf, but make sure your handwriting is neat and
can be read.
 Answer what the question is asking for. For example, a question maybe asking for loop iterations as a function of
input N, you will not get any point for answering detailed instruction count.
 Points will be deducted for not submitting in the proper format.