Strings

Character Strings

• Strings in C are stored as null character ‘’ , terminated character arrays.

• This means that the length of a string is the number of characters it contains one more to store the null character.

• Basically all the strings are the arrays of characters.

• As we declare the array of integers in case of integer array, the same is the case for the strings but here the array is declared as of character type.

String operations

Common string operations include Finding lengths, copying, searching, replacing and counting the occurrences of a specific characters and words.

Arrays of strings

An array of strings is just a two dimensional array of characters.

Example :

char  names [ 7 ][ 6 ] = { “Ryan” ,

“Tom” ,

“Chad” ,

“Jackie” ,

“Tara” ,

“Lori” ,

“Kelly” ,

} ;

This gives you an array of seven names.

Sparse Matrix

Sparse Matrices

• ü    A sparse matrix, like a sparse array, is a matrix where most of the elements are the same value. In most cases, the common value is zero, but this is not necessarily the case.

• ü    The principles for handling these matrices can also be used to speed up operations on other kinds of sparse matrices.

• ü    When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix.

• ü    Sparse data is by nature easily compressed, and this compression almost always results in significantly less computer data storage usage.

• ü    Indeed, some very large sparse matrices are infeasible to manipulate with the standard dense algorithms.

A simple example is given below :

0      6      0      0      0

0      0      0      0      8

9      0      0      0      0

0      0      6      0      0

0      0      0      5      0

Multidimensional Array

Multidimensional Arrays

Multidimensional arrays are arrays of arrays are declared.

A simple example is given below for 2-D array:

int  int_array [ 10 ] [ 10 ] ;         //  A two dimensional array

• Initializing a two dimensional array

It can be initialized as follows :

int array [ 2 ] [ 2 ]  =  {1, 2, 3, 4}  ;

• Accessing the elements

Elements in two dimensional arrays can be accessed as follows:

a [ 0 ] [ 0 ]  =  10 ;    //  assigns 10 to element at first row first column

a [ 0 ] [ 1 ]  =  1 ;      //  assigns 1 to element at first row second column

a [ 2 ] [ 2 ]  =  11 ;    //  assigns 11 to element at third row third column

Implementation of a 2-D array

A two dimensional array can be implemented in a programming language in two ways :

1. Row major implementation

2. Column major implementation

Row major implementation

In it elements of array are read form keyboard row-wise i.e, complete first row is stored, then complete second row and so on.

Address of element,  a[i][j] = B + W ( n ( i – L₁ ) + ( j – L₂))

Where,       B     –     Base address

W    –     Size of each array element

n      –     Number of columns

L₁ –     Lower bound of row

L₂ –     Lower bound of column

Column major implementation

In it elements of array are read form keyboard column-wise i.e, complete first column is stored, then complete second column and so on.

Address of element,  a[i][j] = B + W ( m ( j – L₂ ) + ( i – L₁))

Where,

B     –     Base address

W    –     Size of each array element

m     –     Number of rows

L₁ –     Lower bound of row

L₂ –     Lower bound of column

1-D Array

One dimensional Array

An array can be defined as an infinite collection of homogenous (similar type) elements.

Few points:

• Arrays are always stored in consecutive memory locations.
• Array name s a pointer to its first element.
• There is no bound checking concept for arrays in C.
• One dimensional array is declared as follows:

data_type  var_name [expression] ;

• Size of array is determined as follows:

Size = (upperbound – lowerbound) + 1

• Initializing One dimensional array:

The initializers are specified within braces & separated by commas.

• Accessing one dimensional array elements:

Array_name [index or subscript] ;

• Implementation of one dimensional array in memory:

Address of element a[k] = B + W * K

INSERTION Algorithm

DELETION Algorithm

TRAVERSAL Algorithm

MERGING Algorithm

Tower Of Hanoi

TOWER OF HANOI

The Classical Towers of Hanoi

An initial position of all disks is on post ‘A’.

The solution of the puzzle is to build the tower on post ‘C’.

Solving the Tower of Hanoi – ALGORITHM

STEPWISE SOLUTION

Follow the same step again and again as shown in the following figure.

Step-1  Move disks 1,2,3 to B and 4 to C.

Step-2  Move 1,2,3 to A

Step-3 Then again repeat the same step with the remaining disks.

If one needs a recursive or iterative algorithm which generates the series of moves for solving arbitrary Towers of Hanoi then one should use a kind of back track programming, that is to remember previous steps of the analysis and not to repeat the analysis of the Towers from the ground.

Recursion

BASICS OF RECURSION

Recursion is an alternative to iteration in making a function execute repeatedly.

