Programming II Time Complexity

 Assignment: Find T(n), f(n), c, and n0 for each of the code fragments given in Figures 1,
2, and 3. Put the results of your analysis in your report in the algorithm
section. Your analysis should be patterned after the analysis in Figure 8.
Transform the code fragment into while-loops. Account for the cost of
each line. Sum the total and express it in closed form.
Write functions af01, af02, and af03 that return T(n) according to your
analysis. Functions af01, af02, and af03 compute T(n) analytically. Model
your design of functions af01, af02, and af03 after example analytical
function af00 shown in Figure 6.
Write functions ef01, ef02, and ef03 that return T(n) by counting the
number of times each statement in the code fragment executes. Functions
ef01, ef02, and ef03 compute T(n) empirically. Mode your design of
functions ef01, ef02, and ef03 after example empirical function ef00 shown
in Figure 7.
Put all functions that compute T(n) in file F09.cpp. Write function
prototypes for each of your functions and put them in file F09.h. Write file
p09.cpp that tests all six functions in file F09.cpp. File p09.cpp contains
function main. Write functions in file p09.cpp that read separate files
containing values of n for each code fragment. Refer to the input section
to determine which files contain data for functions ef01 and af01; ef02 and
af02; and ef03 and af03.
Create file p09make containing instructions for the UNIX utility make that
compile and link program p09.
 
Prohibition: Use of the C++ Standard Template Library is prohibited in the
implementation of this project.
Program Files: Project 9 consists of files p09.cpp, F09.h, F09.cpp, and p09make. Project
file names are exactly as given. Failure to employ the foregoing names will
result in a score of zero (0) for this project
Project files must be stored in the root directory of your student account.
Failure to store project files in the root directory of your student account
will result in a score of zero (0) for this project.
File Description
p09.cpp File p09.cpp contains functions that process command line
arguments and exercise analytical and empirical functions.
F09.h File F09.h defines class f that contains prototypes for
analytical functions af01, af02 and af03, and empirical
functions ef01, ef02 and ef03.
F09.cpp File F09.cpp contains implementations for the functions
whose prototypes are defined in file F09.h. File F09.cpp
can contain functions to support computations performed
by the analytical and empirical functions contained in the
file.
p09make File p09make contains instructions for program p09.
Instructions are written for the UNIX utility make. Program
p09 is contained in file p09.
Command Line: Project 9 can be invoked with zero, one, two, three, or four program
parameters. The first three program parameters are the input file names.
The fourth parameter is the output file name. Sample command lines
together with corresponding actions by program p09 are shown below.
Boldfaced type indicates data entered at the keyboard by the user.
$ p09
Enter the first input file name: i091.dat
Enter the second input file name: i092.dat
Enter the third input file name: i093.dat
Enter the output file name: o09.dat
$ p09 i091.dat
Enter the second input file name: i092.dat
Enter the third input file name: i093.dat
Enter the output file name: o09.dat
$ p09 i091.dat i092.dat
Enter the third input file name: i093.dat
Enter the output file name: o09.dat
$ p09 i091.dat i092.dat i093.dat
Enter the output file name: o09.dat
$ p09 i091.dat i092.dat i093.dat o09.dat
 
Input files: Files i091.dat, i092.dat, and i093.dat contain values of n for code
fragments (1), (2), and (3) respectively. Program p09 reads an input file and
produces output for that file. Program p09 reads input files in succession
and produces output for each input file as the file is read.
Output files: Send your output to both the output file and the display (stdout). Put your
output in three columns. Label the first column n, the second column
Analytical and the third column Empirical. Produce values of T(n) for each
code fragment. One line is printed for each value of n read. Write the value
of n in the column labeled n. Write the value of T(n) computed by the
designated analytical function, af0x, in the column labeled Analytical.
Write the value of T(n) computed by the selected empirical function, ef0x,
in the column titled Empirical. Produce one table for each code fragment.
Identify the tables by the code fragment analyzed. Figure 5 contains the
output for example code fragment 0 shown in Figure 4.
Figure 1.
Code fragment 1.
int sum=1;
for (int a=0;a<n;a++) sum=sum*4;
while (sum0) sum--;
Figure 2.
Code fragment 2.
for (int i=0;i<n;i++) {
int m=n;
while (m1) m=m/4;
}
Figure 3.
Code fragment 3.
int sum=0;
for(int i=0;i<n;i++)
for(int j=0;j<i*i;j++)
for (int k=0;k<j;k++)
 sum++;
Figure 4. Example
Code Fragment 0
int sum=0;
for (int i=0;i<n;i++) sum++;
Figure 5. Example
Output for Code
Fragment 0 n Analytical Empirical
1 3 3
10 33 33
20 63 63
30 93 93
40 123 123
50 153 153
60 183 183
70 213 213
80 243 243
90 273 273
Figure 6.
Analytical Timing
Function af00.
int af01(int n)
{ return 3*n+3;
}
3
Programming II Time Complexity
CMSC 2613 Project p09
Figure 7.
Empirical Code
Function ef00. int ef01(int n)
 
{ int t=0, i, sum;
 sum=0; t++;
 i=0; t++;
 while (i<n) { t++;
 sum++; t++;
 i++; t++;
 } t++;
 return t;
}
Figure 8.
Analysis of Code
Fragment 0 Line Code Cost Reduced Form
1 sum=0; 1 1
2 i=0; 1 1
3 while (i<n) { ?1
????-1
????=0
n
4 sum++; same as line 3 n
5 i++; same as line 3 n
6 } 1 1
T(n)= 3n+3
4
Powered by