Find Out the summation Of the boundary elements Of the array

Find Out the summation Of the boundary elements Of the array


Problem 2.8:

Given a two-dimensional array, find out the summation of the boundary elements of the array. Here no element should be added twice.
Solution:
>>First, we have to identify the boundary elements.

• In a two dimensional array, elements of first column and the last column and the first row and last row are the boundary elements as shown in the Figure-2.8.

>> Here the index, i represents the row number and j represents the column-number.

• When i is 1, the row is the first row and when i is m (where m represents the number of rows in the array), the row is the last row.

• Similarly, when j = 1, the column is the first column and the index of the last column is j = n. So, a number in a two-dimensional array is a boundary element if i = 1, i = m, j = 1 or j = n

The summation Of the boundary elements Of the array

• We shall start from the first number of the array.

• If it is a boundary element, the number will be added to the sum (which is a variable to store the result and initially it is set zero).

• We shall check every number whether it is a boundary element or not, if the number is a boundary element it will be added to sum.

• Otherwise, we shall proceed with the next number of the list (array) and continue the process to the end of the list.

Location of an element

Location of an element of a two-dimensional array
Row-major Order:

• If Loc (A[i, j]) denotes the location in the memory of the element A[i][j] or Aij, then in row-major order –
  

Loc (A[i, j]) = Base (A) + (n (i - 1) + (j - 1)) * w;

• Here Base (A) is starting or base address of the array A, n is the number of columns and w is the width of each cell, i.e, number bytes per cell.

Column-major Order:

In column-major order,

Loc (A[i, j]) = Base (A) + (m (j - 1) + (i - 1)) * w;

Here Base (A) is starting or base address of the array A, m is the number of rows and w is the cell width



Example:
Base address, Base (A) = 100, Size of the array = 5 × 6. If the type of array is integer then find Loc (A[4, 3]).
Solution:
(2 bytes for each integer cell in C/C++)
If the array is stored in row-major order:
Loc (A[4, 3]) = Base (A) + (n (i - 1) + (j - 1))* 2
= 100 + (6 × 3 + 2)* 2
= 100 + 40
= 140

If the array is stored in memory in column-major order:
Loc (A[4, 3]) = Base (A) + m (j - 1) + (i - 1)* 2
= 100 + (5 × 2 + 3)* 2
= 100 + 26
=126

Two dimensional array representation in memory

• The elements of a two dimensional array are stored in computer’s memory row by row or column by column.
• If the array is stored as row by row, it is called row-major order.
• If the array is stored as column by column, it is called column-major order.
• Suppose there is a two-dimensional array of size 5 × 6. That means, there are 5 rows and 6 columns in the array.
• In row-major order, elements of a two dimensional array are ordered as –
• A11, A12, A13, A14, A15, A16, A21, A22, A23, A24, A25, A26, A31, ............, A46, A51, A52, .......,A56.
• and in column-major order, elements are ordered as –
• A11, A21, A31, A41, A51, A12, A22, A32, A42, A52, A13, ............, A55, A16, A26, .......,A56.

Two Dimensional Array

---

---

Definition of two dimensional array

• Two dimensional array is an array that has two dimensions, such as row and column.
• Total number of elements in a two dimensional array can be calculated by multiplication of the number of rows and the number of columns.
• If there are m rows and n columns, then the total number of elements is m × n, and m × n is called the size of the array.
• Of course, the data elements of the array will be same type.
• In mathematics, the two dimensional array is called a matrix and in business it is called table

A two dimensional array can be expressed as follows:




To store and retrieve values in and from array

Data can be stored in a two dimensional array using loop or directly as shown below:
i) storing data taken from keyboard

int B[7][3];
for (int i = 0; i < 7; ++ i)
{
for (int j = 0; j < 3; ++ j)
scanf (“%d”, &B[i][j]);
}


ii) Direct insertion of data in two dimensional array

int B[7][3] = {
{ 1, 2, 3},
{ 9, 10, 11},
… …. ….,
… …. ….,
… …. ….,
… …. ….,
{22, 25, 40}
};

---

---

Insert The Element Into The Array At A Given Position

---

---

Problem 2.5:
Given a list of integers stored in a linear array and a data element, insert the element into the array at a given position.
Algorithm 2.5:
Algorithm to insert an element into an array.
1. Input: An array A[1...n], the position of insertion m and the data x.
2. Increase the size of the array, A[1...n + 1]
3. for (i = m; i≤ n; i = i + 1)
A[i + 1] = A[i];
4. A[m] = x;
5. Output: The array, A with size n + 1.

