Proof of Correctness Given the following Algorithms derive their correctness or not by proof 1. of the required invariants (a) Fibonnacci n2 3 and findjib(n) > ((1+ V5)/2)"-2 def find_fib(n): if n-0: return 0 if n - 1: return 1 return find_fib(n-1) + find_fib(n-2)
Proof of Correctness Given the following Algorithms derive their correctness or not by proof 1. of the required invariants (a) Fibonnacci n2 3 and findjib(n) > ((1+ V5)/2)"-2 def find_fib(n): if n-0: return 0 if n - 1: return 1 return find_fib(n-1) + find_fib(n-2)
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...
Related questions
Question
(NOTE: Please provide answer like 1b but do not answer 1b, answer 1a only)
Transcribed Image Text:1.
Proof of Correctness Given the following Algorithms derive their correctness or not by proof
of the required invariants
(a)
Fibonnacci
n2 3 and findjib(n) > ((1+ V5)/2)"-2
def find fib(n):
if n-0: return 0
if n - 1: return 1
return find_fib(n-1) + find_fib(n-2)
(b)
For a >0 and b > 0 ánd a > GCD(a, b)
GCD
def find_gcd(a, b):
while(b):
a, b = b, a % b
return a
Answer:
Proof:
Given : a>0 and b > 0ánd a > GCD(a, b)
If a = 0
Then GCD(a,b) z6
0> b>0 Ealse
So this statement is valid only when a >0 ,b > 0 and a > GCD(a, b)
Under ths condition:
(1) Įf'a = b
Thên GCD(a,b) = a =b
So the given Algorithm is correct.
(2) If a < b
Sample case: a = 24, b = 32
GCD(24,32) = 8
According to the given algorithm:
GCD (a, b)
While: b>0
Looping times a, b (a % b)
return
GCD (24,32)
GCD (32,24)
GCD (24,8)
GCD (8, 0)
a = 32
Yes (b = 32)
Yes (b = 24)
Yes (b = 8)
No (b=0)
1st
a=b=32, b=24%32 =24
a=b=24, b=32%24 =8
a=b=8, b=24%8 =0
a= 24
3rd
a = 8
break
As we can see above, retyn: a = 8, break
So the given Algorithpris correct.
(3) If a > b
Sample case: 35, b = 21
GCD(35,21 7
Accordiag to the given algorithm:
GCD (a, b)
While: b>0
Looping times a,5 (a % b)
return
GCD (35,21)
Yes (b = 21)
Yes (b = 14)
Yes (b = 7)
No (b=0)
1st
a=b=21, b=35%21 =14
a = 21
GCD (21,14)
GCD (14,7)
GCD (7, 0)
2nd
a=b=14, b=21%14 =7
a =14
Зrd
a=b=7, b=14%7 0
a = 7
break
As we can see above, return: a = 7, Kreak
So the given Algorithm is correct
This can be also wrote by úsing Recursion:
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Recommended textbooks for you
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 Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
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 Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
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
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY