For the following loops, state whether any dependence exists, and if so, specify the type of dependence,and whether the dependence has a fixed distance. If the distance between every pair of loop iterations thathave a dependence relationship is fixed, we say the dependence has a fixed distance. For instance, the loopfor i = 1, 100 a(i) = a(i+1) has a fixed distance of 1.for i= 1, 100a(i+3) = a(i) + 11.(a) dependence?YES with type –NO(b) fixed dependence distance?YES with distance =NO2.for i= 3, 100a(i) = a(2i-5) + 1(a) dependence?YES with typeNO(b) fixed dependence distance?YES with distance =NO3.for i= 1, 100a(i) = a(i-1) + 1(a) dependence?YES with type -NO(b) fixed dependence distance?YES with distance =NO4.for i= 1, 100a(2i) = a(2i+4) + 1(a) dependence?YES with type –NO(b) fixed dependence distance?YES with distance =NOfor i= 1, 100a (2i) = a(2i-1) + 15.(a) dependence?YES with type –NO(b) fixed dependence distance?YES with distance =NOfor i= 1, 10a(i) = a(25 - i) + 16.(a) dependence?YES with typeNO(b) fixed dependence distance?YES with distance =NO

Answered: For the following loops, state whether…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

100%

For the following loops, state whether any dependence exists, and if so, specify the type of dependence,
and whether the dependence has a fixed distance. If the distance between every pair of loop iterations that
have a dependence relationship is fixed, we say the dependence has a fixed distance. For instance, the loop
for i = 1, 100 a(i) = a(i+1) has a fixed distance of 1.
for i= 1, 100
a(i+3) = a(i) + 1
1.
(a) dependence?
YES with type –
NO
(b) fixed dependence distance?
YES with distance =
NO
2.
for i= 3, 100
a(i) = a(2i-5) + 1
(a) dependence?
YES with type
NO
(b) fixed dependence distance?
YES with distance =
NO
3.
for i= 1, 100
a(i) = a(i-1) + 1
(a) dependence?
YES with type -
NO
(b) fixed dependence distance?
YES with distance =
NO
4.
for i= 1, 100
a(2i) = a(2i+4) + 1
(a) dependence?
YES with type –
NO
(b) fixed dependence distance?
YES with distance =
NO
for i= 1, 100
a (2i) = a(2i-1) + 1
5.
(a) dependence?
YES with type –
NO
(b) fixed dependence distance?
YES with distance =
NO
for i= 1, 10
a(i) = a(25 - i) + 1
6.
(a) dependence?
YES with type
NO
(b) fixed dependence distance?
YES with distance =
NO

Expert Solution

Step 1

The dependence occurs when same element is accessed in any other iteration.

1. for i=1,100

a(i+3)=a(i)+1

in the given loop, the loop starts from writing a(4), The same element will be accessed to write a(7),

a(7)=a(4)+1

(a) There is dependence . The dependence type is inter dependence (dependence between different loop iterations) . The direction is read after write . a(4) is written first, then it is read.

(b) Fixed dependence distance is -3.

2. for i=3,100

a(i)=a(2i-5)+1

Here the loop starts by writing a(3), the same element will be accessed to write a(4)

a(4)=a(8-3)+1

=a(3)+1

(a) There is dependence . The dependence type is inter dependence . The direction is read after write . a(3) is written first, then it is read.

(b) No fixed length dependence

3. for i=1,100

a(i)=a(i-1)+1

loop starts by writing a(1) and then reads it to write a(2).

(a) There is dependence . The dependence type is inter dependence . The direction is read after write . a(1) is written first, then it is read.

(b) Yes, fixed length=-1

Step by step

Solved in 2 steps

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