Showing posts with label C Theory. Show all posts
Showing posts with label C Theory. Show all posts

## Designing Algorithms.

Since the meaning of algorithm and data has been understood,so strategies can be devised for designing algorithms.The following is a useful strategy.

### Investigation Step:

1. Identify the ouptut needed.
This includes the form in which the output have to be presented.At the same time,it has to be determined at what intervals and with what precision the output data needs to be given to user.
2. Identify the input variable available.
This activity consider the specific inputs available for this program,the form in which the input variable would  be available,the availability of inputs at different intervals,the ways in which the input would be fed to the transforming process.
3. Identify the major decisions and conditions.
This activity looks into the conditions imposed by the need identified and the limitations of the environment in which the algorithm has o be implemented.
4. Identify the processes required to transform inputs into required outputs.
This activity identifies the various types of procedures needed to manipulate the inputs,within the  bounding conditions and the limitations mentioned in step 3, to produce the needed outputs.
5. Identify the environment available
This activity determines the kind of users and the type of computing machines and software available for implementing the solution through the processes considered in step.

### Top-down development step:

1. Devise the overall problem solution by identifying the major components of system.
The goal is to divide the problem solution into manageable small pieces that can be solved separately.
2. Verify the feasibility of breaking up the overall problem solution.
The basic idea here is to check that though each small piece of solution procedure are independent of each other,as they together form the whole solution to problem.In fact,the different pieces of solution procedures have to cooperate and communicate in order to solve the larger problem.

### Stepwise refinement:

1. Work out each and every detail for each small piece of manageable solution procedure.
Every input and output dealt with and the transformation algorithms implemented in each small piece of solution procedure,which is also known as process,is detailed.Even the interfacing details between each small procedure are worked out.
2. Decompose any solution procedure detailed in step 1 is checked once again.
If necessary any of these may be further broken up into still smaller pieces of solution procedure till it can no more be divided into meaningful procedure.
3. Group processes together which have some commonality.
Some small processes may have to interface with a common upper level process.Such processes may be grouped together if required.
4. Group variables together which have some appropriate commonality.
Certain variables of same type may be dealt as elements of a group.
5. Test each small procedure for its detail and correctness and its interfacing with the other small procedures.
Walk through each of the small procedures to determine whether it satisfies the primary requirements and would deliver the appropriate outputs.Also,suitable tests have to be carried out to verify the interfacing between various procedures.Hence,the top-down approach starts with a big and hazy goal.It breaks the big goal into smaller components.These components are themselves broken down into smaller parts.This strategy continues until the designer reaches the stage where he or she  has concrete steps that can actually be carried out.
It has to be noted that the top-down approach does not actually take into account any existing equipment,people or process.It begins with a "clean slate" and obtains the optimal solution.The top-down approach is most appropriate for large and complex projects where there is no existing equipment to worry about.However,if the existing equipment can be made to fit into the new plan with very less effort,it would be beneficial to use it and save cost.

## Data Types.

Data type plays an important role in any programming language as they refer to an extensive  used for declaring the variables or function of similar or different types.Type of variable determines how much space it occupies in storage and also how the bit pattern is interpreted.
S.N.Types and Description
1
Basic Types:
They are arithmetic types and consists of the two types: (a) integer types and (b) floating-point types.
2
Enumerated types:
They are again arithmetic types and they are used to define variables that can only be assigned certain discrete integer values throughout the program.
3
The type void:
The type specifier void indicates that no value is available.
4
Derived types:
They include (a) Pointer types, (b) Array types, (c) Structure types, (d) Union types and (e) Function types.
The array  and structure data types are collectively as the aggregate types. The type of a function specifies the type of the function's return value i.e the result of a operation which the function will return after its execution. We will see basic data types in the following section, whereas, other data types will be coveredlater.

## Integer Types

