Computer Science: An Overview (12th Edition)
12th Edition
ISBN: 9780133760064
Author: Glenn Brookshear, Dennis Brylow
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 5, Problem 57CRP
Program Plan Intro
Loop invariant:
A loop invariant is a condition that is automatically “true” instantly previous and instantly next each iteration of a loop.
- It states an approach for achieving a goal; it is exactly the “pre-condition” for implementing the loop’s body, and it is exactly the “post-condition” of what is outputted by executing the loop’s body.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
solve with Matlab
Assignment vs. Equals is important in loops. An assignment is a = b and means assign value
b to variable a. The equals operator is ab results in 1 or yes if they are equal, 0 or no if
they are not.
The final type of loop is a WHILE loop. It requires that a series of operations occur while the
condition applied to a specified variable is correct.
The example syntax is:
i=10;
while i>5
i-i-1
end
Practice Problem: Given the matrix: M-[1 1; 1 3;]; Use loops to determine how many
of the entries are greater than 1 and the location of all qualifying entries (the
corresponding row and column).
This exercise contains a while loop annotated with a pre- and a post-condition and also a loop invariant. Use the loop invariant theorem to prove the
correctness of the loop with respect to the pre- and post-conditions.
[Pre-condition: m is a positive integer, largest = A[1] and i = 1]
while (i + m)
1. i := i +1
2. if A[i] > largest then largest := A[i]
end while
[Post-condition: largest = maximum value of A[1], A[2], ..., A[m]]
loop invariant: I(n) is "largest = maximum value of A[1], A[2],
A[n + 1] and i = n+ 1."
Proof: 1. Basis Property: Select I(0) from the choices below.
O largest = 0.
O largest = the maximum value of A[1] and i = 1.
O largest = the maximum value of A[1].
O largest = the maximum value of A[O + 1] and 0 + 1.
O largest = 1.
O largest =
According to the pre-condition
this statement is true.
Complete the proof by constructing proofs for each of the following: II. Inductive Property, III. Eventual Falsity of Guard, and IV. Correctness of the Post-
Condition. Submit…
x = 1; y = 2; z = 1; n = 5;
while (z
Chapter 5 Solutions
Computer Science: An Overview (12th Edition)
Ch. 5.1 - Prob. 1QECh. 5.1 - Prob. 2QECh. 5.1 - Prob. 3QECh. 5.1 - Suppose the insertion sort as presented in Figure...Ch. 5.2 - A primitive in one context might turn out to be a...Ch. 5.2 - Prob. 2QECh. 5.2 - The Euclidean algorithm finds the greatest common...Ch. 5.2 - Describe a collection of primitives that are used...Ch. 5.3 - Prob. 2QECh. 5.3 - Prob. 3QE
Ch. 5.3 - Prob. 4QECh. 5.4 - Modify the sequential search function in Figure...Ch. 5.4 - Prob. 2QECh. 5.4 - Some of the popular programming languages today...Ch. 5.4 - Suppose the insertion sort as presented in Figure...Ch. 5.4 - Prob. 5QECh. 5.4 - Prob. 6QECh. 5.4 - Prob. 7QECh. 5.5 - What names are interrogated by the binary search...Ch. 5.5 - Prob. 2QECh. 5.5 - What sequence of numbers would be printed by the...Ch. 5.5 - What is the termination condition in the recursive...Ch. 5.6 - Prob. 1QECh. 5.6 - Give an example of an algorithm in each of the...Ch. 5.6 - List the classes (n2), (log2n), (n), and (n3) in...Ch. 5.6 - Prob. 4QECh. 5.6 - Prob. 5QECh. 5.6 - Prob. 6QECh. 5.6 - Prob. 7QECh. 5.6 - Suppose that both a program and the hardware that...Ch. 5 - Prob. 1CRPCh. 5 - Prob. 2CRPCh. 5 - Prob. 3CRPCh. 5 - Select a subject with which you are familiar and...Ch. 5 - Does the following program represent an algorithm...Ch. 5 - Prob. 6CRPCh. 5 - Prob. 7CRPCh. 5 - Prob. 8CRPCh. 5 - What must be done to translate a posttest loop...Ch. 5 - Design an algorithm that when given an arrangement...Ch. 5 - Prob. 11CRPCh. 5 - Design an algorithm for determining the day of the...Ch. 5 - What is the difference between a formal...Ch. 5 - Prob. 14CRPCh. 5 - Prob. 15CRPCh. 5 - The following is a multiplication problem in...Ch. 5 - Prob. 17CRPCh. 5 - Four prospectors with only one lantern must walk...Ch. 5 - Starting with a large wine glass and a small wine...Ch. 5 - Two bees, named Romeo and Juliet, live in...Ch. 5 - What letters are interrogated by the binary search...Ch. 5 - The following algorithm is designed to print the...Ch. 5 - What sequence of numbers is printed by the...Ch. 5 - Prob. 24CRPCh. 5 - What letters are interrogated by the binary search...Ch. 5 - Prob. 26CRPCh. 5 - Identity the termination condition in each of the...Ch. 5 - Identity the body of the following loop structure...Ch. 5 - Prob. 29CRPCh. 5 - Design a recursive version of the Euclidean...Ch. 5 - Prob. 31CRPCh. 5 - Identify the important constituents of the control...Ch. 5 - Identify the termination condition in the...Ch. 5 - Call the function MysteryPrint (defined below)...Ch. 5 - Prob. 35CRPCh. 5 - Prob. 36CRPCh. 5 - Prob. 37CRPCh. 5 - The factorial of 0 is defined to be 1. The...Ch. 5 - a. Suppose you must sort a list of five names, and...Ch. 5 - The puzzle called the Towers of Hanoi consists of...Ch. 5 - Prob. 41CRPCh. 5 - Develop two algorithms, one based on a loop...Ch. 5 - Design an algorithm to find the square root of a...Ch. 5 - Prob. 44CRPCh. 5 - Prob. 45CRPCh. 5 - Design an algorithm that, given a list of five or...Ch. 5 - Prob. 47CRPCh. 5 - Prob. 48CRPCh. 5 - Prob. 49CRPCh. 5 - Prob. 50CRPCh. 5 - Prob. 51CRPCh. 5 - Does the loop in the following routine terminate?...Ch. 5 - Prob. 53CRPCh. 5 - Prob. 54CRPCh. 5 - The following program segment is designed to find...Ch. 5 - a. Identity the preconditions for the sequential...Ch. 5 - Prob. 57CRPCh. 5 - Prob. 1SICh. 5 - Prob. 2SICh. 5 - Prob. 3SICh. 5 - Prob. 4SICh. 5 - Prob. 5SICh. 5 - Is it ethical to design an algorithm for...Ch. 5 - Prob. 7SICh. 5 - Prob. 8SI
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- A={w ∈{0, 1}* | w starts with a symbol and ends with the other symbol} The state diagram for an NFA?arrow_forwardDetermine the loop invariant of the code written then prove that the loop invariant holds on Initialization, Maintainance and Termination.arrow_forwardWrite the steps number 1-8 like thisarrow_forward
- course (discrete structures) Recall question 2 from Tutorial 3 (Pigeon-Hole Principle), where we have a round-robin chess tournament for 150 players, each of whom play 7 games. We showed that since there are 20 possible first moves for White and 20 possible first moves for Black in response, that there must be two different games in the tournament that begin with the same first two moves. For which of the following changes would this result still be true? Question 1 options: a) each player played 6 games instead of 7 b) each player played 8 games instead of 7 c) there were 200 players instead of 150 (and each played 7 games) d) there were 100 players instead of 150 (and each played 7 games)arrow_forwardAnswer as much as you canarrow_forwardPlease calculate the cyclomatic complexity metric V(G) in three different ways based on the following program flow graph: 2 5 8 10 11 12 13 14arrow_forward
- QUESTION 3 Examine the following loop segment Prove that it is correct by proving the invariant Q Q:j = x - i // returns the value of (x-y) given non- negative integers x, y local variables: integers i,j i=0 j= x while iy do j=j-1 i= l+1 end while //j now has the value of (x - y) return jarrow_forwardConstruct a DFA based on the followingarrow_forwardUsing the rules of the Hoare calculus, show the partial correctness of the following program given the pre- and post-conditions. The invariance of the loop is given. For each rule application, also specify the name of the rule used. {P} n20 i- 0: k:= -1; y:0; (1) y-i'A k-2i -1aisn while iarrow_forwardarrow_back_iosSEE MORE QUESTIONSarrow_forward_ios
Recommended textbooks for you
C++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology Ptr
Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:Cengage
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr
Programming Logic & Design Comprehensive
Computer Science
ISBN:9781337669405
Author:FARRELL
Publisher:Cengage