CSC236H5 Lecture Notes - Lecture 7: Concatenation, Substring, Loop Invariant

27 views2 pages
School
Course
Professor

Document Summary

Csc236 tutorial 7: correctness of recursive functions. For all strings u, v, we say that v is the reversal of u, denoted v = ur, if. |u| = |v| 0 i |u| 1, ui = v|u| i 1 where |u| denotes the length of u, and ui is the i-th character of u. We assume that strings are indexed from 0 to the length of the string minus 1. For example, abcde = ( edcba )r. consider the algorithm below that reverses a string u: return u else : L = len ( u ) if l < 2: The goal is to prove that algorithm rev correctly reverses a string. Write pre- and postconditions for the given function rev, and give a precise statement for correctness of rev. Then, show that rev is correct according to your correctness statement.

Get access

Grade+
$40 USD/m
Billed monthly
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers

Related Documents

Related Questions