Following table gives you details about standard integer data types with its storage sizes and value ranges:
TypeStorage sizeValue range
char1 byte-128 to 127 or 0 to 255
unsigned char1 byte0 to 255
signed char1 byte-128 to 127
int2 or 4 bytes-32,768 to 32,767 or -2,147,483,648 to 2,147,483,647
unsigned int2 or 4 bytes0 to 65,535 or 0 to 4,294,967,295
short2 bytes-32,768 to 32,767
unsigned short2 bytes0 to 65,535
long4 bytes-2,147,483,648 to 2,147,483,647
unsigned long4 bytes0 to 4,294,967,295
To get the exact size of a type or a variable on a particular platform, you can use the sizeof() operator. The expressions sizeof(type) yields the storage size of the object or type in bytes. Following is an example to get the size of int type on any machine:
```#include <stdio.h>
#include <limits.h>

int main()
{
printf("Storage size for int : %d \n", sizeof(int));
return 0;
}```
When you compile and execute the above program it produces the following result:
```Storage size for int : 4
```

## Floating-Point Types

Following table gives you details about standard floating-point data types with storage sizes and value ranges and their precision:
TypeStorage sizeValue rangePrecision
float4 byte1.2E-38 to 3.4E+386 decimal places
double8 byte2.3E-308 to 1.7E+30815 decimal places
long double10 byte3.4E-4932 to 1.1E+493219 decimal places
The header file float.h defines macros that allow you to use these values and other details about the binary representation of real numbers in your programs. Following example will print storage space taken by a float type and its range values:
```#include <stdio.h>
#include <float.h>

int main()
{
printf("Storage size for float : %d \n", sizeof(float));
printf("Minimum float positive value: %E\n", FLT_MIN );
printf("Maximum float positive value: %E\n", FLT_MAX );
printf("Precision value: %d\n", FLT_DIG );
return 0;
}```
When you compile and execute the above program, it produces the following result:
```Storage size for float : 4
Minimum float positive value: 1.175494E-38
Maximum float positive value: 3.402823E+38
Precision value: 6
```

## The void Type

The void is a data type that specifies no value is available. It is used in three kinds of situations:
S.N.
Types and Description
1
Function returns as void
There are various functions in C which do not return value or you can say they return void. A function with no return value has the return type as void. For example void exit (int status);
2
Function arguments as void
There are various functions in C which do not accept any parameter. A function with no parameter can accept as a void. For example, int rand(void);
3
Pointers to void
A pointer of type void * represents the address of an object, but not its type. For example a memory allocation function void *malloc( size_t size ); returns a pointer to void which can be casted to any data type.
The void type may not be understood to you at this point, so let ignore it as we will cover these concepts in the upcoming chapters.

## Variables.

Till now,we have discussed the elements of algorithm.But a program comprises of algorithm and data.Therefore,it is now necessary to understand the concept of data.It is known that data is a symbolic representation of value and that programs set the context that gives data a proper meaning.In programs,data is transformed into information.
The question is ,how is data represented in program?
Almost every algorithm contains data and usually the data is 'contained' in what is called a variable.
The variable is a container for a value that may vary during the execution of program.For example,in the tea-making algorithm,the level of water is a variable and the quantity of tea level is also a variable.
Each variable in a program is given a name,for example,

• water_level
• water_temperature
• tea_leaves_quantity
and at any given time the value,which is represented by water_level,for instance,may be different to its value at some other time.This statement
"if the kettle does not contain water then fill the kettle" could also be written as
"if water_level is 0 then fill the kettle"
or
"if water_level=0 then fill the kettle"
At some point water_level will be at maximum value,whatever that is and the kettle will be full.

## Variables and data types:

The data used in algorithms can be of different types.The simplest types of data that an algorithm might use are
• numeric data,e.g., 12,11.45,901,27,32,etc.
• alphabetic or character data such as 'A','Z',or 'Any String',or 'Any character from the keyboard'.
• logical data,that is propositions with true/false values.
A variable is nothing but a name given to a storage area that our programs can manipulate. Each variable in C has a specific type, which determines the size and layout of the variable's memory; the range of values that can be stored within that memory; and the set of operations that can be applied to the variable.
The name of a variable can be composed of letters, digits, and the underscore character. It must begin with either a letter or an underscore. Upper and lowercase letters are distinct because C is case-sensitive. Based on the basic types explained in previous chapter, there will be the following basic variable types:
TypeDescription
charTypically a single octet(one byte). This is an integer type.
intThe most natural size of integer for the machine.
floatA single-precision floating point value.
doubleA double-precision floating point value.
voidRepresents the absence of type.
C programming language also allows to define various other types of variables, which we will cover in subsequent chapters like Enumeration, Pointer, Array, Structure, Union, etc. For this chapter, let us study only basic variable types.

