Question

For each pseudo-code function below (after the next ==== line), write a useful loop invariant capturing correctness for the main loop in each of the following programs and briefly argue initialization, preservation, and termination. EXAMPLE PROBLEM: //Function to return the max of an array A Maximum(array of integers A) Local integer integer m m=0 for i = 1 to n if A[i] > m then m = A[i] end function Maximum EXAMPLE SOLUTION: The loop invariant is m = max(0, max_{1 \leq j \leq i-1} A[j]). INITIALIZATION: at loop body entry, i=1 and m = 0, so m=max(0, max_{1 \leq j \leq i-1}(A[j])=max(0, max_{1 \leq j \leq 0}A[j]). PRESERVATION: if m=max(0, max_{1 \leq j \leq i-1} A[j]), then we have two cases: (1) If condition A[i] > m is true, then assignment m=A[i] makes m=max(0, max_{1 \leq j \leq i} A[j]), (2) Otherwise if condition A[i] > m is false, then m is not assigned a new value and so remains unchanged, yet m=max(0, max_{1 \leq j \leq i} A[j]) since A[i] <= m. In other words, at iteration i A[i] gets included in the calculation of maximum m. Afterwards, incrementing i by 1 in the next iteration restores the invariant. TERMINATION: when the loop terminates, i==n+1, so the invariant implies m=max(0, max_{1 \leq j \leq n}A[j]) as desired. ====================================================================== E1. //Function to return the value of x^2 for x>=1 Square(positive integer x) Local integers integers i,j i=1 j=1 while i \noteq x do j=j + 2i + 1 i=i + 1 end while return j end function Square

Answer #1

Loop invariant is an indermediate value that is true according to the given condition.

So lets see, what is invariant for above problem.

j=1,i=1

x=4

While (i! =x)

LOOP 1, while condituon is TRUE

j= 1+ 2*1+1=4,,//j is the invariant here

i=1+1=2

LOOP 2 while condition is TRUE

j=4+2*2+1=9

i=2+1=3

LOOP 3 while condition is TRUE

j= 9+ 2*3 +1 =16

i=4

LOOP 4, condition fails.

Now, you can se, the condition inside while fails, that is i==x, 4==4, so it comes out of the loop

Also, j=16, that is equal to x^2, that means invariant for this problem holds true as per the function specification.

Hope i helped you.

Arrays, loops, functions: Lotto
Element Repeated Function
Write a function that that takes as parameters an array of ints,
an int value named element, and an int value named end. Return a
bool based on whether the element appears in the array starting
from index 0 and up to but not including the end index.
Generate Random Array
Write a function that takes as parameters an array of integers
and another integer for the size of the array. Create a...

Find the exact number of times (in terms of n) the innermost
statement (X = X + 1) is executed in the following code. That is,
find the final value of X. Then express the total running time in
terms of O( ), Ω( ), or Θ( ) as appropriate.
X = 0;
for k = 1 to n
for j = 1 to n –
k
X = X + 1;
The following program computes and returns...

IN C++ AS SIMPLE AS POSSIBLE ______
Re-write the given function,
printSeriesSquareFifth, to
use a while loop (instead of for).
• The function takes a single integer n as a
parameter
• The function prints a series between 1 and
that parameter, and also prints its result
• The result is calculated by summing the numbers between 1 and
n (inclusive). If a number is divisible by 5, its
square gets added to the result instead.
• The function does not...

(a) Write an algorithm (use pseudo-code) to determine whether a
function
f ∶ Z100 → Z100 is surjective. That is, supply a “Method” to go
with
Input: A function (array) f with f(i) ∈ Z100 for i = 0, 1, . . . ,
99.
Output: Boolean B. B=‘true’ if f is surjective, ‘false’
otherwise.
Try to make your algorithm as efficient as possible.
Do NOT include an implementation of your algorithm in a programming
language.
(b) How many comparisons...

Given the following algorithm, matching each statement to the
correct sequence for complexity analysis.
procedure Alg3(A): A is a list of n integers
1 for i = 1 to n-1 do
2 x=aix=ai
3 j = i − 1
4 while (j ≥≥ 0) do
5 if x≥ajx≥aj then
6 break
7 end if
8 aj+1=ajaj+1=aj
9 j = j − 1
a end while
b aj+1=xaj+1=x
c end for
d return A
The complexity of this algorithm is O(n2)O(n2)...

q : explain the code for a beginner in c what each line do
Question 2. The following code defines an array
size that sums elements of the defined array through the loop.
Analyze the following code, and demonstrate
the type of error if found?
What we can do to make this code function
correctly ?
#include <stdio.h>
#define A 10
int main(int argc, char** argv) {
int Total = 0;
int numbers[A];
for (int i=0; i < A; i++)...

My assignment:
Triplet Template Class Directions:
Define a template class for a generic triplet. The private data
member for the triplet is a generic array with three elements. The
triplet ADT has the following functions:
default constructor
explicit constructor: initialize the data member using
parameters
three accessors (three get functions) which will return the
value of each individual element of the array data member
one mutator (set function) which will assign values to the
data member...

The following algorithm finds the initial substring of y
that can be reversed and found in y. For example,
longestInitialReverseSubstringLength(“aabaa”) = 5, because “aabaa”
is the same string forwards and backwards, so the longest initial
substring that can be reversed and found in the string is “aabaa”.
Also, longestInitialReverseSubstringLength(“bbbbababbabbbbb”) is 6,
because “babbbb” can be found in the string (see color-highlighted
portions of the string), but no longer initial string exists
reversed in any part of the string.
longestInitialReverseSubstringLength(String
y)...

I'm trying to write a nested loop in Mips Assembly that prints
out, for example, if user input x was 5:
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
(spaces in between)
So far my code is :
li $v0, 5 #Ask for integer
syscall
move $t5, $v0
addi $t0, $zero, 0
For1:
slt $t1, $t0, $t5
beq $t1, $zero, Exit
add $s0, $s0, $t0
addi $t0, $t0, 1...

Using the following code perform ALL of the tasks below in
C++:
-------------------------------------------------------------------------------------------------------------------------------------------
Implementation:
Overload input operator>> a bigint in the following
manner: Read in any number of digits [0-9] until a semi colon ";"
is encountered. The number may span over multiple lines. You can
assume the input is valid.
Overload the operator+ so that it adds two bigint together.
Overload the subscript operator[]. It should return the i-th
digit, where i is the 10^i position. So the first...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 8 minutes ago

asked 40 minutes ago

asked 47 minutes ago

asked 58 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago