Due: November 23, 2015
Note about points. If you submit this by Friday, November 20, at 11:55pm, we will add 10 points to whatever score you receive.
All these questions are to be answered using the CSIF systems. If you use some other system, your answers may differ, and we will grade based on the CSIF systems.
|You must put your answers in a file called “Linux.txt” or “Linux.pdf”. If you need to submit pictures also, put them in files called “Linuxn.ext”, where n is a digit and ext is an appropriate extension. If you call your file(s) anything else, or submit something other than text or a PDF file, we will not grade it and you will get 0!|
Please do either of the two questions. You must pick one; you cannot do part of one and part of the other. In your submission, state which one you have done.
If you do question 4, you must submit a file called “MyProgLab.ext”, where ext is any 3-letter extension. We will not look at the contents of this file; its presence tells us you did the MyProgrammingLab exercises.|
If you do question 5, you must put your answers in a file called “CPL.txt” or “CPL.pdf”. If you call your file(s) anything else, or submit something other than text or a PDF file, we will not grade it and you will get 0!
|You must put your function in a file called “fibs.c”. Do not include the timing function library. If you call your file anything else, or submit something other than a C program (for example, a text or PDF file containing the code), we will not grade it and you will get 0!|
Write a program that takes a single integer command-line argument, n. It prints the first n Fibonacci numbers in two ways. First, it prints them by repeatedly calling a function that computes the Fibonacci numbers iteratively. Second, it prints them by repeatedly calling a function that computes the Fibonacci numbers recursively. For example, to print the first 20 numbers, and time their computation, you would type
fibs 20The output looks like this:
Iterative: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181Put one blank after the word “timing:” in the last two lines, and print the difference in times using the format “%12.6f”.
Recursive: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Iterative timing: 0.000017
Recursive timing: 0.000084
You need to check for three error conditions.
fprintf(stderr, "%s not an integer\n", argv);and exit with exit code 1.
Argument must be a positive integerand exit with exit code 1.
fprintf(stderr, "Usage: %s number\n", argv);and exit with exit code 1.
To do this program, you must write two Fibonacci functions, the first computing a Fibonacci number iteratively and the second, recursively. Here is a prototype for the functions:
int iterfib(int n); /* compute the n-th Fibonacci number iteratively */ int recfib(int n); /* compute the n-th Fibonacci number recursively */These both take an integer argument n and return the nth Fibonacci number. They do not print anything — your main routine should do that!
The comparison of the two routines is to be done based on their time. Timing a routine requires that you obtain the time before calling the routine, then call it, and then obtain the time after the routine returns. Now subtract the first time from the second. To help, we have written two functions. The first function obtains the current time. Its prototype is:
struct timeval *gettime(void);and it returns a structure containing the number of seconds (field tv_sec) and microseconds (field tv_usec) since time 0 (called “the epoch”, it is January 1, 1970, at 12:00:00am). To use this function, you must put this line where you have the other includes:
#include <sys/time.h>The pointer that gettime returns points to a static area in the library. So, each time you call gettime, that changes. This means that if you need to refer to a previous value returned by gettime, be sure to copy it somewhere!
The second function returns the difference between two times in seconds as a double. Its prototype is:
double timediff(struct timeval *t1, struct timeval *t2);and it returns the difference between the second and the first arguments in seconds as a floating point number.
The timing functions are in the object file “timeit.o”, available at ~bishop/ecs30/timeit.o on the CSIF. It is a binary file, and so will only work on the CSIF.
There is also a sample program using the two timing functions. It is available at ~bishop/ecs30/timeex.c on the CSIF. This may help you use those functions. It shows you one way to save the value returned by gettime.
Finally, there is an executable program, reffibs, that will produce the proper output. It is available at ~bishop/ecs30/buggy.c on the CSIF. You can compare your output against it. Remember, though, that the times you get may differ from the times this program gets. Gradebot takes this into account when grading your program.
Also, note the output spacing. There are 2 spaces after the colon in the lines that begin with “Iterative:” and “Recursive:”, and one space after the colon in the lines with “timings:”.
|You must put your corrected program in a file called “buggy.c”. If you call your file anything else, or submit something other than a C program (for example, a text or PDF file containing the code), we will not grade it and you will get 0!|
|You can also obtain a PDF version of this.||Version of November 13, 2015 at 6:46PM|