## Variable Definition in C:

A variable definition means to tell the compiler where and how much to create the storage for the variable. A variable definition specifies a data type and contains a list of one or more variables of that type as follows:
`type variable_list;`
Here, type must be a valid C data type including char, w_char, int, float, double, bool or any user-defined object, etc., and variable_list may consist of one or more identifier names separated by commas. Some valid declarations are shown here:
```int    i, j, k;
char   c, ch;
float  f, salary;
double d;```
The line int i, j, k; both declares and defines the variables i, j and k; which instructs the compiler to create variables named i, j and k of type int.
Variables can be initialized (assigned an initial value) in their declaration. The initializer consists of an equal sign followed by a constant expression as follows:
`type variable_name = value;`
Some examples are:
```extern int d = 3, f = 5;    // declaration of d and f.
int d = 3, f = 5;           // definition and initializing d and f.
byte z = 22;                // definition and initializes z.
char x = 'x';               // the variable x has the value 'x'.```
For definition without an initializer: variables with static storage duration are implicitly initialized with NULL (all bytes have the value 0); the initial value of all other variables is undefined.

## Variable Declaration in C:

A variable declaration provides assurance to the compiler that there is one variable existing with the given type and name so that compiler proceed for further compilation without needing complete detail about the variable. A variable declaration has its meaning at the time of compilation only, compiler needs actual variable declaration at the time of linking of the program.
A variable declaration is useful when you are using multiple files and you define your variable in one of the files which will be available at the time of linking of the program. You will use extern keyword to declare a variable at any place. Though you can declare a variable multiple times in your C program but it can be defined only once in a file, a function or a block of code.

## Example:

Try following example, where variables have been declared at the top, but they have been defined and initialized inside the main function:
```#include <stdio.h>

// Variable declaration:
extern int a, b;
extern int c;
extern float f;

int main ()
{
/* variable definition: */
int a, b;
int c;
float f;

/* actual initialization */
a = 10;
b = 20;

c = a + b;
printf("value of c : %d \n", c);

f = 70.0/3.0;
printf("value of f : %f \n", f);

return 0;
}```
When the above code is compiled and executed, it produces the following result:
```value of c : 30
value of f : 23.333334
```
Same concept applies on function declaration where you provide a function name at the time of its declaration and its actual definition can be given anywhere else. For example:
```// function declaration
int func();

int main()
{
// function call
int i = func();
}

// function definition
int func()
{
return 0;
}```

## Lvalues and Rvalues in C:

There are two kinds of expressions in C:
1. <> lvalue : An expression that is an lvalue may appear as either the left-hand or right-hand side of an assignment.
2. <> rvalue : An expression that is an rvalue may appear on the right- but not left-hand side of an assignment.
Variables are lvalues and so may appear on the left-hand side of an assignment. Numeric literals are rvalues and so may not be assigned and can not appear on the left-hand side. Following is a valid statement:
`int g = 20;`
But following is not a valid statement and would generate compile-time error:
`10 = 20;`

## The Repetition constructs-repeat and while

Repetition can be implemented using constructs like the repeat loop,while loop and if...then...goto... loop.The repeat loop is used to iterate or repeat a process or sequence of processes until some conditional becomes true.
It has the general form:

Repeat
Process 1
Process 2
..............
...............
Process N
until proposition
Here is an example:
Repeat
Fill water in kettle
until Kettle is full

The process is 'Fill water in Kettle',the proposition is 'Kettle is full'.
The repeat loop does some processing before testing the state of proposition.
What happens though if in the above example the Kettle is already full?
If the Kettle is already full at the start of the Repeat loop,then filling more water will lead to an overflow.This is a drawback of Repeat construct.
In such case the while loop is more appropriate.The above example with the while lopp is shown as follows:

while Kettle is not full
fill water in Kettle

Since,the decision about the Kettle being full or not is made before filling water,the possibility of an overflow is eliminated.The while loop find out whether some condition is true before repeating a process or a sequence of processes.
If the condition is false,the process or the sequence of process is not executed.The general form of while loop processes is not executed.
The general form of while loop is :

