DIGITAL NOTES

ON
DESIGN AND ANALYSIS OF ALGORITHMS

[Link] II YEAR - II SEM

(2023-24)

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

MALLA REDDY ENGINEERING COLLEGE

 MODULE III: Dynamic Programming and Optimization Techniques

A: Dynamic Programming - General method, applications-Matrix chain

multiplication, Optimal binary searchtrees,0/1 knapsack problem, Longest
Common Subsequence.

B: Optimization Techniques- All pairs shortest path problem, travelling sales

person problem, Reliability design.

Dynamic Programming:
Dynamic programming is a technique that breaks the problems into sub-problems, and
saves the result for future purposes so that we do not need to compute the result again.
The sub-problems are optimized to optimize the overall solution is known as optimal
substructure property. The main use of dynamic programming is to solve optimization
problems. Here, optimization problems mean that when we are trying to find out the
minimum or the maximum solution of a problem. The dynamic programming
guarantees to find the optimal solution of a problem if the solution exists.

The definition of dynamic programming says that it is a technique for solving a

complex problem by first breaking into a collection of simpler sub-problems, solving
each sub-problem just once, and then storing their solutions to avoid repetitive
computations.

Let's understand this approach through an example.

Consider an example of the Fibonacci series. The following series is the Fibonacci
series:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…

The numbers in the above series are not randomly calculated. Mathematically, we
could write each of the terms using the below formula:

F(n) = F(n-1) + F(n-2),

With the base values F(0) = 0, and F(1) = 1. To calculate the other numbers, we follow
the above relationship. For example, F(2) is the sum f(0) and f(1), which is equal to 1.

How can we calculate F(20)?

The F(20) term will be calculated using the nth formula of the Fibonacci series. The
below figure shows that how F(20) is calculated.
As we can observe in the above figure that F(20) is calculated as the sum of F(19) and
F(18). In the dynamic programming approach, we try to divide the problem into the
similar sub-problems. We are following this approach in the above case where F(20)
into the similar sub-problems, i.e., F(19) and F(18). If we recap the definition of
dynamic programming that it says the similar sub-problem should not be computed
more than once. Still, in the above case, the sub-problem is calculated twice. In the
above example, F(18) is calculated two times; similarly, F(17) is also calculated twice.
However, this technique is quite useful as it solves the similar sub-problems, but we
need to be cautious while storing the results because we are not particular about
storing the result that we have computed once, then it can lead to a wastage of
resources.

In the above example, if we calculate the F(18) in the right subtree, then it leads to the
tremendous usage of resources and decreases the overall performance.

The solution to the above problem is to save the computed results in an array. First, we
calculate F(16) and F(17) and save their values in an array. The F(18) is calculated by
summing the values of F(17) and F(16), which are already saved in an array. The
computed value of F(18) is saved in an array. The value of F(19) is calculated using
the sum of F(18), and F(17), and their values are already saved in an array. The
computed value of F(19) is stored in an array. The value of F(20) can be calculated by
adding the values of F(19) and F(18), and the values of both F(19) and F(18) are stored
in an array. The final computed value of F(20) is stored in an array.

How does the dynamic programming approach work?

The following are the steps that the dynamic programming follows:

o It breaks down the complex problem into simpler sub-problems.

 o It finds the optimal solution to these sub-problems.
o It stores the results of sub-problems (memorization). The process of storing the
results of sub-problems is known as memorization.
o It reuses them so that same sub-problem is not calculated more than once.
o Finally, calculate the result of the complex problem.

The above five steps are the basic steps for dynamic programming. The dynamic
programming is applicable that are having properties such as:

Those problems that are having overlapping subproblems and optimal substructures.
Here, optimal substructure means that the solution of optimization problems can be
obtained by simply combining the optimal solution of all the subproblems.

In the case of dynamic programming, the space complexity would be increased as we

are storing the intermediate results, but the time complexity would be decreased.

Approaches of dynamic programming

There are two approaches to dynamic programming:

o Top-down approach
o Bottom-up approach

Top-down approach
The top-down approach follows the memorization technique, while bottom-up
approach follows the tabulation method. Here memorization is equal to the sum of
recursion and caching. Recursion means calling the function itself, while caching
means storing the intermediate results.