Recurrence from Latin ,  re = back + currere = to run to happen again

Types of Recursion

I  Direct recursion           – Function calls itself from within itself.

II Indirect recursion       – Two functions call one another mutually.

int abc( )                                  int abc( )

{                                               {

—-;                                          —–;

abc( );                                              xyz( );

}                                               }

int xyz( )

{

abc( );

——–;

}

Direct Recursion                    Indirect Recursion

Linear Recursion

Every possible chain of recursive calls must eventually reach a base case, and handling of each base case should not use recursion. A simple example of linear recursion is given .

Binary Recursion

It occurs when there are two recursive calls for each non base case.

Example is the problem to add all numbers in an integer array A.

Multiple Recursion

In it we make many recursive calls.

Example is summation puzzles.

Data Structure Operations

DATA STRUCTURE OPERATIONS

• The data which is stored in our data structures are processed by certain set of operations.
• While selecting a particular data structure for the application we choose given data structure largely on the frequency with which specific operations are performed.

The following operations we can perform on the data structures :

TRAVERSING

Accessing each data exactly once in the data structure so that each data item is traversed or visited.

SEARCHING

Finding the location of data within the data structure which satisfy the searching condition or the criteria.

INSERTING

Adding a new data in the data structure.

DELETING

Removing the data from the data structure is referred as deletion.

SORTING

Arranging the data in some logical order.

MERGING

Combining the data of two different sorted files into a single sorted file.

Algorithm & Performance

ALGORITHM & PERFORMANCE

An algorithm is a definite, step-by-step procedure for performing some task.

Algorithm is of two types :

1. 1. Incremental algorithm – It proceeds in step incremental order.
2. 2. Divide & conquer algorithm – It breaks the problem into several sub problems that are similar to original problem but smaller in size, solve them recursively and then combine these solutions to create a solution to the original problem.

PERFORMANCE

• When we discuss algorithms, we often need a way of talking about the efficiency of the algorithm, that is, what sort of resources will be required to execute the algorithm.
• The resource in question can be time how long will the algorithm run or space how much memory will the algorithm require.
• In practice, we will mostly be concerned with the run-time efficiency of the algorithm, but many of the same ideas apply to space efficiency.

Algorithm Analysis

• The worst-case running time, this refers to the longest running time of the algorithm for any input of size n.
• The best-case running time, which refers to the shortest running time for any input of size n.
• The average-case running time, which refers to the average running time where the average is taken over all possible inputs of size n.

GROWTH RATE

The growth rate of a function has to do with the rate at which the value of the function changes as the size of its input increases. The growth rate gives the general shape of the function, rather than its specific value.

Looking at growth rates in this way is sometimes called asymptotic analysis, where the term asymptotic” carries the connotation of for large values of n.”

NOTATIONS

O‍‍‍‍-Notation

It bounds the function to within constant factors.

We say  f(n) = O(g(n))  if there exists positive constant n₀,c₁ and c₂ such that to the right of n₀ the value of f(n) always lies between c₁g(n) and c₂g(n).

O-Notation

This gives the upper bound. It gives f(n) = O(g(n))  if there are positive constants n₀ and c such that to the right of n₀, the value of f(n) always lies on or below cg(n).

Ω- Notation

It says f(n) =   Ω g(n)   if there are positive constants n₀ and c such that to the right of n₀, the value of f(n) always lies on or above cg(n).

Data Structures

DATA STRUCTURES

Data structure is the representation of the logical relationship existing between individual elements of data.

It is the mathematical or logical model of particular organization of data items.

CLASSIFICATION

I    Primitive data Structure

These are basic structures and are directly operated upon by the machine instructions.

Eg. Integer, floating point, character, pointers etc.

II   Non- Primitive data structure

These are derived from primitive data structures & emphasizes on structuring of a group of homogenous or heterogeneous data items.

Eg.  Arrays, lists, files etc.

Memory Allocations in C

1. 1. Compile time or Static allocation

The required amount of memory is allocated to the program element at the start of the program.

1. 2. Run-time or dynamic allocation (using pointers)

The amount of memory to be allocated is unknown but the memory is reserved when only needed i.e, during the runtime.

C provides the following dynamic allocation and de-allocation functions :

I malloc( )

II calloc( )

III free( )

IV realloc( )

About Author

The site creator, DEEPAK SINGHAL (DEEPS)  basically endeavoured to publish his ideas in terms of electornix and microelectronics & Computerzz and Algorithmzz  from the very basic level to the microprocessor and the microcontroller level.

All the views and reviews are courteously welcomed here so as to provide the timely feedbacks.