Problem as assignment

Given, two linear arrays of integers, merge the two arrays into a single array.


This is the end
of
one dimensional array


Preview <<

>>>>Next

---

---

Find out the summations of even and odd numbers

---

---

Algorithm 2.3:
Algorithm to find the summation of even and odd numbers

Input: A[1...n], sum_odd = 0, sum_even = 0;
//An array and variables to store the summation
2. for (i = 1; i ≤ n; i = i + 1)
{
if (A[i]%2 = = 0), sum_even = sum_even + A[i];
else sum_odd = sum_odd + A[i];
}
3. Output: Summation of odd numbers (print sum_odd) and summation of even numbers (print sum_even)


Find Out The Summations Of Numbers In Odd Index And Even Index Separately

Problem 2.4:
Given a list of integers stored in a linear array, find out the summations of numbers in odd index and even index separately.

Solution:
This problem is similar to the problem 2.3. Here the difference is that, we have to check whether the index is odd or even.

Summation Of Even And Odd Indexed Numbers
Algorithm 2.4:
Algorithm to find the summation of even and odd indexed numbers
Input: A[1...n], sum_odd = 0, sum_even = 0;
//An array and variables (to store the summation)
2. for (i = 1; i ≤ n; i = i + 1)
{
if (i%2 = = 0), sum_even = sum_even + A[i];
else sum_odd = sum_odd + A[i];
}
3. Output: Summation of numbers in odd indices (print sum_odd) and summation of numbers in even indices (print sum_even)




preview <<

>>Next

---

---

To find out largest element

---

---

Problem 2.1:
Given a list of elements, write an algorithm to store the list of elements (numbers) in an array and find out the largest element of the list.
Algorithm 2.1: Algorithm to search the largest element of a list
1. Input: x[1 . . . n];
2. for (i = 1; i ≤ n; i = i + 1)
store data to x[i];
3. large = x[1];
4. for (i = 2; i ≤ n; i = i + 1)
if (x[i] > large), large = x[i]; // if any element larger
then the previous_upgrade large
5. Output: the largest number is, large


Find Out A Particular (Specific) Element


Problem 2.2
Given a linear array with data, find out a particular (specific) element of x from the array. We do not know the index (cell) number where the element has been stored.

Algorithm 2.2: Algorithm to search a particular element from a list
1. Input: a[1 . . . n], x;
//A set of data in array a, and variable x i.e., the target element
2. found = 0
3. for (i = 1; i ≤ n; i = i + 1)
{
if (a[i] = = x);
location = i, found = 1, break;
}
4. Output: if (found = = 1), print “FOUND” message and location.
else print “NOT FOUND” message

Find out the summations of odd numbers and even numbers separately


Problem 2.3:
Given a list of integers stored in a linear array. Find out the summations of odd numbers and even numbers separately.
Solution:

• Given a list of integer, we have to find out the odd numbers and then we shall add those odd numbers.
• Similarly, we shall find out the even numbers in the list and adding those numbers we shall get the summation of even .
• To store the result, we require two variables; sum__even and sum__odd.
• Initially, values of these variables will be zero (0) and every time we find an even number we shall add it to the sum__even and every time we find an odd number, we shall add it to the sum__odd.
  

• If a number is divisible by 2 it is even, otherwise odd.
• We have to start from the first number of the list.
• If it is even, it will be added with the sum_even and if it is odd, it will be added with the sum_odd.
• Similarly, we shall access whole list one by one and we shall add them with either sum_even (if a number is even) or sum_odd (if a number is odd).

preview <<

>>> Next

---

---

One Dimensional Array

---

---

An array that can be represented by only one dimension such as row or column and that holds finite number of same type of data items is called one dimensional (linear) array.
Here 1, 2, 3, … … …, 10 are index number, and
0, 10, 12, … … …, 39 are data items or elements of the array and B is the array name.
Symbolically an element of the array is expressed as Bi or B[i], which denotes ith element of the array, B.
Thus B[4], B[9] denotes respectively the 4th element and the 9th element of the array, B.
The name of the array usually is a name constituted by one or more characters.
Thus array name may be A, S, Stock, Array1 etc.
The element of an array may be number (integer or floating point number) or character



Expression of one dimensional array in C/C++:
For integer array:
int a[10];
For character array:
char b[30];
For floating point array:
float c[10];






Store an element into an array
B[4] = 19; it means 19 will be stored in the cell number 4 of the array of B
If there is any (previous) value that will be overwritten.

Read (retrieve) a value (element) from an array
x = B[6]; it means the value of x will be 20, since the cell number 6 of the array, B contains 20

Code in C/C++ for storing data in an array
int x[10];
for (i = 0; i < style="font-weight: bold;">Code in C/C++ for accessing data from an array and the data will be displayed on the monitor’s screen:
int AC[20];
for (i =0; i < style="font-weight: bold;">Here array name is AC and the size of the array is 20.

Preview <<

>>Next

---

---

Definition of an array

---

---

• An array is a finite set of same type of data items. In other words, it is a collection of homogeneous data items (elements).
• The elements of an array are stored in successive memory locations.
• Any element of an array is referred by array name and index number (subscript).
• There may have many dimensional arrays. But usually two types of array are widely used; such as

one dimensional (linear) array and
two dimensional array.

>> Next

---

---

Space complexity

---

---

This complexity is related to space (memory) needs in the main memory for the data used to implement the algorithm for solving any problem. That means if there n data items used in an algorithm, the space complexity of the algorithm will be proportional to n.

The complexity of an algorithm (either time complexity or space complexity) is represented using asymptotic notations.
One of the asymptotic notations is O (big-oh) notation.
Big-oh (O) notation is also called upper bound of the complexity.

If we get the total number of element comparisons is ½ n2 – ½ n, then we can write it as O (n2).
Since (½ n2 – ½ n) <>

Preview <<

---

---

This is the end Of Chapter 1

---

---

Time complexity

This complexity is related to execution time of the algorithm.
It depends on the number of element (item) comparisons and number of element movement (movement of data from one place to another).
However, the complexity of the most of the algorithms described here related to the number of element comparisons.
That means, the complexity of the algorithm is computed with respect to the total number of element (item) comparisons needed for the algorithm

Preview <<<<<<

>>>>>>Next

Importance of data structure

• Computer science as well as computer engineering deals with two jargons which are software and hardware.
• Without software, hardware (electrical, mechanical, electronic parts of computer that we see and touch) is useless.
• So, study of software is very important in computer science, and software consists of programs which use different types of data.
• In a program we not only use elementary data items but also use different types of organized data. That means we use data structure in a program. As we know we write programs to solve problems. That is, to solve problems we have to use data structures. The different data structures give us different types of facilities.
• If we need to store data in such a way that we have to retrieve data directly irrespective of their storage location. We can get this facility using one type of data structure such as array gives us such facility.
  

Preview <<

• >>Next
  

program

Program

• Sequence of instructions of any programming language that can be followed to perform a particular task.

• For a particular problem, at first we may write an algorithm then the algorithm may be converted into a program.

• In a program usually we use a large amount of data. Most of the cases these data are not elementary items, where exists structural relationship between elementary data items.
  
  That means the programs uses data structure(s).

Preview <<

>> Next

Algorithm

Set or sequence of instructions (steps) that can be followed to perform a task (problem).
Do not strictly follow grammar of any particular programming language.
However its language may be near to a programming language.

q Each and every algorithm can be divided into three sections.

v First section is input section, where we show which data elements are to be given.

v The second section is very important one, which is operational or processing section. Here we have to do all necessary operations, such as computation, taking decision, calling other procedure (algorithm) etc.

v The third section is output, where we display the result found from the second section

preview <<

Next >>

BackgRound2

Example of Data Structures:
Array, Linked List, Stack, Queue, Tree, Graph, Hash
Table etc.
Types of elementary data item:
Character, Integer, Floating point numbers etc.

Expressions of elementary data in C/C++
Elementary data item - Expression in C/C++
Character - char
Integer - int
Floating point number - float

preview <<

>>Next

BackgRound

Elementary items constitute a unit and that unit may be considered as a structure.
.>> structure may be treated as a frame or proforma where we organize some elementary items in different ways.
Data structure is a structure or unit where we organize elementary data items in different ways.
>>That means, a data structure is a means of structural relationships of elementary data items for storing and retrieving data in computer’s memory.
Usually elementary data items are the elements of a data structure.
However, a data structure may be an element of another data structure. That means a data structure may contain another data structure

next

Data Structures Fundamentals

Data Structures Fundamentals
By
Md. Rafiqul lslam, Ph.D
M.A. Mottalib, Ph.D

,

facebook