Advantages

o It is very easy to understand and implement.

o It solves the sub-problems only when it is required.
o It is easy to debug.

Disadvantages
It uses the recursion technique that occupies more memory in the call stack.
Sometimes when the recursion is too deep, the stack overflow condition will occur.

It occupies more memory that degrades the overall performance.

 Let's understand dynamic programming through an example.

1. int fib(int n)
2. {
3. if(n<0)
4. error;
5. if(n==0)
6. return 0;
7. if(n==1)
8. return 1;
9. sum = fib(n-1) + fib(n-2);
10. }

In the above code, we have used the recursive approach to find out the Fibonacci
series. When the value of 'n' increases, the function calls will also increase, and
computations will also increase. In this case, the time complexity increases
exponentially, and it becomes 2n.

One solution to this problem is to use the dynamic programming approach. Rather than
generating the recursive tree again and again, we can reuse the previously calculated
value. If we use the dynamic programming approach, then the time complexity would
be O(n).

When we apply the dynamic programming approach in the implementation of the

Fibonacci series, then the code would look like:

1. static int count = 0;

2. int fib(int n)
3. {
4. if(memo[n]!= NULL)
5. return memo[n];
6. count++;
7. if(n<0)
8. error;
9. if(n==0)
10. return 0;
11. if(n==1)
12. return 1;
13. sum = fib(n-1) + fib(n-2);
14. memo[n] = sum;
15. }

In the above code, we have used the memorization technique in which we store the
results in an array to reuse the values. This is also known as a top-down approach in
which we move from the top and break the problem into sub-problems.

Bottom-Up approach
The bottom-up approach is also one of the techniques which can be used to implement
the dynamic programming. It uses the tabulation technique to implement the dynamic
programming approach. It solves the same kind of problems but it removes the
recursion. If we remove the recursion, there is no stack overflow issue and no overhead
of the recursive functions. In this tabulation technique, we solve the problems and
store the results in a matrix.

The bottom-up is the approach used to avoid the recursion, thus saving the memory
space. The bottom-up is an algorithm that starts from the beginning, whereas the
recursive algorithm starts from the end and works backward. In the bottom-up
approach, we start from the base case to find the answer for the end. As we know, the
base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from
the base cases, so we will start from 0 and 1.

Key points

o We solve all the smaller sub-problems that will be needed to solve the larger
sub-problems then move to the larger problems using smaller sub-problems.
o We use for loop to iterate over the sub-problems.
o The bottom-up approach is also known as the tabulation or table filling method.

Let's understand through an example.

Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions,
respectively shown as below:
 Since the bottom-up approach starts from the lower values, so the values at a[0] and
a[1] are added to find the value of a[2] shown as below:

The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown
as below:

The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown
as below:

The value of a[5] will be calculated by adding the values of a[4] and a[3], and it
becomes 5 shown as below:

The code for implementing the Fibonacci series using the bottom-up approach is given
below:

1. int fib(int n)
2. {
3. int A[];
4. A[0] = 0, A[1] = 1;
5. for( i=2; i<=n; i++)
6. {
7. A[i] = A[i-1] + A[i-2]
8. }
9. return A[n];
10. }

In the above code, base cases are 0 and 1 and then we have used for loop to find other
values of Fibonacci series.

Let's understand through the diagrammatic representation.

Initially, the first two values, i.e., 0 and 1 can be represented as:

When i=2 then the values 0 and 1 are added shown as below:

When i=3 then the values 1and 1 are added shown as below:

When i=4 then the values 2 and 1 are added shown as below:
When i=5, then the values 3 and 2 are added shown as below:

In the above case, we are starting from the bottom and reaching to the top.

Applications:

[Link] chain multiplication

[Link] Binary search tree

3.0/1 Knapsack problem

[Link] common subsequence

 Matrix Chain Multiplication:
It is a Method under Dynamic Programming in which previous output is taken as input for
next. Here, Chain means first matrix's column is equal to the second matrix's row [always].

In general:

If A = ⌊aij⌋ is a p x q matrix
B = ⌊bij⌋ is a q x r matrix
C = ⌊cij⌋ is a p x r matrix

