Problem 2 Motivation In computer science, we often use induction to prove the correctness of a function - that is, we prove formally that the function does what it is supposed to do. This is sometimes called "proving a function." For example, consider the Python function below, which reverses an input string using recursion. def reverse_string(s): |||||| reverse the string s. The first letter becomes the last letter, the second letter becomes the second- args: s, the string to be reversed returns: the reversed string if s == ""; return "" else: return reverse_string(s [1:])+s[0] Here it is in action. reverse_string("CSCI 0200") ¹0020 ICSC' We got the right answer for this input! But...would we get the right answer on every possible input? Let's write a proof which will guarantee that we will.
Problem 2 Motivation In computer science, we often use induction to prove the correctness of a function - that is, we prove formally that the function does what it is supposed to do. This is sometimes called "proving a function." For example, consider the Python function below, which reverses an input string using recursion. def reverse_string(s): |||||| reverse the string s. The first letter becomes the last letter, the second letter becomes the second- args: s, the string to be reversed returns: the reversed string if s == ""; return "" else: return reverse_string(s [1:])+s[0] Here it is in action. reverse_string("CSCI 0200") ¹0020 ICSC' We got the right answer for this input! But...would we get the right answer on every possible input? Let's write a proof which will guarantee that we will.
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
Solve Problem 2 by using an induction.
![Problem 2
Motivation
In computer science, we often use induction to prove the correctness of a function - that is, we prove formally that the function does
what it is supposed to do. This is sometimes called "proving a function." For example, consider the Python function below, which
reverses an input string using recursion.
def reverse_string(s):
||||||
reverse the string s. The first letter becomes the last letter, the second letter becomes the second-
args:
s, the string to be reversed
returns: the reversed string
||||||
if s == "":
return
else:
return reverse_string(s[1:]) + s [0]
Here it is in action.
||||
reverse_string ("CSCI 0200")
¹0020 ICSC'
We got the right answer for this input! But...would we get the right answer on every possible input? Let's write a proof which will
guarantee that we will.
0
C](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F385eb8fb-6648-4df6-8047-4f830c46ad3b%2F7ca56bff-40a0-41b2-ab16-2b883adf027a%2Fckokcln_processed.png&w=3840&q=75)
Transcribed Image Text:Problem 2
Motivation
In computer science, we often use induction to prove the correctness of a function - that is, we prove formally that the function does
what it is supposed to do. This is sometimes called "proving a function." For example, consider the Python function below, which
reverses an input string using recursion.
def reverse_string(s):
||||||
reverse the string s. The first letter becomes the last letter, the second letter becomes the second-
args:
s, the string to be reversed
returns: the reversed string
||||||
if s == "":
return
else:
return reverse_string(s[1:]) + s [0]
Here it is in action.
||||
reverse_string ("CSCI 0200")
¹0020 ICSC'
We got the right answer for this input! But...would we get the right answer on every possible input? Let's write a proof which will
guarantee that we will.
0
C
Transcribed Image Text:Problem Statement
We'll write a string with n characters as $₁8283 · Sn-2Sn-1Sn.
Now we can state the thing we want to prove:
Proposition: For any n E N, the result of calling the function reverse_string on the string $18283
of s, that is, the string SnSn-15n-2 · · S3S2S1.
Prove this claim using induction.
Note: The empty string € is the string with no elements at all; this string is its own reversal.
Sn-2Sn-1Sn is the reversal
Expert Solution
Step 1: Base case and assumption
At the base case, let us consider an empty string and a one letter character.
I.e., when n = 0,
Then s = " "
So, its reverse is " ", which is returned by the function as well by its definition.
Again, when n = 1,
Then s = some single character string, say "a".
Then, its reverse is also "a", which we can write as s[0] + " " = s[0] + reverse_string(" ")
= s[0] + reverse_string(s[1:])
Here, s[1:] = " ", as s is a single character string.
Hence, we see, the function reverses a string for n = 0, 1 successfully.
Let us assume, the function reverses a string of length k for some k > 0.
i.e., let, s = s1s2s3............sk-1sk
[ here each si is some character ]
Then, reverse_string(s) = sksk-1............s3s2s1
Step by step
Solved in 3 steps with 1 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