while proposition
begin
Process 1
Process 2
...............
...............
Process N
end

The if...then...goto is also used to repeat a process or a sequence of process until the given proposition is false.In the Kettle example,this construct would be implemented as follows:

1. Fill some water in Kettle
2. if Kettle not full then goto 1

So long as the proposition 'Kettle not full' is true,the process 'fill some water in Kettle' is repeated.
The general form of if...then...got.. is:
Process 1
Process 2
..............
..............
Process N
if proposition then goto Process 1

### Termination:

The definition of algorithm cannot be restricted to procedure that eventually finish.Algorithms might also include procedures that could run forever without stopping.Such a procedure has been called a computational method by Knuth or calculation procedure or algorithm by Kleene.However,Kleene notes that such a method must eventually exhibit 'some object'.Minsky (1967) makes the observation that,if an algorithm has not terminated,then how can the following question be answered:"Will it terminate with correct answer?".Thus the answer is :undecideable.It can never be known,nor can the deisgner do an analysis beforehand to find it out.The analysis of algorithms for their likelihood of termination is called termination analysis.

### Correctness:

The prepared algorithm need to be verified for its correctness.Correctness means how easily its logic can be argued to meet the algorithm's primary goal.This requires the algorithm to be made in such a way that all the elements in it are traceable to the requirements.
Correctness requires that all the components like the data structure,modules,external interfaces and module interconnections are completely specified.
In other words,correctness is the degree to which an algorithm performs its specified function.The most common measure of correctness is defects per Kilo Lines of codes(KLOC) that implements the algorithm,where defect is defined as the verified lack of conformance to requirements.

## Sequence and Decision in Algorithm.

Sequence means that each step or process in the algorithm is executed in the specified order.In the Kettle example,each process must be in the proper place otherwise the algorithm will fail.

### The decision constructs -if...then,if...then...else...

In algorithms the outcome of a decision is either true or false;there is no state in between.The outcome of the decision is based on some condition that can only result in a true or false value.
For example:
if today is Monday then collect pay
Here,the above statement is a decision and the decision takes the general form: if proposition then process
A proposition,in this sense,is a statement,which can only be true or false.It is either true that 'today is Monday' or it is false.If the proposition is true,then the process or procedure that follows the proposition is executed.
The decision can also be stated as:
if proposition
then process 1
else             process 2
This  is the if...then...else... form of decision.This means that if the proposition is true,then execute process 1,else execute process 2.
The first form of the decision if proposition then process has a null else,that is,there is no else.

#### Let us take an example to understand sequence and decision.

Q1)Write an algorithm to check whether a number given by user is even or odd.
Solution: Let the number to be checked be represented by 'N'.
The number 'N' is divided by 2 to give an integer quotient,denoted by Q.If the remainder,designated as 'R' is zero,'N' is even,otherwise 'N' is odd.This logic is applied in following algorithm.
1. START
Print "Enter the number"
3. [Take Input]
Input N
4. [Logic Applied to find whether number is even or odd]
Q <- N/2 (i.e. Q=N/2)
5. [Finding remainder]
R <- N-Q*2 (i.e. R=N-Q*2)
6. [Decision Construct]
If R = 0 then Print "N is EVEN"
7. [Decision Construct] If R!=0 then Print "N is ODD"
8. STOP

Q2)Print the largest among three numbers.
Solution: Let the three number be represented  by A,B, and C.There can be three ways of solving the problem.The three algorithms with some differences are given below:
Type 1: By using AND operator.
1. START
2. Print "Enter the Number"
3. Input A,B,C
4. If A >= B AND B>=C
Then print A
5. If B >= C AND C >= A
Then Print B
ELSE Print C
6. STOP
Type 2: This algorithm uses a variable MAX to store the largest number.
1. START
2. Print "Enter THREE NUMBERS"
3. Input A,B,c
4. MAX <-A (i.e. MAX=A)
5. If B > MAX Then MAX <- B (i.e. MAX=B)
6. If C > MAX Then MAX <- C (i.e. MAX=C)
7. Print MAX
8. STOP
Type 3: This algorithm uses a nested if construct.
1. START
2. Print "Enter three number"
3. Input A,B,C
4. If A > B then
If A > C Then
Print A
Else Print C
Else If B > C Then
Print B
Else Print C
5. STOP
If you face any problem regarding ALGORITHM,inform us and we will try to solve it out.