Then

Given following matrices {A1,A2,A3,...An} and we have to perform the matrix multiplication,
which can be accomplished by a series of matrix multiplications

A1 xA2 x,A3 x.....x An

Matrix Multiplication operation is associative in nature rather commutative. By this, we

mean that we have to follow the above matrix order for multiplication but we are free
to parenthesize the above multiplication depending upon our need.

In general, for 1≤ i≤ p and 1≤ j ≤ r

It can be observed that the total entries in matrix 'C' is 'pXr' as the matrix is of dimension p x
r Also each entry takes O (q) times to compute, thus the total time to compute all possible
entries for the matrix 'C' which is a multiplication of 'A' and 'B' is proportional to the product
of the dimension p q r.

It is also noticed that we can save the number of operations by reordering the parenthesis.

Example1: Let us have 3 matrices, A1,A2,A3 of order (10 x 100), (100 x 5) and (5 x 50)
respectively.

Three Matrices can be multiplied in two ways i.e.,(N-1) ways where N=no of matrices:

1. A1,(A2,A3): First multiply (A2 and A3) then multiply resultant with A1.
2. (A1,A2),A3: First multiply (A1 and A2) then multiply resultant withA3.

No of Scalar multiplication in Case 1 will be:

1. (100 x 5 x 50) + (10 x 100 x 50) = 25000 + 50000 = 75000

 No of Scalar multiplication in Case 2 will be:

1. (100 x 10 x 5) + (10 x 5 x 50) = 5000 + 2500 = 7500

To find the best possible way to calculate the product, we could simply parenthesis the
expression in every possible fashion and count each time how many scalar multiplication are
required.

Matrix Chain Multiplication Problem can be stated as "find the optimal parenthesization
of a chain of matrices to be multiplied such that the number of scalar multiplication is
minimized".

Number of ways for parenthesizing the matrices:

There are very large numbers of ways of parenthesizing these matrices. If there are n items,
there are (n-1) ways in which the outer most pair of parenthesis can place.

(A1) (A2,A3,A4,................An)
Or (A1,A2) (A3,A4 .................An)
Or (A1,A2,A3) (A4 ...............An)
........................

Or(A1,A2,A3.............An-1) (An)

It can be observed that after splitting the kth matrices, we are left with two parenthesized
sequence of matrices: one consist 'k' matrices and another consist 'n-k' matrices.

Now there are 'L' ways of parenthesizing the left sublist and 'R' ways of parenthesizing the
right sublist then the Total will be L.R:

Dynamic Programming Approach:

Let Ai,j be the result of multiplying matrices i through j. It can be seen that the dimension of
Ai,j is pi-1 x pj matrix.

Dynamic Programming solution involves breaking up the problems into subproblems whose
solution can be combined to solve the global problem.

At the greatest level of parenthesization, we multiply two matrices

A1.....n=A1....k x Ak+1....n)

Thus we are left with two questions:

 o How to split the sequence of matrices?
o How to parenthesize the subsequence A1.....k andAk+1......n?

One possible answer to the first question for finding the best value of 'k' is to check all
possible choices of 'k' and consider the best among them. But that it can be observed that
checking all possibilities will lead to an exponential number of total possibilities. It can also
be noticed that there exists only O (n2 ) different sequence of matrices, in this way do not
reach the exponential growth.

Step1: Structure of an optimal parenthesization: Our first step in the dynamic paradigm is
to find the optimal substructure and then use it to construct an optimal solution to the
problem from an optimal solution to subproblems.

Let Ai....j where i≤ j denotes the matrix that results from evaluating the product

Ai Ai+1....Aj.

If i < j then any parenthesization of the product Ai Ai+1 ......Aj must split that the product
between Ak and Ak+1 for some integer k in the range i ≤ k ≤ j. That is for some value of k, we
first compute the matrices Ai.....k & Ak+1....j and then multiply them together to produce the
final product Ai....j. The cost of computing Ai....k plus the cost of computing Ak+1....j plus the
cost of multiplying them together is the cost of parenthesization.

Step 2: A Recursive Solution: Let m [i, j] be the minimum number of scalar multiplication
needed to compute the matrix Ai....j.

