Fibonacci Sequence Coding using Memoization C PROGRAM HELP: - Create the mfib() function to calculate Fibonacci using memoization - Also create the initMemo() function to clear out memoization table(s) at the beginning of each mfib() run The output of the program will record the relative amount of time required from the start of each function calculation to the end. Note the speed difference between fib and mfib! Turn in your commented program and a screen shot of the execution run of the program. Do not be alarmed as the non-memoization Fibonacci calls take a long time to calculate, especially the higher values. Be patient. It should finish.

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question

How do I complete the code to produce a similar output show in the att

Fibonacci Sequence Coding using Memoization C PROGRAM HELP:

- Create the mfib() function to calculate Fibonacci using memoization

- Also create the initMemo() function to clear out memoization table(s) at the beginning of each mfib() run

The output of the program will record the relative amount of time required from the start of each function calculation to the end.

Note the speed difference between fib and mfib!

Turn in your commented program and a screen shot of the execution run of the program.

Do not be alarmed as the non-memoization Fibonacci calls take a long time to calculate, especially the higher values.

Be patient. It should finish.

 

Given Code: 

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>

// max number of inputs
#define MAX_FIB 200

// result of call to fib function
unsigned long long result;

//loop variable
int i;


// ========================== MEMO DEFINITIONS ==========================

unsigned long long memo[MAX_FIB];     // array to hold computed data values
bool valid[MAX_FIB];                  // array to hold validity of data

// make all entries in the memoization table invalid
void initMemo() {
  // ***** ADD YOUR INITIALIZATION CODE HERE *****
  // ***** ADD YOUR INITIALIZATION CODE HERE *****
  // ***** ADD YOUR INITIALIZATION CODE HERE *****
  // ***** ADD YOUR INITIALIZATION CODE HERE *****
  // ***** ADD YOUR INITIALIZATION CODE HERE *****

  return;
}

// ========================== TIME DEFINITIONS ==========================
// timer functions found in time.h
// time_t is time type
time_t startTime;
time_t stopTime;

// get current time in seconds from some magic date with
// t = time(NULL);
// or
// time(&t);
// where t is of type time_t
//
// get difference in secs between times (t1-t2) with
// d = difftime(t1, t2);
// where d is of type double

// ========================== NAIVE FIB  ==========================

unsigned long long fib(int n) {
  if (n < 1) {
    return 0;
  } else if (n == 1) {
    return 1;

fib of 0 = 0
time taken (sec)
0.000000
fib of 5 = 5
time taken (sec) = 0.000000
fib of 10 = 55
time taken (sec) = 0.000000
fib of 15
610
time taken (sec)
= 0.000000
fib of 20
6765
time taken (sec) = 0.000000
fib of 25
75025
time taken (sec) = 0.000000
fib of 30
time taken (sec)
832040
0.000000
fib of 35
9227465
time taken (sec)
1.000000
fib of 40
102334155
time taken (sec) = 1.000000
fib of 45 = 1134903170
time taken (sec) = 10.000000
fib of 50
12586269025
time taken (sec) =
110.000000
mfib of 201 = 17323038258947941269
time taken (sec) = 197.000000
Transcribed Image Text:fib of 0 = 0 time taken (sec) 0.000000 fib of 5 = 5 time taken (sec) = 0.000000 fib of 10 = 55 time taken (sec) = 0.000000 fib of 15 610 time taken (sec) = 0.000000 fib of 20 6765 time taken (sec) = 0.000000 fib of 25 75025 time taken (sec) = 0.000000 fib of 30 time taken (sec) 832040 0.000000 fib of 35 9227465 time taken (sec) 1.000000 fib of 40 102334155 time taken (sec) = 1.000000 fib of 45 = 1134903170 time taken (sec) = 10.000000 fib of 50 12586269025 time taken (sec) = 110.000000 mfib of 201 = 17323038258947941269 time taken (sec) = 197.000000
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps with 1 images

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY