Data Structures and Algorithms Implementation through C: Let’s Learn and Apply

CHAPTER 1

Algorithms and Flowcharts

1.1 Introduction of Algorithm

First of all, before making any program or software, we have to make the documentation of it. This documentation provides the information about that entire software. This program or software can be deployed in any programming language, but if it is necessary to change something later in that program or software then its algorithm or documentation is very important.

By studying the documentation, you get complete information about the software and make some changes in it too easily. So, we can say that the understanding of the software increases through algorithms.

Let us take an example, if the software is being created for a shopping complex and its documentation is being prepared. Now, if we have to make some changes to the software according to the needs of the customer, it is very important to be aware of the outline. If the software needs to extend and we have proper documentation of it, then the software developer will not depend on the developer who develop that software.

1.2 What is an algorithm?

Let's take the problem for making a tea. For making a tea, there are following steps:

Set a metallic saucepan on the stove top or hob.

Add the piece of freshly crushed ginger.

Add tea leaves in it.

Add milk according to choice.

Filter a solution with the help tea strainer.

Put the filtered solution into cups.

Serve it.

What we are doing for making a tea which is our problem. We are writing step by step procedure for solving it. Therefore, the definition of an algorithm is It is a step by step procedure to solve a given problem. Moreover, an algorithm accepts an input list of data and creates an output list of data. Fig. 1.1 shows the basis concept of an algorithm.

Fig 1.1: Basic structure of algorithm

We can also analysis an algorithm in terms of time and space complexity. The analysis of an algorithm has discussed in next chapter.

1.3 Flowcharts

Sometime an algorithm can be a difficult to understand. For improving an understandability of an algorithm, the developer makes a flowchart.

Suppose, if you visit a university and you have to go to a specific department then you go through a flowchart. Moreover, via map a person can easily reach to destination place. A flowchart is a pictorial of graphical representation of an algorithm.

1.3.1 Reason to Use Flowcharts

There are various reasons to use a flow chart.

Documentation and training: Flowcharts are ideal for documentation and training purposes. Flowcharts are also very beneficial for training materials because they're visually stimulating while also being easy to understand. Ultimately, this keeps the reader's attention, so they learn faster.

Workflow management: Flow chart is used for continuous improvement of business process all times. This decides when we meet to customer improvement.

Programming: In the world of algorithms, you will find complexity of algorithm. Information Technology (IT) demands flowcharts for programming, and makes the process faster and smoother. Flowcharts will lead to faster, more efficient coding with fewer errors along the way.

Troubleshooting: Multiple problems and solutions can be presented, thus makes algorithms large in size. When created properly, a flowchart for troubleshooting of the module takes less time.

Quality assurance: Modules mapped with flowcharts ensure that regulatory requirements are followed all times. It is an essential process, and is made easier with the use of flowcharts.

Process flow management services: It increases business efficiency through flowchart.

1.4 Advantages

Communication: Flow Charts are better way of communicating the logic of a system.

Effective Analysis: Problem can be effectively analysed with the help of flowchart

Proper Documentation: Flow charts serve as a good program documentation, which is needed for various purposes.

Efficient Coding: The flow charts act as a guide or blueprint during the systems analysis and program development phase.

Proper Debugging: The flow chart helps in debugging process.

Efficient Program Maintenance: The maintenance of operating program becomes easy with the help of flow chart. It helps the programmer to put efforts more efficiently on that part.

1.5 Symbols Used for Making Flowcharts

There are various types of symbols used for making a flowchart: (Fig. 1.2)

Fig 1.2: Flow chart

1.6 Pseudocode

Pseudocode is a complete description about computer program or algorithm. It is expressed in a natural language rather than in a programming language. Pseudocode is sometimes used as a detailed step in the process of developing a program. Moreover pseudocode is one of the method that could be used to represent an algorithm. It is not written in a specific syntax which is used by a programming language and therefore cannot be executed in a computer.

1.7 Difference between Algorithm and Pseudocode