If i=j the chain consist of just one matrix Ai....i=Ai so no scalar multiplication are necessary to
compute the product. Thus m [i, j] = 0 if i=j.

If i<j we assume that to optimally parenthesize the product we split it between A k and
Ak+1 where i≤ k <j. Then m [i,j] equals the minimum cost for computing the subproducts
Ai....k and Ak+1....j+ cost of multiplying them together. We know Ai has dimension pi-1 x pi, so
computing the product Ai....k and Ak+1....j takes pi-1 pk pj scalar multiplication, we obtain

m [i,j] = m [i, k] + m [k + 1, j] + pi-1 pk pj

There are only (j-1) possible values for 'k' namely k = i, i+1.....j-1. Since the optimal
parenthesization must use one of these values for 'k' we need to check them all to find the
best.

So the minimum cost of parenthesizing the product Ai Ai+1......Aj becomes

To construct an optimal solution, let us define s [i,j] to be the value of 'k' at which we can
split the product Ai Ai+1 .....Aj To obtain an optimal parenthesization i.e. s [i, j] = k such that

m [i,j] = m [i, k] + m [k + 1, j] + pi-1 pk pj

Optimal Binary Search Tree (OBST):

An Optimal Binary Search Tree (OBST), also known as a Weighted Binary Search Tree, is
a binary search tree that minimizes the expected search cost. In a binary search tree, the
search cost is the number of comparisons required to search for a given key.
In an OBST, each node is assigned a weight that represents the probability of the key
being searched for. The sum of all the weights in the tree is 1.0. The expected search cost
of a node is the sum of the product of its depth and weight, and the expected search cost of
its children.
To construct an OBST, we start with a sorted list of keys and their probabilities. We then
build a table that contains the expected search cost for all possible sub-trees of the original
list. We can use dynamic programming to fill in this table efficiently. Finally, we use this
table to construct the OBST.
The time complexity of constructing an OBST is O(n^3), where n is the number of keys.
However, with some optimizations, we can reduce the time complexity to O(n^2). Once
the OBST is constructed, the time complexity of searching for a key is O(log n), the same
as for a regular binary search tree.
The OBST is a useful data structure in applications where the keys have different
probabilities of being searched for. It can be used to improve the efficiency of searching
and retrieval operations in databases, compilers, and other computer programs.
Given a sorted array key [0.. n-1] of search keys and an array freq[0.. n-1] of frequency
counts, where freq[i] is the number of searches for keys[i]. Construct a binary search tree
of all keys such that the total cost of all the searches is as small as possible.
Let us first define the cost of a BST. The cost of a BST node is the level of that node
multiplied by its frequency. The level of the root is 1.

Examples:
Input: keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs
10 12
\ /
12 10
I II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118

Input: keys[] = {10, 12, 20}, freq[] = {34, 8, 50}

There can be following possible BSTs
10 12 20 10 20
\ / \ / \ /
12 10 20 12 20 10
\ / / \
20 10 12 12
I II III IV V
Among all possible BSTs, cost of the fifth BST is minimum.
Cost of the fifth BST is 1*50 + 2*34 + 3*8 = 142
0/1 Knapsack problem:
Here knapsack is like a container or a bag. Suppose we have given some items which
have some weights or profits. We have to put some items in the knapsack in such a
way total value produces a maximum profit.

For example, the weight of the container is 20 kg. We have to select the items in such
a way that the sum of the weight of items should be either smaller than or equal to the
weight of the container, and the profit should be maximum.

There are two types of knapsack problems:

o 0/1 knapsack problem

o Fractional knapsack problem

We will discuss both the problems one by one. First, we will learn about the 0/1
knapsack problem.
What is the 0/1 knapsack problem?
The 0/1 knapsack problem means that the items are either completely or no items are
filled in a knapsack. For example, we have two items having weights 2kg and 3kg,
respectively. If we pick the 2kg item then we cannot pick 1kg item from the 2kg item
(item is not divisible); we have to pick the 2kg item completely. This is a 0/1 knapsack
problem in which either we pick the item completely or we will pick that item. The 0/1
knapsack problem is solved by the dynamic programming.

.
Longest Common Subsequence:

Here longest means that the subsequence should be the biggest one. The common means that
some of the characters are common between the two strings. The subsequence means that
some of the characters are taken from the string that is written in increasing order to form a
subsequence.

Let's understand the subsequence through an example.

Suppose we have a string 'w'.

W1 = abcd

The following are the subsequences that can be created from the above string:

o ab
o bd
o ac
o ad
o acd
o bcd

The above are the subsequences as all the characters in a sub-string are written in increasing
order with respect to their position. If we write ca or da then it would be a wrong
subsequence as characters are not appearing in the increasing order. The total number of
subsequences that would be possible is 2n, where n is the number of characters in a string. In
the above string, the value of 'n' is 4 so the total number of subsequences would be 16.

W2= bcd

By simply looking at both the strings w1 and w2, we can say that bcd is the longest common
subsequence. If the strings are long, then it won't be possible to find the subsequence of both
the string and compare them to find the longest common subsequence.

Finding LCS using dynamic programming with the help of a table.

Consider two strings:

X= a b a a b a

Y= b a b b a b

(a, b)

For index i=1, j=1

Since both the characters are different so we consider the maximum value. Both contain the
same value, i.e., 0 so put 0 in (a,b). Suppose we are taking the 0 value from 'X' string, so we
put arrow towards 'a' as shown in the above table.

(a, a)

For index i=1, j=2

Both the characters are the same, so the value would be calculated by adding 1 and upper
diagonal value. Here, upper diagonal value is 0, so the value of this entry would be (1+0)
equal to 1. Here, we are considering the upper diagonal value, so the arrow will point
diagonally.

(a, b)

For index i=1, j=3

Since both the characters are different so we consider the maximum value. The character 'a'
has the maximum value, i.e., 1. The new entry, i.e., (a, b) will contain the value 1 pointing to
the 1 value.
(a, b)

For index i=1, j=4

Since both the characters are different so we consider the maximum value. The character 'a'
has the maximum value, i.e., 1. The new entry, i.e., (a, b) will contain the value 1 pointing to
the 1 value.

(a, a)

For index i=1, j=5

Both the characters are same so the value would be calculated by adding 1 and upper
diagonal value. Here, upper diagonal value is 0 so the value of this entry would be (1+0)
equal to 1. Here, we are considering the upper diagonal value so arrow will point diagonally.

(a, b)

For index i=1, j=6

Since both the characters are different so we consider the maximum value. The character 'a'
has the maximum value, i.e., 1. The new entry, i.e., (a, b) will contain the value 1 pointing to
the 1 value.

(b, b)

For index i=2, j=1

Both the characters are same so the value would be calculated by adding 1 and upper
diagonal value. Here, upper diagonal value is 0 so the value of this entry would be (1+0)
equal to 1. Here, we are considering the upper diagonal value so arrow will point diagonally.

(b, a)

For index i=2, j=2

Since both the characters are different so we consider the maximum value. The character 'a'
has the maximum value, i.e., 1. The new entry, i.e., (a, b) will contain the value 1 pointing to
the 1 value.

In this way, we will find the complete table. The final table would be:
In the above table, we can observe that all the entries are filled. Now we are at the last cell
having 4 value. This cell moves at the left which contains 4 value.; therefore, the first
character of the LCS is 'a'.

The left cell moves upwards diagonally whose value is 3; therefore, the next character is 'b'
and it becomes 'ba'. Now the cell has 2 value that moves on the left. The next cell also has 2
value which is moving upwards; therefore, the next character is 'a' and it becomes 'aba'.

The next cell is having a value 1 that moves upwards. Now we reach the cell (b, b) having
value which is moving diagonally upwards; therefore, the next character is 'b'. The final
string of longest common subsequence is 'baba'.

Why a dynamic programming approach in solving a LCS problem is more efficient

than the recursive algorithm?

If we use the dynamic programming approach, then the number of function calls are reduced.
The dynamic programming approach stores the result of each function call so that the result
of function calls can be used in the future function calls without the need of calling the
functions again.

In the above dynamic algorithm, the results obtained from the comparison between the
elements of x and the elements of y are stored in the table so that the results can be stored for
the future computations.