## ALGORITHMS.

Assuming that you have basic knowledge about computer like when it was made,types of computer and operating system,hardware parts of computer,inventor of computer,etc,i am starting a new but important topic "ALGORITHM".
If you dont have any basic knowledge about computer,just google it.

## What is an Algorithm?

An algorithm is a part of the plan for the computer program. Infact ,an algorithm is an effective procedure for solving a problem in a finite number of steps.
It is effective,which means that an answer is found and it has a finite number of steps.A well-designed algorithm will always provide an answer,it may not be the desired anwser but there will be an answer.A well-designed algorithm is also guaranteed to terimnated.
An Algorithm can also be defined as "finite step by step list of well defined instructions for solving a particular problem".
We always need to write algorithm for making different data structure operations.So lets understand what algorithm consist of.
In first part of algorithm we tell the purpose of algorithm.It lists for variables and input data.The second part is a list of steps.
The steps in algorithm are executed one after the other.Control may be transferred to step 'n' by using statement like 'Go to step n'.The exit and stop statements completes the algorithm.The data may be assigned to variables by using read statement and it is displayed by write or print statement.
Today,all the daily computer applications you use,someone might once have written algorithm for it which worked successfully and its result is in our hand.
Google,Facebook,Twitter,Bing,Yahoo,MSN ,etc,all are created and working successfully as their base(algorithm) had worked correctly.So,before any programmer start making something(own application),he/she should first make the algorithm as it is related to many factors like process execution time,results,etc.

#### General syntax of algorithm is given below:

 ALGORITHM 1: Purpose of algorithm and input data and variables used. Start Step 1: ……………………………………………………… Step 2: ………………………………………………………             :             : Step n: ……………………………………………………………. Stop or Exit.

### Different Ways Of Stating Algorithm.

Algorithm may be represented in various ways.There are four ways of stating algorithms.There steps are as follows:
• Step-form.
• Pseudo-code.
• Flow chart.

#### Step-Form Algorithm:

In the step form representation,the procedure of solving a problem is stated with written statements.Each statement solves a part of problem and these together completes the solution.The step-form uses just normal language to define each procedure.Every statement ,that defines an action,is logically related o preceding statement.

#### Pseudo-code:

The pseudo-code is a written form representation of the algorithm.However,it differs from the step form as it uses a restricted vocabulary to define its action of solving the problem.One problem with human language is that it can seem to be imprecise.But the pseudo-code,which is in human language,tends towards more precision by using a limited vocabulary.

#### Flow chart and Nassi-Schneiderman:

Flow chart and Nassi-Schneiderman are graphically oriented representation forms.They use symbols and language to represent sequence,decision and repetition actions.
Standard flowchart symbols are given below:

#### Key Features of an Algorithm and the Step-form.

Here is an example of an algorithm,for making a pot of tea.
1. If the kettle does not contain water,then fill the kettle.
2. Plug the kettle into power point and switch it on.
3. If the teapot is not empty,then empty the teapot.
4. Place tea leaves in teapot.
5. If the water in the kettle is not boiling,then go to step 2.
6. Switch off the kettle.
7. Pour water from the kettle into the teapot.
It can be seen that the algorithm has a number of steps and that some steps(1,3 and 5) involve decision making and one step(5 in case) involves repetition,in this case the process of waiting for the kettle to boil.
From this example,it is evident that algorithms show there three features:
Therefore, an algorithm can be stated using three basic constructs : sequence, decision and repetition.

## Number System.

To learn various programming languages,we must first learn all types of number system and their conversion.
In this post,i am going to give you some information related to number system.

#### Number system:

A number system defines a set of values used to represent quantity.We talk about the number of people attending class,the number of modules taken per student and also use numbers to represent grades achieved by students in test.Study of number system is not just limited to computers.We apply numbers everyday and knowing how numbers work will give us an insight into how a computer manipulates and stores numbers.
• The number of values that a digit can assume is equal to the base of the system.It is also called as the Radix of system.For example,for a decimal system(0-9),the base is "10",hence every digit can assume 10 values.
• The largest value of a digit is always one less than the base.For example,the largest digit in a decimal system is 9(one less than the base).
• Each digit position represents a different multiple of base,i.e. the numbers have positional importance.
• For example consider the decimal number (349.25)10.Here,the position of each digit is represented as follows:   3*102+4*101+9*100+2*10-1+5*10-2,which is equal to 300+40+9+0.25=349.25.
• Hence,we can implement a common rule for all the numbering system as follows.For a general number,we have to multiply each of digit by some power of base(B) or radix.