There are various types of difference between algorithm and pseudocode. Some differences are shown in Table 1.1.

Table. 1.1: Difference between Algorithm and Pseudocode

Example 1: Write an algorithm, flowchart and program to print 1 to 100.

Solution:

Algorithm:

Step 1. Start

Step 2. Initialize N as 0

Step 3. Increment N by 1

Step 4. Print N

Step 5. If N is less than 100 then go back to step 3.

Flowchart:

Fig 1.3: Flowchart to print 1 to 100

C Program:

#include

#include

void main()

{

int N;

clrscr();

N=0;

while (N<100) {

N=N+1;

printf(%d, N);}

}

Output:

1234567891011121314151617181920212223242526272829303132333435363

7383940414243444546474849505152535455565758596061626364656667686

9707172737475767778798081828384858687888990919293949596979899100

Example 2: Write an algorithm, flowchart and program to show the given number is even or odd.

Solution:

Algorithm:

Step 1. Start

Step 2. Take number num from user

Step 3. Check number is divisible by 2

Step 4. If yes then print EVEN

Step 5. Otherwise print ODD

Step 6. Stop

Flowchart:

Fig 1.4: Flowchart to show the given number is even or odd

C Program:

#include

void main()

{

int num, rem;

printf(Enter a number \n);

scanf(%d, &num);

rem=num%2;

if(rem==0)

printf(EVEN \n);

else

printf(ODD \n);

getch();

}

Output:

Enter a Number 18

EVEN

Example 3: Write an algorithm, flowchart and program to display greatest number of three numbers.

Solution:

Algorithm:

Step 1. Start.

Step 2. Take three numbers A, B and C

Step 3. If A>B is true then go to step 4 otherwise go to step 6

Step 4. If A>C is true then display A and go to step 8

Step 5. Otherwise display C and to step 8

Step 6. If B>C then display B and go to step 8

Step 7. Otherwise display C and go to step 8

Step 8. Stop

Flowchart:

Fig 1.5: Flowchart to display greatest number of three numbers

C Program:

#include

#include

void main()

{

int A, B, C;

clrscr();

printf(Enter three numbers\n);

scanf(%d%d%d,&A,&B,&C);

if (A>B)

{

if (A>C)

{

printf(A is the greatest among three \n);

}

else

{

printf(C is the greatest among three \n);

}

}

else if (B>C)

printf(B is the greatest among three \n);

else

printf(C is the greatest among three \n);

getch();

}

Output:

Enter three numbers

11

32

19

B is the greatest among three

Example 4: Write an algorithm, flowchart and program to print sum of first N natural numbers.

Solution:

Algorithm:

Step 1. Start.

Step 2. Take number n

Step 3. Assign value Sum=0, i=1;

Step 4. If i<=N

Step 5. Sum=Sum+i;

Step 6. go back to step 4

Step 7. Print Sum

Step 8. Stop

Flowchart:

Fig 1.6: Flowchart to print sum of first N natural numbers

C Program:

#include

#include

void main()

{

int i, num, sum = 0;

clrscr();

printf(Enter an integer number \n);

scanf (%d, &num);

for (i = 1; i <= num; i++)

{

sum = sum + i;

}

printf (Sum of first %d natural numbers = %d\n, num, sum);

getch();

}

Output:

Enter an integer number

5

Sum of first 5 natural numbers = 15

Example 5: Write an algorithm, flowchart and program to check whether number is prime or not.

Solution:

Algorithm:

Step 1. Start

Step 2. Take three variables num, i, count

Step 3. Initialize i=2 and count=0

Step 4. Check i should be less than num/2

Step 5. If it is true then divide num to i and compare reminder to zero

Step 6. If it is true then increment count check to zero

Step 7. If it is true then show the number is PRIME and go to step 9

Step 8. Otherwise show the number is NOT PRIME

Step 9. Stop

Flowchart:

Fig 1.7: Flowchart to check whether a number is prime or not