The time taken by the dynamic programming approach to complete a table is O(mn) and the
time taken by the recursive algorithm is 2max(m, n).

Optimization techniques:
All pairs shortest path problem:

In the all pairs shortest path problem, we have to find a shortest path between every pair of
vertices in a directed graph G. That is, for every pair of vertices (i, j), we have to find a
shortest path from i to j as well as one from j to i. These two paths are same when G is
undirected.
When no edge has a negative length, the all-pairs shortest path problem may be solved by
using Dijkstra’s greedy single source algorithm ‘n’ times, once with each of the n vertices as
the source vertex.

The all pairs shortest path problem is to determine a matrix A such that A (i, j) is the length
of a shortest path from i to j. The matrix A can be obtained by solving n single-source
problems using the algorithm shortest Paths. Since each application of this procedure
requires O (n2) time, the matrix A can be obtained in O (n3) time. All The dynamic
programming solution, called Floyd’s algorithm, runs in O (n 3) time. Floyd’s algorithm
works even when the graph has negative length edges (provided there are no negative length
cycles).

The shortest i to j path in G, i ≠ j originates at vertex i and goes through some intermediate
vertices (possibly none) and terminates at vertex j. If k is an intermediate vertex on this
shortest path, then the subpaths from i to k and from k to j must be shortest paths from i to k
and k to j, respectively. Otherwise, the i to j path is not of minimum length. So, the principle
of optimality holds. Let Ak (i, j) represent the length of a shortest path from i to j going
through no vertex of index greater than k, we obtain:

Ak (i, j) = min {Ak-1 (i, k) + Ak-1 (k, j), Ak-1 (i,j)} 1<=k<=n

Example 1:

Given a weighted digraph G = (V, E) with weight. Determine the length of the shortest path
between all pairs of vertices in G. Here we assume that there are no cycles with zero or
negative cost.

General formula: Ak (i, j) = min {Ak-1 (i, k) + Ak-1 (k, j), Ak-1 (i,j)} 1<=k<=n

Solve the problem for different values of k = 1, 2 and 3

A3 gives all pairs shortest path from all the vertices
Reliability design:
The reliability design problem is the designing of a system composed of several devices
connected in series or parallel. Reliability means the probability to get the success of the
device.
Let’s say, we have to set up a system consisting of D1, D2, D3, …………, and Dn devices,
each device has some costs C1, C2, C3, …….., Cn. Each device has a reliability of 0.9 then
the entire system has reliability which is equal to the product of the reliabilities of all
devices i.e., πri = (0.9)4=0.6561

Serial Combination of one copy of each device

It means that 35% of the system has a chance to fail, due to the failure of any one device.
the problem is that we want to construct a system whose reliability is maximum. How it
can be done so? we can think that we can take more than one copy of each device so that if
one device fails we can use the copy of that device, which means we can connect the
devices parallel. When the same type of 3 devices is connected parallel in stage 1 having a
reliability 0.9 each then:
Reliability of device1, r 1= 0.9
The probability that device does not work well = 1 – r1 = 1 – 0.9 = 0.1
The probability that all three copies failed = ( 1-r1 )3 = (0.1)3 = 0.001
The Probability that all three copies work properly = 1 – (1- r1)3 = 1- 0.001 = 0.999
We can see that the system with multiple copies of the same device parallel may increase
the reliability of the system.
 Multiple copies of the same device type are connected in parallel through the use of a
switching circuit
The problem is to design a system that is composed of several devices connected inseries.
Let ri be the reliability of device Di (that is ri is the probability that device ‘i’will function
properly) then the reliability of the entire system is 𝝅ri. Even if the individual devices are
very reliable (the ri’s are very close to one), the reliability of the system may not be very
good.

If the stage ‘i’ contains mi copies of devices [Link] the probability that all mi have a
malfunction is (1-ri) [Link] the reliability of stage ‘i’ becomes 1-(1-ri) mi

The reliability of stage‘i’ is given by a function øi(mi).

Our problem is to use device duplication. This maximization is to be carried out under a cost
constraint. Let ci be the cost of each unit of device i and let c be the maximum allowable
cost of the system being designed.

Ui = floor( C – ∑Ci / Ci ) + 1 (1 is added because we have one copy of each device

before)