#### Various Numbering System:

Name of number system                            Base

1. Binary                                                         2
2. Octal                                                           8
3. Decimal                                                     10
4. Duodecimal                                               12
There are many more number system,but the above listed number system are common and important number system which are used now a days in our day to day life.

### Decimal Number System:

g
The number  system we have been taught to use since school is called as decimal number system.We are familiar with counting and mathematics that uses this system.
Characteristics of a decimal system:
Some of important characteristic of a decimal system are:
1. It uses the base of 10.
2. The largest value of digit is9.
3. Each place represents a different multiple of 10.The multiples are also called as weighted values.The weighted values of each position are as shown below: #### Most Significant Digit(MSD):

It is the leftmost digit having the highest weight.

#### Least Significant Digit(LSD):

It is the rightmost digit having lowest weight.

### The Binary Number System:

• Most modern computer system operate using the binary logic.A computer cannot operate on the decimal number system.
• A binary number system uses only two values 0(for OFF) and 1(for ONN).
• The binary number system works loke a decimal number system except one change.It uses the base 2.
• Hence,the largest value of a digit is 1 an the number of values a digit can assume is two i.e. 0 and 1.
• The weighted values for different positions for a binary system are as show in below fig. • The binary digit(0 and 1) are also called as bits.Thus,binary system is a two bit system.
• The leftmost bit in a given binary number with the highest weight is called as Most Significant Bit(MSB) whereas the rightmost bit in a given number with the lowest weight is called as Least Significant Bit(LSB).

#### Binary Number Format:

• We typically write binary number as a sequence of bits(bits is short for binary digits.).We have definition for there bits.These boundaries are: • In any number base,we may add as many leading zeros as we wish without changing its value.
• However,we normally add leading zeros to adjust the binary number to a desired size of boundary.
• For example,we can represent the number five as: #### Disadvantages of the Binary System:

• The binary number system has an important drawback.It requires a very long string of 1's and 0's to represent a decimal number.For example:
(128)10=(10000000)2.

• So we require 8 bits to represent (128)10.
• To overcome this the other numbering system were developed.

### Octal Number System:

The important features of the octal number system are as follows:
1. Base:The base used for octal number system is 8.
2. Each digit in octal system will assume 8 different values from 0 to 7.
3. The largest value of a digit in the octal system will be 7.The below figure represents the octal number system.The last row of figure represents the largest value of digit. 4. Each digit has a different multiple of base.

#### Application  of Octal System:

1. In order to represent large numbers,we will need a huge strings of 0's and 1's if the binary system is used.
2. So the octal system can be used for reducing the size of the large binary number.
3. But it is important to note that the digital circuits and computers internally work strictly with the binary structure and not with the octal structure.
4. The octal structure is used only for the convenience of the user.

### Hexadecimal Number System:

The important features of a hexadecimal number system are as follows:
• Base:The base of hexadecimal system is 16.
• The number of values assumed by each digit is 16.The values include digits 0 through 9 followed by alphabets A to F(A,B,C,D,E,F).
• Hexadecimal values are: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.
• O represent least significant digit whereas F represents the most significant digit.
To have base 16,we need 16 digits.Hence,we use 0 through 9 but need more 6 digits.To overcome this,we use first six alphabets letters A,B,C,D,E,F.Here, A represents 10,B represents 11,C represents 12,D represents 13,E represents 14,F represents 15.

### Counting in a general Radix(Base) r: • We have discussed the number system with radix 10,2,8 and 16.Every such system having a radix "r" contains "r" distinct characters.
• In decimal system the number character is 10.Similarly,in octal system the number of characters is 8.
Check out this video by Soham Railkar.The video is about Introduction to Number System.You can find this video also on SKRtutorials.

### Contact our Support

Email us: nerdprogrammergm@gmail.com

### Our Team Memebers

• • • 