C Program:

#include

#include

void main()

{

int num, i, count = 0;

printf(Enter a number:);

scanf(%d, &num);

for (i = 2; i <= num / 2; i++)

{

if(num % i == 0)

{

count++;

break;

}

}

if (count == 0)

printf(%d is a prime number, num);

else

printf(%d is not a prime number, num);

getch();

}

Output:

Enter a number: 5

5 is a prime number

Exercise

A. Pick the correct alternative for each of the following questions:

A Method which uses a list of well-defined instructions to complete a task starting from initial state to end state is:

1. Program

2. Flowchart

3. Algorithm

4. None

Flowchart and Algorithm are used for:

1. Better Programming

2. Easy testing and Debugging

3. Efficient

4. All

An algorithm represented in the form of programming languages is ________

1. Flowchart

2. Pseudo Code

3. Program

4. None

Which symbol is used to represent output in a flowchart?

1. Square

2. Circle

3. Parallelogram

4. Triangle

In some programming languages, programmers must write a variable ____ telling the compiler what data type is expected for the variable.

1. Name

2. Termination

3. Decision

4. Declaration

Declaring a variable involves selecting a name and a ____.

1. Size

2. Length

3. Style

4. Type

Pseudocode is used for:

1. Denoting the program Flow

2. For coding the program

3. To make structure chart

4. To write program steps

Pseudo code emphasizes on

1. Development

2. Coding

3. Design

4. Debugging

B. Design an algorithm, flowchart and c program for finding the sum of the numbers 2, 4, 6, 8… n.

C. Write an algorithm to read 100 numbers and then display the largest number.

D. Design an algorithm, flowchart and c program to print out each character typed at a keyboard until the character ‘m’ is entered.

E. Design an algorithm and the corresponding flowchart for checking the given character is a vowel or not.

F. Write the differences between an algorithm, flowchart and pseudocode.

CHAPTER 2

Algorithm Analysis

2.1 Introduction

Generally, people can think that a computer can do anything but it is difficult to make people understand a computer can do anything without instruction, programs or software. If people want to search anything in computer then they enter the information and after few seconds they get the desired result. But during this searching process a program is being executing in background and this process depends on the execution speed and organized storage of information. If our data or information is properly organized then searching process will take less amount of time and get the desired result faster.

The organization of data directly depends on the execution time. If information is well organized then the process gives fast result. Here process is nothing but a set of instruction. This set of instruction is termed as program.

2.2 Why to Study an Algorithm?

The study of algorithms, gives us a language to express performance as a function of problem size. If there is a software company and some people have created the particular software of that company. After some time, if there is some change in that software and some members of that technical team has switch the companies, then this task will be very complicated for the new members as they will not understand the coding. But if the proper documentation is available or an algorithm of the code is available then it is quite easy to understand the software. That is why algorithm plays an important role for constructing the software.

2.3 Definition of an Algorithm

Algorithm is a combination of sequence of finite number of steps defined to solve a particular problem. It is a well defined procedure which will take input and produce output. The input and output may be some data or values.

Properties of an algorithm:

Input: Zero or more input but is should be finite.

Output: It must contains at least one output and it should also be finite.

It should produce the output within the time.

It should be deterministic or we can say each and every step should be unambiguous.

Simplicity: Every step in an algorithm should perform at least one task.

It should be independent to programming languages or be generic to all programming languages.

2.4 Steps to Construct an Algorithm

There are following steps for constructing an algorithm:

Problem Definition: Know the problem clearly

Constraint to be satisfied: Requirement needed to satisfy the problem

Design the problem: Gather information to solve the problem

Draw the flow chart: Diagram for understanding the problem

Validation or Testing: Track an algorithm for different inputs

Implementation: Convert algorithm to programming languages

Analysis: Tracing and debugging the code, aposteriori analysis required.

Algorithms are used to convert our problem into one by one statement. These statements can be converted into computer programming instructions which form a program. This program is executed by computer