DEPARTMENT: INFORMATION TECHNOLOGY

OPTION: IT

MODULE CODE: ITLDS601

CREDITS: 12

ACADEMIC YEAR: 2025-2026

MODULE TITLE: ALGORITHM AND DATA STRUCTURE USING

C

January, 2026

MODULE LEADER: UWIZEYE Samuel

Purpose statement
This core module describes the skills, knowledge and attitude required to apply algorithm and
data structure using C. The trainee will be able to use algorithm for solving problems, apply c
programming and apply data structure using C. He/She also able to write flowchat and
pseudocode then translate into programming language.

~1~
 Assessment Methods

1. Theoretical assessment(Presentations, Group assignments, Quizzes, Formative

Assessments) ( 10 marks ).

2. Theoretical assessment (Invigilated CAT). ( 10 marks ).

3. Practical assessment. ( 30 marks ).

4. Final theoretical Exam and Final Practical Exam. (20 marks and 30 marks).

~2~
 Table of Contents
LEARNING UNIT 1-USE ALGORITHM TO SOLVE PROBLEMS........................................................8
Learning Outcome 1.1 Describe algorithm..............................................................................................8
1.1.1 Introduction to Algorithm.............................................................................................................8
1.1.2 Key concepts of algorithm in programming...............................................................................12
Learning Outcome 1.2 Design algorithm to solve a problem.................................................................14
1.2.1 Computer Systems and Sub-systems..........................................................................................14
1.2.2 Top-down design........................................................................................................................15
1.2.3 Algorithm purpose......................................................................................................................17
1.2.4 Test Data.....................................................................................................................................18
1.2.5 Trace tables.................................................................................................................................19
1.2.6 Validation and Verification.........................................................................................................21
1.2.7 Producing an Algorithm..............................................................................................................22
Learning Outcome 1.3 Select Algorithm type to solve a problem.........................................................22
Learning Outcome 1.4 Use Simple recursive algorithms type...............................................................23
1.4.1 The Three Laws of Recursion.....................................................................................................23
1.4.2 Examples on recursive algorithms..............................................................................................24
Learning Outcome 1.5 Use Backtracking Algorithms Type....................................................................26
1.5.1 Description of backtracking algorithm.......................................................................................26
1.5.2 Non-recursive backtracking, using a stack.................................................................................28
1.5.3 Keeping backtracking simple......................................................................................................30
1.5.4 Example of Application of Backtracking with constraint satisfaction.......................................31
Learning Outcome 1.6 Use Divide and conquer algorithms Type..........................................................34
1.6.1 Introduction to Divide and Conquer...........................................................................................34
1.6.2 Fundamentals of Divide and Conquer........................................................................................35
1.6.3 General algorithm for Divide and Conquer................................................................................35
1.6.4 Recurrence Relation for DAC algorithm....................................................................................36
1.6.5 Applications of Divide and Conquer..........................................................................................36
Learning Outcome 1.7 Use Dynamic programming algorithms type.....................................................53
1.7.1 Characteristics of Dynamic Programming..................................................................................54
1.7.2 Dynamic Programming Methods................................................................................................55
1.7.3 Solving a dynamic programming problem.................................................................................58

~3~
 Learning Outcome 1.8 Use Greedy Algorithms Type.............................................................................63
1.8.1 Description of greedy algorithm.................................................................................................64
1.8.2 Use of greedy approach for solving the activity selection problem............................................69
1.8.3 Greedy method vs Dynamic Programming.................................................................................73
Learning Outcome 1.9 Use Branch and bound algorithms Type............................................................73
1.9.1 Branch and bound algorithm introduction..................................................................................73
Learning Outcome 1.10 Use Brute force algorithms type......................................................................76
1.10.1. Introduction to brute force algorithm.......................................................................................76
1.10.2 Implementing the brute force search.........................................................................................78
1.10.3 Combinatorial explosion...........................................................................................................79
1.10.4 Speeding up brute-force searches.............................................................................................83
1.10.5 Reordering the search space......................................................................................................83
1.10.6 Alternatives to brute-force search.............................................................................................84
Learning Outcome 1.11 Use Randomized Algorithms Type...................................................................84
1.11.1 introduction to randomized algorithms.....................................................................................84
1.11.2 Computational complexity........................................................................................................85
1.11.3 Derandomization.......................................................................................................................85
Learning Outcome 1.12: Write algorithm pseudocode..........................................................................85
1.12.1 Description of algorithm pseudocode.......................................................................................86
1.12.2 Difference Between Algorithm and Pseudocode......................................................................86
1.12.3 Use of pseudocode syntax.........................................................................................................88
Learning Outcome 1.13: Write algorithm flowchart............................................................................104
1.13.1 Description of algorithm flowchart.........................................................................................104
1.13.2 Difference Between Algorithm and Flowchart.......................................................................106
1.13.3 Examples of flowchart............................................................................................................107
Learning outcome 1.14 Apply Algorithm complexity to measure its speed in execution....................110
LEARNING UNIT 2: APPLY C PROGRAMMING FUNDAMENTALS..............................................................113
Learning Outcome 2.1. Setup the environment of C programming.....................................................113
2.1.1 Introduction to C.......................................................................................................................113
2.1.2 Description of the environment of C programming..................................................................117
2.1.3 Steps to install tool to compile and execute C programs..........................................................118
2.1.4 Some commonly used shortcut keys of Dev-C ++...................................................................121
2.1.5 Some C compilers for UNIX/LINUX Operating System.........................................................122
Learning Outcome 2.2 Use C Syntax....................................................................................................122

~4~
 2.2.1 Structure of a C program...........................................................................................................122
2.2.2 Programming rules....................................................................................................................125
2.2.3 The ‘C’ Character Set...............................................................................................................126
2.2.4 Delimiters..................................................................................................................................127
2.2.5 The ‘C’ keywords.....................................................................................................................128
2.2.6 Identifiers..................................................................................................................................128
2.2.7 Input and Output in c................................................................................................................129
Learning Outcome 2.3: Describe Data Types.......................................................................................130
2.3.1 Overview of Data types............................................................................................................131
2.3.2. Description of 4 Data types in C..............................................................................................131
2.3.3 Data type modifiers in C...........................................................................................................133
2.3.4. Entire Data Types in C............................................................................................................135
2.3.5 Examples of Application of data types.....................................................................................136
Learning Outcome 2.4: Use variables..................................................................................................137
2.4.1 Description of variables............................................................................................................137
2.4.2 Key Differences between Identifier and Variable....................................................................139
2.4.3 Types of Variable......................................................................................................................139
Learning Outcome 2.5: Use Constants.................................................................................................141
2.5.1 Description of constants in C....................................................................................................141
2.5.2 Creation and Use of Constants in C..........................................................................................143
Learning Outcome 2.6: Use operators.................................................................................................144
2.6.1. Description and application of operators in C.........................................................................145
2.6.2 Priority of Operations and their Clubbing................................................................................155
Learning Outcome 2.7: Use conditions................................................................................................157
2.7.1 Description of Decision control statements in C......................................................................158
2.7.2 Application of Decision Control statements.............................................................................158
Learning Outcome 2.8: Use Loops.......................................................................................................165
2.8.1 Description of loops in C programming...................................................................................165
2.8.2 Application of loop control statements.....................................................................................165
Learning Outcome 2.9: Use arrays.......................................................................................................175
2.9.1 Description of arrays in C programming..................................................................................175
2.9.2 Single Dimensional Array.........................................................................................................176
2.9.3 Multi Dimensional Array..........................................................................................................178
Learning Outcome 2.10: Use functions in C Programming..................................................................181

~5~
 2.10.1 Description of functions..........................................................................................................181
2.10.2 Using of functions syntaxes....................................................................................................187
2.10.3 Category of functions..............................................................................................................189
2.10.5 Call by value and call by reference.........................................................................................193
2.10.6 Storage class............................................................................................................................197
Learning Outcome 2.11: Manage memory using pointers...................................................................204
2.11.1 Memory management in C programming introduction..........................................................204
2.11.2 Description of pointers in C....................................................................................................204
2.11.3 Using Operators that are used with Pointers...........................................................................205
2.11.4 Application of pointers in C....................................................................................................210
2.11.5 Use of Static Memory Allocation..........................................................................................217
2.11.6 Use of Dynamic Memory Allocation......................................................................................219
Learning Outcome 2.12: Use structure................................................................................................239
2.12.1 Description of structure in C...................................................................................................239
2.12.2 Use of Array Structures in C...................................................................................................242
2.12.3 Nested Structure in C..............................................................................................................245
2.12.4 Passing Structure to Function.................................................................................................250
2.12.5 Pointers to Structures in C......................................................................................................251
2.12.6 typedef in C.............................................................................................................................254
Learning Outcome 2.13: Use file I/O in C.............................................................................................258
2.13.1 Description of file I/O.............................................................................................................258
2.13.2 Steps for File Operations........................................................................................................259
LEARNING UNIT 3: APPLY DATA STRUCTURE USING C.............................................................................265
Learning outcome 3.1 Use Data Structure Type to use Solving a Problem..........................................265
3.1.1 Description of Data Structures using C....................................................................................265
3.1.2 Searching...................................................................................................................................269
3.1.3 List of Data Structures using C.................................................................................................283
Learning output 3.2 Use Array Data Structure Using C Programming Techniques..............................283
3.2.1 Description of array data structure............................................................................................283
3.2.2 Application of array structure using C......................................................................................284
3.2.3 Using arrays data structure operations......................................................................................284
Learning outcome 3.3 Use Linked List Data Structure Using C Programming Techniques...................285
3.3.1 Description of use of stack data structure using C....................................................................285
3.3.2 Applications of stack.................................................................................................................286

~6~
 3.3.3 Types of Linked List.................................................................................................................286
3.3.4 Basic Operations on Linked List...............................................................................................290
3.3.5 Demonstration of Linked List in a C program..........................................................................295
Learning outcome 3.4. Use Stack Data Structure Using C Programming Techniques..........................304
3.4.1 Description of use of stack data structure using C....................................................................304
3.4.2 Applications of stack................................................................................................................306
3.4.3 Operations on Stack..................................................................................................................306
3.4.4 Demonstration of Stack – using Array......................................................................................306
3.4.5 Demonstration of Stack – using LinkedList.............................................................................310
Learning outcome 3.5 Use Queue Data Structure Using C Programming Techniques.........................316
3.5.1 Description of queue data structure using C.............................................................................316
3.5.2 Operations on Queue.................................................................................................................319
3.5.4 Demonstration of Queue- using LinkedList.............................................................................325
Learning Outcome 3.6 Use Trees Data Structure Using C Programming Techniques..........................332
3.6.1 Description of tree data structure..............................................................................................332
3.6.2 General tree...............................................................................................................................333
3.6.3 Important Terms........................................................................................................................335
3.6.4 Applications of trees.................................................................................................................336
3.6.5 Binary Tree...............................................................................................................................336
3.6.6 Binary Search Tree...................................................................................................................350
3.6.7 AVL Tree..................................................................................................................................357
3.6.8 Heap..........................................................................................................................................363
Learning outcome 3.7 Use Hashing Data Structure Using C Programming Techniques.......................367
3.7.1 Description of hashing data structure.......................................................................................367
3.7.2 Implementation.........................................................................................................................367
Learning outcome 3.8 Use Graph Data Structure Using C Programming Techniques..........................374
3.8.1 Introduction to graph in data structure......................................................................................374
3.8.2 Graph Terminology...................................................................................................................375
3.8.3 Graph to a Tree.........................................................................................................................377
3.8.4 Graph Traversal........................................................................................................................378
Exercises..............................................................................................................................................386
References:..............................................................................................................................................398

~7~
~8~
LEARNING UNIT 1-USE ALGORITHM TO SOLVE PROBLEMS

Learning Outcomes:
1.1 Describe algorithm.
1.2 Design Algorithm to solve a problem
1.3 Select Algorithm type to solve a problem
1.4 Use simple recursive algorithms type
1.5 Use Backtracking algorithms type
1.6 Use Divide and conquer algorithms type
1.7 Use Dynamic programming algorithms type
1.8 Use Greedy algorithms type
1.9 Use Branch and bound algorithms type
1.10 Use Brute force algorithms type
1.11 Use Randomized algorithms type
1.12 Write Algorithm pseudocode
1.13 Write Algorithm flowchart
1.14 Apply Algorithm complexity to measure its speed
in execution

Learning Outcome 1.1 Describe algorithm.

1.1.1 Introduction to Algorithm
a. Definition:

An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem,

based on conducting a sequence of specified actions.

A process or set of rules to be followed in calculations or other problem-solving operations,

especially by a computer.

Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a

certain order to get the desired output.

~9~
Algorithms are generally created independent of underlying languages, i.e. an algorithm can be
implemented in more than one programming language.

b. Characteristics of an Algorithm

An algorithm must possess following characteristics:

1. Finiteness: An algorithm should have finite number of steps and it should end after a
finite time.
2. Input: An algorithm may have many inputs or no inputs at all.
3. Output: It should result at least one output.
4. Definiteness: Each step must be clear, well-defined and precise. There should be no any
ambiguity.
5. Effectiveness: Each step must be simple and should take a finite amount of time.

c. Importance of using algorithms

• Aid in the management and handling of huge amounts of data, even if there are several large
databases involved.
• Simplify applicability of program.
• Knowledge of algorithms, in combination with data structures, enables a programmer to
write the proper codes quickly and efficiently.
• Choosing the right algorithms (and data structure) will ensure the program runs fast while
also maintaining integrity and reliability of data.
d. Expressing an algorithm

Algorithms can be expressed in many kinds of notation, including natural languages,

pseudocode, flowcharts, and programming languages. Natural language expressions of
algorithms tend to be verbose and ambiguous, and are rarely used for complex or technical
algorithms. Pseudocode and flowcharts are structured ways to express algorithms that avoid
many of the ambiguities common in natural language statements, while remaining independent

~ 10 ~
of a particular implementation language. Programming languages are primarily intended for
expressing algorithms in a form that can be executed by a computer, but are often used as a way
to define or document algorithms.

e. Writing algorithm

In order to write an algorithm, following things are needed as a pre-requisite:

1. The problem that is to be solved by this algorithm.

2. The constraints of the problem that must be considered while solving the problem.
3. The input to be taken to solve the problem.
4. The output to be expected when the problem the is solved.
5. The solution to this problem, in the given constraints.
Then the algorithm is written with the help of above parameters such that it solves the problem.

There are no well-defined standards for writing algorithms. Rather, it is problem and resource
dependent. Algorithms are never written to support a particular programming code.

As we know that all programming languages share basic code constructs like loops (do, for,
while), flow-control (if-else), etc. These common constructs can be used to write an algorithm.

We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is
a process and is executed after the problem domain is well-defined. That is, we should know the
problem domain, for which we are designing a solution.

Example:
Problem − Design an algorithm to add two numbers and display the result.

Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP

~ 11 ~
Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be
written as −

Step 1 − START ADD

Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

In design and analysis of algorithms, usually the second method is used to describe an
algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted
definitions. He can observe what operations are being used and how the process is flowing.

Writing step numbers, is optional.

We design an algorithm to get a solution of a given problem. A problem can be solved in more
than one ways.

Hence, many solution algorithms can be derived for a given problem. The next step is to
analyze those proposed solution algorithms and implement the best suitable solution.

f. Variables

~ 12 ~
Variables are symbolic names given to data where the value of the data stored may
change during the execution of the program. In effect, a variable is a named area of memory
used to store data.
In a program every variable has:
 Name(identifier)
 Data type (a set of values and a set of operations on those values).
 Size
 Address (memory location)
 Value

1.1.2 Key concepts of algorithm in programming

a. Source code: A computer program's source code is the collection of files needed to
convert from human-readable form to some kind of computer-executable form.
b. Machine code: Sometimes referred to as machine language or object code, machine
code is a collection of binary digits or bits that the computer reads and interprets.
Machine language is the only language a computer is capable of understanding.
c. Editing: The first step in developing an application in programming is to write/edit
the source code. The source code contains all the instructions which needs to be executed
by the machine in a text format (understandable by humans).

~ 13 ~
d. Compiling vs interpreting: To convert source code into machine code, we use either
a compiler or an interpreter.

e. Linking, loading and debugging

The linking is performed by a linker.

It will search all the object files and replace all the undefined references with the referenced
machine code within the library files. At the end of the linking process we are going to have
an executable file.

Interpreter Compiler

Translates program one statement Scans the entire program and translates it as
at a time. a whole into machine code.

Interpreters usually take less

Compilers usually take a large amount of
amount of time to analyze the
time to analyze the source code. However,
source code. However, the overall
the overall execution time is comparatively
execution time is comparatively
faster than interpreters.
slower than compilers.

Generates Object Code which further

No Object Code is generated, hence
requires linking, hence requires more
are memory efficient.
memory.

Programming languages like

Programming languages like C, C++, Java
JavaScript, Python, Ruby use
use compilers.
interpreters.

Loading
The final step is the loading of the program file into the computer’s memory so that it can be
executed. This is performed by a loader. Usually the linked will include the loader into the

~ 14 ~
 executable file. When we run the executable it will trigger the loader which will load the
program into the memory and the execution will begin.

Debugging means to correct or remove errors (bugs) if there are in a program.

Programming errors come in 3 varieties:

a) Compiler (syntax) error:

You get it when you’ve broken the rules of computer programming language.

Example: spelling printf as prinntf or printif.

You also receive a compiler error, if accidentally use the wrong punctuation or place
punctuation in the wrong place.

b) Run-time error:

It can be caused by attempting to do impossible arithmetic operations, such calculating non-

numeric data, dividing a number by zero, or find the square root of a negative number.

c) Logic error:

Your application runs but produces incorrect result. Perhaps the results of calculation are
incorrect or the wrong text appears, or the text is ok but appears in the wrong location.

Learning Outcome 1.2 Design algorithm to solve a problem

1.2.1 Computer Systems and Sub-systems
 A computer system is a device which performs a task or solves a problem, it is made up of
hardware, software, data, communication and people.
 A computer system is made up of sub-systems. These sub-systems are made up of sub-systems
and so on, until they only perform one task.

~ 15 ~
 1.2.2 Top-down design

Use top-down design, structure diagrams, library routines, sub-routines and Standard methods of
solution
a. Top-down design

 Top-down design is breaking down a system into smaller sub-systems and breaking these sub-
systems down into smaller sub-systems until each sub-system performs one task.
 This is a method of breaking down a problem into smaller problems.
 Doing this allows several programmers to work on different sub-systems; thus, making the
design process more efficient.

b. Structure diagrams

Structure diagrams are used to represent top-down design in a hierarchical form.

~ 16 ~
 c. Library routines

 A library routine is a set of programming instructions for a specific task available to use.
 It is debugged and tested before being made available.

d. Sub-routines
 A sub-routine is a set of programming instructions for a given task that forms a sub-system.
 Sub-routines are written in high-level programming languages (they may be referred to as
functions or procedures).

e. Standard methods of solution

 Some tasks are needed frequently (for example, taking the square root of a number). These
are referred to as standard solutions).
 What high-level programming languages can do is provide these standard solutions as
standard functions or procedures.
 Library routines can also provide standard solutions.

~ 17 ~
1.2.3 Algorithm purpose
Work out the purpose of a given algorithm with given Value 45

Solution

Input data: 45

The predefined function DIV gives the integer result of a division.

Example: 10 DIV 3 = 3

The predefined function MOD gives the remainder of a division.

Example: 10 MOD 3 = 1

~ 18 ~
 Purpose: Converts a decimal number into binary.

1.2.4 Test Data

Test data commonly include the following types:
 Normal Test Data
 Abnormal Test Data
 Extreme Test Data
 Boundary Test Data
Example: Five test scores, out of 25, are input and validated. The average is output. Any input
values out of range are rejected with a suitable error message.

Suggest and apply suitable test data.

~ 19 ~
 a. Normal Test Data:

 Normal test data consists of values which are expected to be accepted by an algorithm.
 Test data: 5, 10
 Expected result: both values should be accepted.

b. Abnormal Test Data:

 Abnormal test data consists of values which are expected to be rejected by an algorithm.
 Test data: 45, -19
 Expected result: both values should be rejected.

c. Extreme Test Data:

 Extreme test data consists of the smallest and largest possible values which are accepted by an
algorithm.
 Test data: 0, 25
 Expected result: both values should be accepted.

d. Boundary Test Data:

 Boundary test data is used to determine where the smallest and largest values occur.
 Test data: 25, 26
 Expected result: 25 should be accepted, 26 should be rejected.

1.2.5 Trace tables

Use Trace Tables to find the value of Variables at each step in an algorithm.
Example 1: Study the flowchart and complete the trace table for the input values.

~ 20 ~
Input data:

1.8, 2.0, 1.0, 1.3, 1.0, 2.5, 2.0, 1.3, 1.8, 1.3, -1

Solution:

~ 21 ~
 1.2.6 Validation and Verification
a. Validation is checking if a value is reasonable before being accepted into a computer
system.

Examples of different types of validation checks include:

 Range checks - A range check checks if a number input is in a specified range.
 Length checks - A length check checks if data input contains a certain number of characters or a
number of characters in a specified range.
 Type checks - A type check checks if data input is a certain type (such as string or integer).
 Format checks - A format check checks if data input is in a certain format (pattern).
 Presence checks - A presence check checks if data has been entered and the value isn’t null.
 Character checks - A character check checks if a string input does not contain any invalid
characters or symbols.
 Check digits - A form of error detection. A check digit is the final digit in a code of numbers. It
is calculated from all the other digits in the code. Its purpose is to spot human errors on data
entry.

b. Verification is checking if data has been accurately input into a computer or transferred
rom one part of a computer system to another.

Examples of different types of verification methods include:

 Double entry - In double entry, data is input twice. The computer checks whether both entries
match.
 Screen / visual check - In a screen/visual check, after the user has entered data, the computer
displays the input for the user to confirm that it is correct.
 Parity check - A parity check is a method of error detection in data transmission from one
device/medium to another.
• For example, if a byte of data is transmitted, it would have a parity bit allocated to it before it
was transmitted.
• Systems which use odd parity have an odd number of 1-bits.
• Systems which use even parity have an even number of 1-bits.

~ 22 ~
 Checksum - A checksum is another method of error detection in data transmission. Data is sent
in blocks and at the end of each block, another value is added – this is the checksum.

1.2.7 Producing an Algorithm

Three main stages are involved in creating an algorithm for a given problem:
 Data input
 Data processing
 Output

Consider a computer program that finds the average value of three numbers:

 First, the program must prompt the user to enter the numbers (data input).
 Next, the program calculates the average value of the numbers (data processing).
 Finally, the program displays the result on the computer’s screen (results output).

Learning Outcome 1.3 Select Algorithm type to solve a

problem
Algorithms that use a similar problem-solving approach can be grouped together

This classification scheme is neither exhaustive nor disjoint

The purpose is not to be able to classify an algorithm as one type or another, but to highlight the
various ways in which a problem can be solved.

Algorithm types we will consider include:

 Simple recursive algorithms

 Backtracking algorithms
 Divide and conquer algorithms
 Dynamic programming algorithms
 Greedy algorithms
 Branch and bound algorithms

~ 23 ~
  Brute force algorithms
 Randomized algorithms

Learning Outcome 1.4 Use Simple recursive algorithms type

Recursive algorithm is a method of simplification that divides the problem into sub-problems of
the same nature. The result of one recursion is the input for the next recursion. In simpler words,
it’s an Algorithm that calls itself repeatedly until the problem is solved.

It is called “simple” because several of the other algorithm types are inherently recursive.

More generally if a problem can be solved utilizing solutions to smaller versions of the same
problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive
algorithm to solve that problem. For example, the elements of a recursively defined set, or the
value of a recursively defined function can be obtained by a recursive algorithm.

If a set or a function is defined recursively, then a recursive algorithm to compute its members or
values mirrors the definition. Initial steps of the recursive algorithm correspond to the basis
clause of the recursive definition and they identify the basic elements.

They are then followed by steps corresponding to the inductive clause, which reduce the
computation for an element of one generation to that of elements of the immediately preceding
generation.

In general, recursive computer programs require more memory and computation compared with
iterative algorithms, but they are simpler and for many cases a natural way of thinking about the
problem.

1.4.1 The Three Laws of Recursion

All recursive algorithms must obey three important laws:

 A recursive algorithm must have a base case.

 A recursive algorithm must change its state and move toward the base case.
 A recursive algorithm must call itself, recursively.

~ 24 ~
First, a base case is the condition that allows the algorithm to stop recursing. A base case is
typically a problem that is small enough to solve directly.

To obey the second law, we must arrange for a change of state that moves the algorithm toward
the base case. A change of state means that some data that the algorithm is using is modified.
Usually the data that represents our problem gets smaller in some way.

The final law is that the algorithm must call itself. This is the very definition of recursion.
Recursion is an elegant expression of solving a problem by breaking it down into a smaller and
easier problems.

1.4.2 Examples on recursive algorithms

Example 1: Algorithm for finding the k-th even natural number

Algorithm 1: Even(positive integer k)

Input: k , a positive integer
Output: k-th even natural number (the first even being 0)

Algorithm:
if k = 1, then return 0;
else return Even(k-1) + 2 .

Here the computation of Even(k) is reduced to that of Even for a smaller input value, that
is Even(k-1). Even(k) eventually becomes Even(1) which is 0 by the first line. For example, to
compute Even(3), Algorithm Even(k) is called with k = 2. In the computation
of Even(2), Algorithm Even(k) is called with k = 1. Since Even(1) = 0, 0 is returned for the
computation of Even(2), and Even(2) = Even(1) + 2 = 2 is obtained. This value 2 for Even(2) is
now returned to the computation of Even(3), and Even(3) = Even(2) + 2 = 4 is obtained.

Example 2: Algorithm to find the factorial of a number n using a function

As we know factorial of a number is defined as:

n! = n(n-1)(n-2)...1

or in other words:
~ 25 ~
n! = n(n-1)!

The recursive version uses the second definition: n! = n * (n - 1)!, which is naturally
a recursive definition. It defines the factorial of n in terms of the factorial of a smaller version (n
- 1). We don't need to specify in advance, how many times the loop will run.

function factorialRecursive(n) {

let result = 0;

if (n == 1)

// base case: n==1

result = 1;

// recursive case

else result = n * factorialRecursive(n - 1);

return result;

factorialRecursive(4);

Recursive algorithms can also be used to test objects for membership in a set.

Example 3: Algorithm for testing whether or not a number x is a natural number

Algorithm 4 Natural(a number x)
Input: A number x
Output: "Yes" if x is a natural number, else "No"

Algorithm:
if x < 0, then return "No"
else
if x = 0, then return "Yes"
else return Natural( x - 1 )

~ 26 ~
Learning Outcome 1.5 Use Backtracking Algorithms Type
1.5.1 Description of backtracking algorithm
a. Definition

Backtracking is a very important concept in computer science and is used in many applications.
Generally, we use it when all possible solutions of a problem need to be explored. It is also often
employed to identify solutions that satisfy a given criterion also called a constraint.

b. State Space Tree

A space state tree is a tree representing all the possible states (solution or nonsolution) of the
problem from the root as an initial state to the leaf as a terminal state.

State Space Tree

c. Pseudocode

Backtrack(x)

if x is not a solution

return false

if x is a new solution

add to list of solutions

backtrack(expand x)
~ 27 ~
 d. Usage considerations

In any backtracking algorithm, the algorithm seeks a path to a feasible solution that includes
some intermediate checkpoints. If the checkpoints do not lead to a viable solution, the problem
can return to the checkpoints and take another path to find a solution. Consider the following
scenario:

In this case, S represents the problem's starting point. You start at S and work your way to
solution S1 via the midway point M1. However, you discovered that solution S1 is not a viable
solution to our problem. As a result, you backtrack (return) from S1, return to M1, return to S,
and then look for the feasible solution S2. This process is repeated until you arrive at a workable
solution.

1. S1 and S2 are not viable options in this case. According to this example, only S3 is a viable
solution. When you look at this example, you can see that we go through all possible

~ 28 ~
 combinations until you find a viable solution. As a result, you refer to backtracking as a brute-
force algorithmic technique.

2. A "space state tree" is the above tree representation of a problem. It represents all possible
states of a given problem (solution or non-solution).

The final algorithm is as follows:

 Step 1: Return success if the current point is a viable solution.

 Step 2: Otherwise, if all paths have been exhausted (i.e., the current point is an endpoint),
return failure because there is no feasible solution.

 Step 3: If the current point is not an endpoint, backtrack and explore other points, then repeat
the preceding steps.

e. Early stopping variants

The pseudo-code above will call output for all candidates that are a solution to the given
instance. The algorithm can be modified to stop after finding the first solution, or a specified
number of solutions; or after testing a specified number of partial candidates, or after spending a
given amount of CPU time.

1.5.2 Non-recursive backtracking, using a stack

Backtracking is a rather typical recursive algorithm, and any recursive algorithm can be rewritten
as a stack algorithm. In fact, that is how your recursive algorithms are translated into machine or
assembly language.

boolean solve(Node n) {
put node n on the stack;
while the stack is not empty {
if the node at the top of the stack is a leaf {
if it is a goal node, return true
else pop it off the stack
}

~ 29 ~
 else {
if the node at the top of the stack has untried children
push the next untried child onto the stack
else pop the node off the stack
}
return false
}

Starting from the root, the only nodes that can be pushed onto the stack are the children of the
node currently on the top of the stack, and these are only pushed on one child at a time; hence,
the nodes on the stack at all times describe a valid path in the tree.

Nodes are removed from the stack only when it is known that they have no goal nodes among
their descendants. Therefore, if the root node gets removed (making the stack empty), there must
have been no goal nodes at all, and no solution to the problem.

When the stack algorithm terminates successfully, the nodes on the stack form (in reverse order)
a path from the root to a goal node.

Similarly, when the recursive algorithm finds a goal node, the path information is embodied (in
reverse order) in the sequence of recursive calls. Thus as the recursion unwinds, the path can be
recovered one node at a time, by (for instance) printing the node at the current level, or storing it
in an array.

Here is the recursive backtracking algorithm, modified slightly to print (in reverse order) the
nodes along the successful path:

boolean solve(Node n) {
if n is a leaf node {
if the leaf is a goal node {
print n
return true
}

~ 30 ~
 else return false
} else {
for each child c of n {
if solve(c) succeeds {
print n
return true
}
}
return false
}
}
1.5.3 Keeping backtracking simple

All of these versions of the backtracking algorithm are pretty simple, but when applied to a real
problem, they can get pretty cluttered up with details. Even determining whether the node is a
leaf can be complex: for example, if the path represents a series of moves in a chess endgame
problem, the leaves are the checkmate and stalemate solutions.

To keep the program clean, therefore, tests like this should be buried in methods. In a chess
game, for example, you could test whether a node is a leaf by writing a gameOver method (or
you could even call it isLeaf). This method would encapsulate all the ugly details of figuring out
whether any possible moves remain.

Notice that the backtracking altorithms require us to keep track, for each node on the current
path, which of its children have been tried already (so we don't have to try them again).

In the above code we made this look simple, by just saying for each child c of n. In reality, it
may be difficult to figure out what the possible children are, and there may be no obvious way to
step through them. In chess, for example, a node can represent one arrangement of pieces on a
chessboard, and each child of that node can represent the arrangement after some piece has made
a legal move. How do you find these children, and how do you keep track of which ones you've
already examined?

~ 31 ~
The most straightforward way to keep track of which children of the node have been tried is as
follows: Upon initial entry to the node (that is, when you first get there from above), make a list
of all its children. As you try each child, take it off the list. When the list is empty, there are no
remaining untried children, and you can return "failure." This is a simple approach, but it may
require quite a lot of additional work.

There is an easier way to keep track of which children have been tried, if you can define an
ordering on the children. If there is an ordering, and you know which child you just tried, you
can determine which child to try next.

For example, you might be able to number the children 1 through n, and try them in numerical
order. Then, if you have just tried child k, you know that you have already tried
children 1 through k-1, and you have not yet tried children k+1 through n. Or, if you are trying to
color a map with just four colors, you can always try red first, then yellow, then green, then blue.
If child yellow fails, you know to try child green next. If you are searching a maze, you can try
choices in the order left, straight, right (or perhaps north, east, south, west).

It isn't always easy to find a simple way to order the children of a node. In the chess game
example, you might number your pieces (or perhaps the squares of the board) and try them in
numerical order; but in addition each piece may also have several moves, and these must also be
ordered.

You can probably find some way to order the children of a node. If the ordering scheme is
simple enough, you should use it; but if it is too cumbersome, you are better off keeping a list of
untried children.

1.5.4 Example of Application of Backtracking with constraint satisfaction

Problem: You want to find all the possible ways of arranging 2 boys and 1 girl on 3 benches.
Constraint: Girl should not be on the middle bench.

Solution: There are a total of 3! = 6 possibilities. We will try all the possibilities and get the
possible solutions. We recursively try all the possibilities.

All the possibilities are:

~ 32 ~
 All the possibilities

The following state space tree shows the possible solutions.

State tree with all the solutions

Example 2:

You need to arrange the three letters x, y, and z so that z cannot be next to x.

According to the backtracking, you will first construct a state-space tree. Look for all possible
solutions and compare them to the given constraint. You must only keep solutions that meet the

~ 33 ~
following constraint:

The following are possible solutions to the problems: (x,y,z), (x,z,y), (y,x,z), (y,z,x), (z,x,y)
(z,y,x).

Nonetheless, valid solutions to this problem are those that satisfy the constraint that keeps only
(x,y,z) and (z,y,x) in the final solution set.

Example 3: To color a map with no more than four colors:

– color(Country n)

• If all countries have been colored (n > number of countries) return

success; otherwise,

• For each color c of four colors,

– If country n is not adjacent to a country that has been colored c

» Color country n with color c

» recursivly color country n+1

~ 34 ~
 » If successful, return success

. Return failure (if loop exits)

Learning Outcome 1.6 Use Divide and conquer algorithms

Type
1.6.1 Introduction to Divide and Conquer
Divide and Conquer is broadly a 3-step strategy:

1. Divide the actual problem into sub-problems (A subproblem is just a smaller instance of the
same problem).

2. Conquer i.e. recursively solve each sub-problem.

3. Combine the solutions of the sub-problems to get the solution to the actual problem.

For example, Let there be a problem of size N and let us divide this problem into 4 sub-problems
say n1, n2, n3, and n4.

Let the time taken to complete the whole problem be T(N), time taken to complete n1, n2, n3, n4
respectively be T(n1), T(n2), T(n3) and T(n4), time taken in dividing the problem into sub-
problems be D(N), time taken to combine the solutions of sub-problems into one final solution
be C(N).

~ 35 ~
Then,
T(N) = T(n1) + T(n2) + T(n3) + T(n4) + D(N) + C(N) (If N is large)
T(N) = g(n) (If N is small)

Traditionally, an algorithm is only called divide and conquer if it contains two or more recursive
calls

1.6.2 Fundamentals of Divide and Conquer

The Divide and Conquer strategy follows two fundamentals:

1. Relational formula

a. It is the first thing required to solve a problem by divide and conquer effectively.

b. The relational formula is the formula that we generate for a given technique.

c. We need this formula to apply divide and conquer, break the problem into sub-problems and
then solve them recursively.

2. Stopping condition

a. It defines the point at which we need to stop dividing our main problem into sub-problems and
start combining the results that we get out of sub-problems.

b. We can also say that the stopping condition defines the base case of our recursive algorithm.

1.6.3 General algorithm for Divide and Conquer

Consider a problem named DAC having array ‘a’, smallest index as ‘i’ and the largest index
being ‘j’.

DAC(a, i, j){

if(small (i,j))

return solution(small(i, j))

else{

m = Divide(i, j);

b = DAC(a, i, m);

~ 36 ~
c = DAC(a, m, j);

d = Combine(b,c);

1.6.4 Recurrence Relation for DAC algorithm

The general time complexity analysis of DAC algorithm is given by the recurrence relation.

T(n) = g(n) if n is small

T(n) = T(n1) + T(n2) + T(n3)+ …+ T(nr) + F(n) when n is large

Where T(n) is the time for Divide and Conquer of size n. g(n) is the computing time required for
solve small input. The F(n) is the time required in dividing the problem P and combining the
solutions to sub problems.

If we want to divide a problem of the size n into a size of n/b taking f(n) time to divide and
combine, then we can set up recurrence relation for obtaining size for n is:

T(n) = a T(n/b) +f(n)

Where T(n)- Time for size n

a- Number of sub problems

n/b- Time for size sub problem n/n

f(n)- Time required for dividing problem into sub problems.

The above equation is called divide and conquer recurrence. The order of growth of T(n)
depends upon the constants a, b and order of growth function f(n).

1.6.5 Applications of Divide and Conquer

Divide and conquer strategy has various application areas such as:

a. Binary search
b. Merge sort
c. Quicksort

~ 37 ~
 d. Strassen’s matrix multiplication
e. Karatsuba algorithm
and many more.

a. Binary search

Binary search is also implemented by the divide and conquer strategy. This is used to find a
particular element in a sorted array.

While implementing binary search, we divide the array into 2 halves and check if the number to
be searched could be on the left half or right half. Then, we go to that half and again divide the
array into further two halves. This process goes on until the number to be searched is found.

Note: - There is another thought of school which says that binary search does not come directly
under the divide and conquer. Rather, it is implemented using an altogether different
methodology named ‘Decrease and Conquer’.

Let us see the implementation of binary search using an example:

The general steps are discussed below.

1. The array in which searching is to be performed is:

Let x = 4 be the element to be searched.

2. Set two pointers low and high at the lowest and the highest positions respectively.

~ 38 ~
3. Find the middle element mid of the array ie. arr[(low + high)/2] = 6.

4. If x == mid, then return mid. Else, compare the element to be searched with m.

5. If x > mid, compare x with the middle element of the elements on the right side of mid. This is
done by setting low to low = mid + 1.
6. Else, compare x with the middle element of the elements on the left side of mid. This is done by
setting high to high=mid -1

7. Repeat steps 3 to 6 until low meets high.

8. x = 4 is found.

The algorithm for binary search will be as follows:

binarySearch(arr, x, low, high)

if low > high

~ 39 ~
 return False

else

mid = (low + high) / 2

if x == arr[mid]

return mid

else if x > arr[mid] // x is on the right side

return binarySearch(arr, x, mid + 1, high)

else // x is on the right side

return binarySearch(arr, x, low, mid - 1)

b. Merge sort

It divides the given array into halves which further divide themselves into two halves until
the array length becomes one.

It then starts merging the two sorted halves from bottom to top until we get the final sorted
array.

~ 40 ~
 Merge sort example

Using the Divide and Conquer technique, we divide a problem into subproblems. When the
solution to each subproblem is ready, we 'combine' the results from the subproblems to solve the
main problem.

Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array
starting at index p and ending at index r, denoted as A[p..r].

Divide

~ 41 ~
If q is the half-way point between p and r, then we can split the subarray A[p..r] into two
arrays A[p..q] and A[q+1, r].

Conquer

In the conquer step, we try to sort both the subarrays A[p..q] and A[q+1, r]. If we haven't yet
reached the base case, we again divide both these subarrays and try to sort them.

Combine

When the conquer step reaches the base step and we get two sorted subarrays A[p..q] and A[q+1,
r] for array A[p..r], we combine the results by creating a sorted array A[p..r] from two sorted
subarrays A[p..q] and A[q+1, r].

MergeSort Algorithm

The MergeSort function repeatedly divides the array into two halves until we reach a stage where
we try to perform MergeSort on a subarray of size 1 i.e. p == r.

After that, the merge function comes into play and combines the sorted arrays into larger arrays
until the whole array is merged.

MergeSort(A, p, r):

if p > r

return

q = (p+r)/2

mergeSort(A, p, q)

mergeSort(A, q+1, r)

merge(A, p, q, r)

To sort an entire array, we need to call MergeSort(A, 0, length(A)-1).

c. Quicksort

Quicksort is a sorting algorithm based on the divide and conquer approach where

~ 42 ~
An array is divided into subarrays by selecting a pivot element (element selected from the array).
While dividing the array, the pivot element should be positioned in such a way that elements less
than pivot are kept on the left side and elements greater than pivot are on the right side of the
pivot.

The left and right subarrays are also divided using the same approach. This process continues
until each subarray contains a single element.

At this point, elements are already sorted. Finally, elements are combined to form a sorted array.

There are many different versions of quickSort that pick pivot in different ways.

Always pick first element as pivot.

Always pick last element as pivot (implemented below)

Pick a random element as pivot.

Pick median as pivot.

Working of Quicksort Algorithm

1. Select the Pivot Element

There are different variations of quicksort where the pivot element is selected from different
positions. Here, we will be selecting the rightmost element of the array as the pivot element.

2. Rearrange the Array

Now the elements of the array are rearranged so that elements that are smaller than the pivot are
put on the left and the elements greater than the pivot are put on the right.

~ 43 ~
Here's how we rearrange the array:

A pointer is fixed at the pivot element. The pivot element is compared with the elements
beginning from the first index.

If the element is greater than the pivot element, a second pointer is set for that element.

Now, pivot is compared with other elements. If an element smaller than the pivot element is
reached, the smaller element is swapped with the greater element found earlier.

~ 44 ~
Again, the process is repeated to set the next greater element as the second pointer. And, swap it
with another smaller element.

The process goes on until the second last element is reached.

Finally, the pivot element is swapped with the second pointer.

3. Divide Subarrays

Pivot elements are again chosen for the left and the right sub-parts separately. And, step 2 is
repeated.

~ 45 ~
Select pivot element of in each half and put at correct place using recursion

The subarrays are divided until each subarray is formed of a single element. At this point, the
array is already sorted.

Quick Sort Algorithm

quickSort(array, leftmostIndex, rightmostIndex)

if (leftmostIndex < rightmostIndex)

pivotIndex <- partition(array,leftmostIndex, rightmostIndex)

quickSort(array, leftmostIndex, pivotIndex - 1)

quickSort(array, pivotIndex, rightmostIndex)

partition(array, leftmostIndex, rightmostIndex)

set rightmostIndex as pivotIndex

storeIndex <- leftmostIndex - 1

for i <- leftmostIndex + 1 to rightmostIndex

if element[i] < pivotElement

swap element[i] and element[storeIndex]

~ 46 ~
 storeIndex++

swap pivotElement and element[storeIndex+1]

return storeIndex + 1

The working of quicksort algorithm with the help of the illustrations below.

~ 47 ~
 d. Strassen’s Matrix Multiplication

The main idea is to use the divide and conquer technique in this algorithm – divide matrix A &
matrix B into 8 submatrices and then recursively compute the submatrices of C.

Consider the following matrices A and B:

A = |a b|, B = |e f| and we know A*B = matrix C = |ae+bg af+bh|

|c d| |g h| |ce+dg cf+dh|

There will be 8 recursive calls:

a*e

b*g

a*f

b*h

c*e

~ 48 ~
d*g

c*f

d*h

The above strategy is the basic strategy

But Strassen came up with a solution where we don’t need 8 recursive calls but can be done in
only 7 calls and some extra addition and subtraction operations.

Strassen’s 7 calls are as follows:

a * (f - h)

(a + b) * h

(c + d) * e

d * (g - e)

(a + d) * (e + h)

(b - d) * (g + h)

(a - c) * (e + f)

Our new matrix C’s new quadrants

matrix C = |p5+p4-p2+p6 p1+p2 |

~ 49 ~
 | p3+p4 p1+p5-p3-p7 |

Strassen’s Submatrix

p5+p4-p2+p6 = (a+d)*(e+h) + d*(g-e) - (a+b)*h + (b-d)*(g+h)

= (ae+de+ah+dh) + (dg-de) - (ah+bh) + (bg-dg+bh-dh)

= ae+bg

p1+p2 = a*(f-h) + (a+b)*h

= (af-ah) + (ah+bh)

= af+bh

p3+p4 = (c+d)*e + d*(g-e)

= (ce+de) + (dg-de)

= ce+dg

p1+p5-p3-p7 = a*(f-h) + (a+d)*(e+h) - (c+d)*e - (a-c)*(e+f)

= (af-ah) + (ae+de+ah+dh) -(ce+de) - (ae-ce+af-cf)

~ 50 ~
 = cf+dh

Algorithm for Strassen’s multiplication

Divide matrix A and matrix B in 4 sub-matrices of size N/2 x N/2 as shown above.

Calculate the 7 matrix multiplications recursively.

Compute the submatrices of C.

Combine these submatrices into our new matrix C

begin
If n = threshold then compute
C = a * b is a conventional matrix.
Else
Partition a into four sub matrices a11, a12, a21, a22.
Partition b into four sub matrices b11, b12, b21, b22.
Strassen ( n/2, a11 + a22, b11 + b22, d1)
Strassen ( n/2, a21 + a22, b11, d2)
Strassen ( n/2, a11, b12 – b22, d3)
Strassen ( n/2, a22, b21 – b11, d4)
Strassen ( n/2, a11 + a12, b22, d5)
Strassen (n/2, a21 – a11, b11 + b22, d6)
Strassen (n/2, a12 – a22, b21 + b22, d7)

C = d1+d4-d5+d7 d3+d5
d2+d4 d1+d3-d2-d6

end if

return (C)
end.

~ 51 ~
 e. Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm that uses a divide and conquer
approach to multiply two numbers. It was discovered by Anatoly Karatsuba in 1960 and
published in 1962.

It is faster than the naive algorithm for multiplying two numbers which requires n2n2 single-digit
products. As an example, the Karatsuba algorithm requires 3^10 = 59,049 single-digit
multiplications to multiply two 1024-digit numbers (n = 1024 = 2^10), whereas the classical
algorithm requires (2^10)^2 = 1,048,576 single-digit multiplications.

The key idea is to reduce the four sub-problems in multiplication to three unique problems.
Thus, on calculating the three unique sub-problems, the original four sub-problems are solved
using addition or subtraction operation. Hence, the speed-up.
Basically Karatsuba stated that if we have to multiply two n-digit numbers x and y, this can be
done with the following operations, assuming that B is the base of m and m < n (for instance: m
= n/2)

First both numbers x and y can be represented as x1,x2 and y1,y2 with the following formula.
x=x1∗Bm+x2x=x1∗Bm+x2
y=y1∗Bm+y2y=y1∗Bm+y2
The product x X y becomes the following product:

xy=(x1∗Bm+x2)(y1∗Bm+y2)xy=(x1∗Bm+x2)(y1∗Bm+y2)
=>xy=x1∗y1∗B(2m)+x1∗y2∗Bm+x2∗y1∗Bm+x2∗y2=>xy=x1∗y1∗B(2m)
+x1∗y2∗Bm+x2∗y1∗Bm+x2∗y2
Observe that there are 4 sub-problems: X1 * Y1, X1 * Y2, X2 * Y1 and X2 * Y2

With a clever insight, we can reduce this to 3 sub-problems and hence, the acceleration.
Let a=x1∗y1a=x1∗y1, b=x1∗y2+x2∗y1b=x1∗y2+x2∗y1 and c=x2∗y2c=x2∗y2

~ 52 ~
Finally, x X y becomes:
xy=a∗B(2m)+b∗Bm+cxy=a∗B(2m)+b∗Bm+c
That is why Karatsuba came up with the brilliant idea to calculate b with the following formula:

b=(x1+x2)(y1+y2)−a−c

Example:

Consider the following multiplication: 47 x 78

x = 47

x = 4 * 10 + 7

x1 = 4

x2 = 7

y = 78

y = 7 * 10 + 8

y1 = 7

y2 = 8

a = x1 * y1 = 4 * 7 = 28

c = x2 * y2 = 7 * 8 = 56

b = (x1 + x2)(y1 + y2) - a - c = 11 * 15 - 28 - 56

~ 53 ~
11 * 15 can in turn be multiplied using Karatsuba Algorithm

Pseudocode

procedure karatsuba(num1, num2)

if (num1 < 10) or (num2 < 10)

return num1*num2

*calculates the size of the numbers*

m = max(size_base10(num1), size_base10(num2))

m2 = m/2

*split the digit sequences about the middle*

high1, low1 = split_at(num1, m2)

high2, low2 = split_at(num2, m2)

*3 calls made to numbers approximately half the size*

z0 = karatsuba(low1, low2)

z1 = karatsuba((low1 + high1), (low2 + high2))

z2 = karatsuba(high1, high2)

return (z2 * 10 ^ (2 * m2)) + ((z1 - z2 - z0) * 10 ^ (m2)) + (z0)

~ 54 ~
Learning Outcome 1.7 Use Dynamic programming
algorithms type
Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by
breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the
overall problem depends upon the optimal solution to its subproblems.

Let’s take the example of the Fibonacci numbers. As we all know, Fibonacci numbers are a
series of numbers in which each number is the sum of the two preceding numbers. The first few
Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8, and they continue on from there.

If we are asked to calculate the nth Fibonacci number, we can do that with the following
equation,

Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

As we can clearly see here, to solve the overall problem (i.e. Fib(n)), we broke it down into two
smaller subproblems (which are Fib(n-1) and Fib(n-2)). This shows that we can use DP to solve
this problem.

Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic
Programming is mainly used when solutions of the same subproblems are needed again and
again i.e Dynamic Programming differs from Divide and Conquer, where subproblems generally
need not overlap.

1.7.1 Characteristics of Dynamic Programming

Before moving on to understand different methods of solving a DP problem, let’s first take a
look at what are the characteristics of a problem that tells us that we can apply DP to solve it.

a. Overlapping Subproblems

Subproblems are smaller versions of the original problem. Any problem has overlapping sub-
problems if finding its solution involves solving the same subproblem multiple times. Take the
example of the Fibonacci numbers; to find the fib(4), we need to break it down into the following
sub-problems:

~ 55 ~
 Recursion tree for calculating Fibonacci numbers

We can clearly see the overlapping subproblem pattern here, as fib(2) has been evaluated twice
and fib(1) has been evaluated three times.

b. Optimal Substructure Property

Any problem has optimal substructure property if its overall optimal solution can be constructed
from the optimal solutions of its subproblems. For Fibonacci numbers, as we know,

Fib(n) = Fib(n-1) + Fib(n-2)

This clearly shows that a problem of size ‘n’ has been reduced to subproblems of size ‘n-1’ and
‘n-2’. Therefore, Fibonacci numbers have optimal substructure property.

1.7.2 Dynamic Programming Methods

DP offers two methods to solve a problem.

a. Top-down with Memoization

In this approach, we try to solve the bigger problem by recursively finding the solution to smaller
sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up

~ 56 ~
solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This
technique of storing the results of already solved subproblems is called Memoization.

Example: Write the code for the factorial problem in the top-down fashion

// Memoized version to find factorial x.

// To speed up we store the values

// of calculated states

// initialized to -1

int dp[MAXN]

// return fact x!

int solve(int x)

if (x==0)

return 1;

if (dp[x]!=-1)

return dp[x];

return (dp[x] = x * solve(x-1));

b. Bottom-up with Tabulation

Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we
solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is
typically done by filling up an n-dimensional table. Based on the results in the table, the solution
to the top/original problem is then computed.

~ 57 ~
Tabulation is the opposite of Memoization, as in Memoization we solve the problem and
maintain a map of already solved sub-problems. In other words, in memoization, we do it top-
down in the sense that we solve the top problem first (which typically recurses down to solve the
sub-problems).

Example: Find the factorial of x in tabulated version

// Tabulated version to find factorial x.

int dp[MAXN];

// base case

int dp[0] = 1;

for (int i = 1; i< =n; i++)

dp[i] = dp[i-1] * i;

Comparison between memorization and Tabulation

~ 58 ~
 1.7.3 Solving a dynamic programming problem
To solve any dynamic programming problem, we can use the FAST method.

Here, FAST stands for:

'F' stands for Find the recursive solution: Whenever we find any DP problem, we have to find
the recursive solution.

'A' stands for Analyse the solution: Once we find the recursive solution then we have to analyse
the solution and look for the overlapping problems.

Typically, all the problems that require maximizing or minimize certain quantities or counting
problems that say to count the arrangements under certain conditions or certain probability
problems can be solved by using Dynamic Programming.

All dynamic programming problems satisfy the overlapping subproblems property and most of
the classic dynamic problems also satisfy the optimal substructure property. Once, we observe
these properties in a given problem, be sure that it can be solved using DP.

DP problems are all about state and their transition. This is the most basic step which must be
done very carefully because the state transition depends on the choice of state definition you
make. So, let’s see what do we mean by the term “state”.

State A state can be defined as the set of parameters that can uniquely identify a certain
position or standing in the given problem. This set of parameters should be as small as possible
to reduce state space.
'S' stands for Save the results for future use: Once we find the overlapping problems, we store
the solutions of these sub-problems. To store the solutions, we use the n-dimensional array for
caching purpose.

The above three steps are used for the top-down approach if we use 'F', 'A' and 'S', which means
that we are achieving the Top-down approach. Since it is not purely because we are using the
recursive technique.

~ 59 ~
'T' stands for Tweak the solution to make it more powerful by eliminating recursion overhead
which is known as a Bottom-up approach. Here we remove the recursion technique and use the
iterative approach to achieve the same results, so it's a pure approach. Recursion is always an
overhead as there are chances of getting a stack overflow error, so we should use the bottom-up
approach to avoid this problem.

Example : Write an efficient program to find the nth Fibonacci number

As we know that Fibonacci series looks like:

0, 1, 1, 2, 3, 5, 8, 13, 21,...

First, we find the recursive solution,

The below is the code of the above recursive solution:

Fib(n)

if(n<2)

return n;

return fib(n-1) + fib(n-2);

The above recursive solution is also the solution for the above problem . So, dynamic
programming is used to reduce the time complexity from the exponential time to the linear time.

Second step is to Analyse the solution

Suppose we want to calculate the fib(4).

~ 60 ~
Fib(4)= fib(3) + fib(2)

Fib(3) = fib(2) + fib(1)

Fib(2) = fib(1) + fib(0)

As we can observe in the above figure that fib(2) is calculated two times while fib(1) is
calculated three times. So, here overlapping problem occurs. In this step, we have analysed the
solution.

Third step is to save the result.

The process of saving the result is known as memoization. In this step, we will follow the same
approach, i.e., recursive approach but with a small different that we have used the cache to store
the solutions so that it can be re-used whenever required.

Below is the code of memoization.

Fib(n)

int cache = new int[n+1];

if(n<2)

return n;

if(cache[n]!= 0)

return cache[n];

return cache[n] = fib(n-1) + fib(n-2);

In the above code, we have used a cache array of size n+1. If cache[n] is not equal to zero then
we return the result from the cache else we will calculate the value of cache and then return the
cache. The technique that we have used here is top-down approach as it follows the recursive
approach. Here, we always look for the cache so cache will be populated on the demand basis.

~ 61 ~
Suppose we want to calculate the fib(4), first we look into cache, and if the value is not in the
cache then the value is calculated and stored in the cache.

Visual representation of the above code is:

Fourth step is to Tweak the solution

In this step, we will remove the recursion completely and make it an iterative approach. So, this
technique is known as a bottom-up approach.

Fib(n)

int cache[] = new int[n+1];

// base cases

cache[0] = 0;

cache[1] = 1;

for(int i=2; i<=n; i++)

~ 62 ~
 {

cache[i] = cache[i-1] + cache[i-2];

return cache[n];

In the above code, we have followed the bottom-up approach. We have declared a cache array of
size n+1. The base cases are cache[0] and cache[1] with their values 0 and 1 respectively. In the
above code, we have removed the recursion completely. We have used an iterative approach. We
have defined a for loop in which we populate the cache with the values from the index i=2 to n,
and from the cache, we will return the result. Suppose we want to calculate f(4), first we will
calculate f(2), then we will calculate f(3) and finally, we we calculate the value of f(4). Here we
are going from down to up so this approach is known as a bottom-up approach.

We can visualize this approach diagrammatically:

As we can observe in the above figure that we are populating the cache from bottom to up so it is
known as bottom-up approach. This approach is much more efficient than the previous one as it

~ 63 ~
is not using recursion but both the approaches have the same time and space complexity, i.e.,
O(n).

In this case, we have used the FAST method to obtain the optimal solution. The above is the
optimal solution that we have got so far but this is not the purely an optimal solution.

Efficient solution:

fib(n)

int first=0, second=1, sum=0;

if(n<2)

return 0;

for(int i =2; i<=n; i++)

sum = first + second;

first = second;

second = sum;

return sum;

The above solution is the efficient solution as we do not use the cache.

Learning Outcome 1.8 Use Greedy Algorithms Type

~ 64 ~
It simply means to pick up a choice/solution that seems the best at the moment (being
greedy). This technique is best suited when we want an immediate situation. It helps to solve
optimization problems i.e. which gives either minimum results or maximum results.

A solution satisfying the condition in the problem is a feasible solution. The solution having
minimum cost out of all possible feasible solutions is the optimal solution i.e. it is the best
solution.

The goal of the greedy algorithm is to find the optimal solution. There can be only 1 optimal
solution.

1.8.1 Description of greedy algorithm

a. Greedy introduction
A. History of Greedy Algorithm

The greedy algorithm was first coined by the Dutch computer scientist and mathematician
Edsger W. Dijkstra when he wanted to calculate the minimum spanning tree. The major purpose
of many greedy algorithms was to solve graph-based problems.

The greedy algorithms first started coming into the picture in the 1950s. The then scientists, Prim
and Kruskal also achieved the optimization techniques for minimizing the costs of graphs during
that decade.

A few years later, in the 1970s, many American researchers proposed a recursive strategy for
solving greedy problems. In 2005, the NIST records registered the greedy paradigm as a separate
optimization strategy.

Since then, the greedy algorithm has been extensively in use in multiple fields including the web
protocols such as the open-shortest-path-first (OSPF) and many other network packet switching
protocols.

B. Greedy Strategies and Decisions

Logic in its easiest form was boiled down to “greedy” or “not greedy”. These statements were
defined by the approach taken to advance in each algorithm stage.

~ 65 ~
For example, Djikstra’s algorithm utilized a stepwise greedy strategy identifying hosts on the
Internet by calculating a cost function. The value returned by the cost function determined
whether the next path is “greedy” or “non-greedy”.

In short, an algorithm ceases to be greedy if at any stage it takes a step that is not locally greedy.
The Greedy problems halt with no further scope of greed.

C. Properties required for the Greedy Algorithm

There are many techniques to solve a problem. Out of these many techniques, we have
optimization techniques for a particular set of problems. Out of optimization techniques as well,
there are multiple choices.

So, how do we know that when to use and when not to use the greedy method as an optimization
algorithm.

For this purpose, we will check the properties of the algorithm. If the following two properties
hold, we will use the greedy approach or other approaches.

1. Greedy choice property

To reach the final optimal solution or the globally optimal solution, we find locally optimal
solutions(the best at that moment) for each sub-task.

2. Optimal sub-programs

A solution to the subproblem of an optimal solution is also always optimal.

D. Characteristic of a Greedy Approach

1. In the greedy method, we divide the main problem into sub-problems and solve each of them
recursively.

2. The greedy method maximizes the resources in a given time constraint.

3. There is a cost and value attribution attached to these resources.

~ 66 ~
 E. Importance of Greedy algorithm

Here are the reasons for using the greedy approach:

 The greedy approach has a few tradeoffs, which may make it suitable for optimization.
 One prominent reason is to achieve the most feasible solution immediately. In the activity
selection problem (Explained below), if more activities can be done before finishing the
current activity, these activities can be performed within the same time.
 Another reason is to divide a problem recursively based on a condition, with no need to
combine all the solutions.
 In the activity selection problem, the “recursive division” step is achieved by scanning a
list of items only once and considering certain activities.

F. Advantages of Greedy Algorithm

1. It is a highly optimized and one of the most straightforward algorithms.

2. This algorithm takes lesser time as compared to others because the best solution is
immediately reachable.

3. In the greedy method, multiple activities can execute in a given time frame.

4. We don’t need to combine the solutions of sub-problems, as it automatically reaches the

optimal solution.

5. The algorithm is easy to implement

G. Limitations of Greedy Algorithm

1. The greedy method works by finding the best possible outcome at every step of the algorithm.
This sometimes leads to inaccurate results.

For example, suppose we wish to find the longest path in the following graph:

~ 67 ~
If we follow the greedy approach, we will make the best possible choice at every node. In that
case, the path will come out to be: 12→16→6→35 which comes out to be 69.

[Link] problematic part for a greedy algorithm is analyzing its accuracy. Even with the proper
solution, it is difficult to demonstrate why it is accurate.

3. Optimization problems (Dijkstra’s Algorithm) with negative graph edges cannot be solved
using a greedy algorithm.

b. Steps to create Greedy Algorithm

A. Feasible

The greedy algorithm proceeds by making feasible choices at each step of the whole process.
Feasible choices are those which satisfy all the algorithmic constraints.

B. Local optimal choice

Choose what is best at the given time i.e. make locally optimal choices while preceding through
the algorithm.

C. Unalterable

~ 68 ~
We cannot alter any sub-solution at any subsequent point of the algorithm while execution.

Example: A real-world problem and formulate a greedy solution for it.

Problem: Alex is a very busy person. He has set aside time T to accomplish some interesting
tasks. He wants to do as many tasks as possible in this allotted time T. For that, he has created an
array A of timestamps to complete a list of items on his itinerary.

Now, here we need to figure out how many things Alex can complete in the T time he has.

Approach to Build a Solution: This given problem is a straightforward greedy problem. In each
iteration, we will have to pick the items from array A that will take the least amount of time to
accomplish a task while keeping two variables in mind: current_Time and number_Of_Things.
To generate a solution, we will have to carry out the following steps.

 Sort the array A in ascending order.

 Select one timestamp at a time.

 After picking up the timestamp, add the timestamp value to current_Time.

 Increase number_Of_Things by one.

 Repeat steps 2 to 4 until the current_Time value reaches T.

c. Components of greedy algorithm

Greedy algorithms have the following five components:

 A candidate set of data that needs a solution

 A selection function that chooses the best contributor to the final solution
 A feasibility function that aids the selection function by determining if a candidate can
be a contributor to the solution
 An objective function that assigns a value to a partial solution
 A solution function that indicates that the optimum solution has been discovered

~ 69 ~
1.8.2 Use of greedy approach for solving the activity selection problem

a. Activity Selection Problem

The Activity Selection Problem is an optimization problem which deals with the selection of
non-conflicting activities that needs to be executed by a single person or machine in a given time
frame.

Each activity is marked by a start and finish time. Greedy technique is used for finding the
solution since this is an optimization problem.

Let's consider that you have n activities with their start and finish times, the objective is to find
solution set having maximum number of non-conflicting activities that can be executed in a
single time frame, assuming that only one person or machine is available for execution.

Some points to note here:

 It might not be possible to complete all the activities, since their timings can collapse.

 Two activities, say i and j, are said to be non-conflicting if si >= fj or sj >=

fi where si and sj denote the starting time of activities i and j respectively,
and fi and fj refer to the finishing time of the activities i and j respectively.

 Greedy approach can be used to find the solution since we want to maximize the count
of activities that can be executed. This approach will greedily choose an activity with
earliest finish time at every step, thus yielding an optimal solution.

Input Data for the Algorithm:

 act[] array containing all the activities.

 s[] array containing the starting time of all the activities.

 f[] array containing the finishing time of all the activities.

Ouput Data from the Algorithm:

~ 70 ~
  sol[] array refering to the solution set containing the maximum number of non-conflicting
activities.

b. Steps for Activity Selection Problem

Following are the steps we will be following to solve the activity selection problem,

Step 1: Sort the given activities in ascending order according to their finishing time.

Step 2: Select the first activity from sorted array act[] and add it to sol[] array.

Step 3: Repeat steps 4 and 5 for the remaining activities in act[].

Step 4: If the start time of the currently selected activity is greater than or equal to the finish time
of previously selected activity, then add it to the sol[] array.

Step 5: Select the next activity in act[] array.

Step 6: Print the sol[] array.

Activity Selection Problem Example

In the table below, we have 6 activities with corresponding start and end time, the objective is to
compute an execution schedule having maximum number of non-conflicting activities:

Start Time (s) Finish Time (f) Activity Name

5 9 a1

1 2 a2

3 4 a3

~ 71 ~
0 6 a4

5 7 a5

8 9 a6

A possible solution would be:

Step 1: Sort the given activities in ascending order according to their finishing time.

The table after we have sorted it:

Start Time (s) Finish Time (f) Activity Name

1 2 a2

3 4 a3

0 6 a4

5 7 a5

~ 72 ~
5 9 a1

8 9 a6

Step 2: Select the first activity from sorted array act[] and add it to the sol[] array, thus sol =
{a2}.

Step 3: Repeat the steps 4 and 5 for the remaining activities in act[].

Step 4: If the start time of the currently selected activity is greater than or equal to the finish time
of the previously selected activity, then add it to sol[].

Step 5: Select the next activity in act[]

For the data given in the above table,

A. Select activity a3. Since the start time of a3 is greater than the finish time of a2 (i.e. s(a3)
> f(a2)), we add a3 to the solution set. Thus sol = {a2, a3}.

B. Select a4. Since s(a4) < f(a3), it is not added to the solution set.

C. Select a5. Since s(a5) > f(a3), a5 gets added to solution set. Thus sol = {a2, a3, a5}

D. Select a1. Since s(a1) < f(a5), a1 is not added to the solution set.

E. Select a6. a6 is added to the solution set since s(a6) > f(a5). Thus sol = {a2, a3, a5, a6}.

Step 6: At last, print the array sol[]

Hence, the execution schedule of maximum number of non-conflicting activities will be:

~ 73 ~
(1,2)

(3,4)

(5,7)

(8,9)

1.8.3 Greedy method vs Dynamic Programming

Learning Outcome 1.9 Use Branch and bound algorithms

Type
1.9.1 Branch and bound algorithm introduction

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and
general mathematical optimization problems. In general, given a Hard problem, a branch and
bound algorithm explores the entire search space of possible solutions and provides an optimal
solution.

A branch and bound algorithm consist of stepwise enumeration of possible candidate solutions
by exploring the entire search space. With all the possible solutions, we first build a rooted
decision tree. The root node represents the entire search space:

~ 74 ~
Here, each child node is a partial solution and part of the solution set. Before constructing the
rooted decision tree, we set an upper and lower bound for a given problem based on the optimal
solution. At each level, we need to make a decision about which node to include in the solution
set. At each level, we explore the node with the best bound. In this way, we can find the best and
optimal solution fast.

Now it is crucial to find a good upper and lower bound in such cases. We can find an upper
bound by using any local optimization method or by picking any point in the search space. On
the other hand, we can obtain a lower bound from convex relaxation or duality.

In general, we want to partition the solution set into smaller subsets of solution. Then we
construct a rooted decision tree, and finally, we choose the best possible subset (node) at each
level to find the best possible solution set.

A branch and bound algorithm is a good choice.

If the given problem is a discrete optimization problem, a branch and bound is a good
choice. Discrete optimization is a subsection of optimization where the variables in the problem

~ 75 ~
should belong to the discrete set. Examples of such problems are 0-1 Integer
Programming or Network Flow problem.

Branch and bound work efficiently on the combinatory optimization problems. Given an
objective function for an optimization problem, combinatory optimization is a process to find the
maxima or minima for the objective function. The domain of the objective function should be
discrete and large. Boolean Satisfiability, Integer Linear Programming are examples of the
combinatory optimization problems.

Example: define a job assignment problem. In a standard version of a job assignment problem,
there can be N jobs and N workers. To keep it simple, we’re taking 3 jobs and 3 workers in our
Example

We can assign any of the available jobs to any worker with the condition that if a job is assigned
to a worker, the other workers can’t take that particular job. We should also notice that each job
has some cost associated with it, and it differs from one worker to another.

Here the main aim is to complete all the jobs by assigning one job to each worker in such a way
that the sum of the cost of all the jobs should be minimized.

Running the algorithm on the sample example we’ve created:

~ 76 ~
Initially, we’ve 3 jobs available. The worker A has the option to take any of the 3 available jobs.
So at level 1, we assigned all the available jobs to the worker A and calculated the cost. We can
see that when we assigned jobs 2 to the worker A, it gives the lowest cost in level 1 of the search
space tree. So we assign the job 2 to worker A and continue the algorithm. “Yes” indicates
that this is currently optimal cost.

After assigning the job 2 to worker A, we still have two open jobs. Let’s consider worker B now.
We’re trying to assign either job 1 or 3 to worker B to obtain optimal cost.

Either we can assign the job 1 or 3 to worker B. Again we check the cost and assign job 1 to
worker B as it is the lowest in level 2.

Finally, we assign the job 3 to worker C, and the optimal cost is 12.

Learning Outcome 1.10 Use Brute force algorithms type

1.10.1. Introduction to brute force algorithm

~ 77 ~
a. Definition:
This is the most basic and simplest type of algorithm. A Brute Force Algorithm is the
straightforward approach to a problem i.e., the first approach that comes to our mind on seeing
the problem. More technically it is just like iterating every possibility available to solve that
problem.
A brute force algorithm simply tries all possibilities until a satisfactory solution is found.

For Example:
If there is a lock of 4-digit PIN. The digits to be chosen from 0-9 then the brute force will be
trying all possible combinations one by one like 0001, 0002, 0003, 0004, and so on until we
get the right PIN. In the worst case, it will take 10,000 tries to find the right combination.

Brute force algorithm can be:

Optimizing: Find the best solution. This may require finding all solutions, or if a value for the
best solution is known, it may stop when any best solution is found
Example: Finding the best path for a travelling salesman.

Satisficing: Stop as soon as a solution is found that is good enough

Example: Finding a travelling salesman path that is within 10% of optimal

b. Improving brute force algorithms

Often, brute force algorithms require exponential time. Various heuristics and optimizations
can be used
Heuristic: A “rule of thumb” that helps you decide which possibilities to look at first
Optimization: In this case, a way to eliminate certain possibilities without fully exploring
them
c. Advantages and disadvantages of brute force algorithm
Advantages of the brute-force algorithm
The advantages of the brute-force algorithms are:

~ 78 ~
  If all the possible solutions are listed down, then you can be guaranteed that the brute-
force approach will find the correct solution.
 It is applicable to problems that exist in a very wide range of domains.
 It is useful for solving small and simple problems.
 It is very simple, does not require any domain knowledge, and can be used as
a comparison benchmark.

Disadvantages of the brute-force algorithm

Here are the disadvantages of brute-force algorithms:

 The brute-force method is very inefficient. For real-time problems, algorithm analysis
quite frequently goes above the O(N!) order of growth.
 Finding the right solution by this method consumes a lot of time. These algorithms run
rather slowly.

 Instead of using a good algorithm design, these algorithms just rely on compromising the
power of the computer.
 These algorithms are neither constructive nor creative in comparison to algorithms that
are constructed through the use of some other design paradigms.

1.10.2 Implementing the brute force search

a. Brute-Force Search
Brute force search is the most common search algorithm as it does not require any domain
knowledge; all that is required is a state description, legal operators, the initial state and the
description of a goal state. It does not improve the performance and completely relies on the
computing power to try out possible combinations.

The brute force algorithm searches all the positions in the text between 0 and n-m, whether the
occurrence of the pattern starts there or not. After each attempt, it shifts the pattern to the right by
exactly 1 position. The time complexity of this algorithm is O(m*n). If we are searching for n
characters in a string of m characters, then it will take n*m tries.

~ 79 ~
Example: Suppose a salesman needs to travel 10 different cities in a country, and he wants to
determine the shortest possible routes out of all the possible combinations. Here brute force
algorithm simply calculates the distance between all the cities and selects the shortest one.
b. Basic algorithm
In order candidate for P after the current one c.

1. valid (P, c): check whether candidate c is a solution for P.

2. output (P, c): use the solution c of P as appropriate to the application.

The next procedure must also tell when there are no more candidates for the instance P, after the
current one c. A convenient way to do that is to return a "null candidate", some conventional data
value Λ that is distinct from any real candidate. Likewise the first procedure should return Λ if
there are no candidates at all for the instance P. The brute-force method is then expressed by the
algorithm

c ← first(P)
while c ≠ Λ do
if valid(P,c) then
output(P, c)
c ← next(P, c)
end while

For example, when looking for the divisors of an integer n, the instance data P is the number n.
The call first(n) should return the integer 1 if n ≥ 1, or Λ otherwise; the call next(n,c) should
return c + 1 if c < n, and Λ otherwise; and valid(n,c) should return true if and only if c is a
divisor of n. (In fact, if we choose Λ to be n + 1, the tests n ≥ 1 and c < n are unnecessary). The
brute-force search algorithm above will call output for every candidate that is a solution to the
given instance P. The algorithm is easily modified to stop after finding the first solution, or a
specified number of solutions; or after testing a specified number of candidates, or after spending
a given amount of CPU time.

1.10.3 Combinatorial explosion

~ 80 ~
Combinatorial explosions occur in some numeric problems when the complexity rapidly
increases, caused by the increasing the number of possible combinations of inputs. As an
example, if you have n constraints or factors for a decision, each with 10 possible options, then
you will have all together 10 to the power n combinations of results. The number of
combinations grows exponentially as n increases.

This explosion in complexity can make some mathematical problems intractable to brute force
solutions. The combinatorial explosion problem prevented computers from competing with
human world champions until suitable heuristic solutions were invented.
The following graph clearly visualizes the problem:

The Problem: Combinatorial Explosion

The naive way of solving combinatorial problems can be paraphrased as `generate and test': In a
first step one enumerates all combinations from which one selects all solutions in the second
step. In most cases however, `generate and test' is simply not feasible. This is obvious if the set
of combinations is infinite. But even if it is finite then it is usually very large, i.e. exponentially
large in size of the problem description. In this case, the generation step runs into a combinatorial
explosion (from which it usually returns only several billions of years later).

Constraint Satisfaction Problems

A typical example is a constraint satisfaction problem: it consists of variables V1,...,Vn which

respectively take values from finite domains D1,...,Dn, where Di is a finite set of values such as
an interval of integers. The problem is to find assignments of values to the variables such that a
constraint C(V1,...,Vn) is satisfied.

~ 81 ~
Let's consider the following example of 15 variables V1,...,V15, all taking values in the
domain {1,...,15} and for which we want to find all solutions that satisfy the constraints:

V1 < V2
V2 < V3
...
V14 < V15

Clearly, there is only 1 solution to this problem, namely:

V1=1, V2=2, ... , V15=15

Let's see how “Generate and Test” solving technique performs on this example.

Generate and Test

We can enumerate the possible assignments by picking a non-assigned variable, non-

deterministically choosing a value in its domain as its assignment, and repeating until all
variables are assigned values. This process spawns a tree: each inner node of this tree
corresponds to a non-deterministic choice of value to assign to a variable, and the leaves are all
possible complete assignments.

The leaves which satisfy the problem's constraint are said to be solutions. Those which violate
this constraint are said to be failures. We will often display a search tree graphically as shown
below, where blue circles represent choice points, red squares failures, and green diamonds
solutions. For convenience, a subtree whose leaves are all failures (resp. solutions) is usually
abbreviated by a red (resp. green) triangle.

~ 82 ~
For our problem, there are 15 variables, each taking one of 15 possible values: this means there
are 15^15 = [Link].859.375 possible assignments. Let's be optimistic and suppose we
have a fast computer able to check 10^9 assignments per second to decide whether each is a
solution or a failure: checking all possibilities would still take approximately 14 years.

For a concrete example, let's consider only 6 variables V1,...,V6 taking values in {1,...,6} and
such that they must satisfy V1 < ... < Vn. The generate and test method produces the following
search tree with 93311 nodes:

~ 83 ~
1.10.4 Speeding up brute-force searches
One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of
candidate solutions, by using heuristics specific to the problem class. For example, in the eight
queens problem the challenge is to place eight queens on a standard chessboard so that no queen
attacks any other. Since each queen can be placed in any of the 64 squares, in principle there are
648 = 281,474,976,710,656 possibilities to consider. However, because the queens are all alike,
and that no two queens can be placed on the same square, the candidates are all possible ways of
choosing of a set of 8 squares from the set all 64 squares; which means 64 choose 8 = 64!/(56!
*8!) = 4,426,165,368 candidate solutions – about 1/60,000 of the previous estimate. Further, no
arrangement with two queens on the same row or the same column can be a solution. Therefore,
we can further restrict the set of candidates to those arrangements.

As this example shows, a little bit of analysis will often lead to dramatic reductions in the
number of candidate solutions, and may turn an intractable problem into a trivial one.

In some cases, the analysis may reduce the candidates to the set of all valid solutions; that is, it
may yield an algorithm that directly enumerates all the desired solutions (or finds one solution,
as appropriate), without wasting time with tests and the generation of invalid candidates. For
example, for the problem "find all integers between 1 and 1,000,000 that are evenly divisible by
417" a naive brute-force solution would generate all integers in the range, testing each of them
for divisibility. However, that problem can be solved much more efficiently by starting with 417
and repeatedly adding 417 until the number exceeds 1,000,000 – which takes only 2398 (=
1,000,000 ÷ 417) steps, and no tests.

1.10.5 Reordering the search space

In applications that require only one solution, rather than all solutions, the expected running time
of a brute force search will often depend on the order in which the candidates are tested. As a
general rule, one should test the most promising candidates first. For example, when searching
for a proper divisor of a random number n, it is better to enumerate the candidate divisors in
increasing order, from 2 to n − 1, than the other way around – because the probability that n is
divisible by c is 1/c. Moreover, the probability of a candidate being valid is often affected by the
previous failed trials. For example, consider the problem of finding a 1 bit in a given 1000-bit
string P. In this case, the candidate solutions are the indices 1 to 1000, and a candidate c is valid
if P[c] = 1. Now, suppose that the first bit of P is equally likely to be 0 or 1, but each bit

~ 84 ~
thereafter is equal to the previous one with 90% probability. If the candidates are enumerated in
increasing order, 1 to 1000, the number t of candidates examined before success will be about 6,
on the average. On the other hand, if the candidates are enumerated in the order
1,11,21,31...991,2,12,22,32 etc., the expected value of t will be only a little more than 2. More
generally, the search space should be enumerated in such a way that the next candidate is most
likely to be valid, given that the previous trials were not. So if the valid solutions are likely to be
"clustered" in some sense, then each new candidate should be as far as possible from the
previous ones, in that same sense. The converse holds, of course, if the solutions are likely to be
spread out more uniformly than expected by chance.

1.10.6 Alternatives to brute-force search

There are many other search methods, or metaheuristics, which are designed to take advantage of
various kinds of partial knowledge one may have about the solution. Heuristics can also be used
to make an early cutoff of parts of the search. One example of this is the minimax principle for
searching game trees, that eliminates many subtrees at an early stage in the search. In certain
fields, such as language parsing, techniques such as chart parsing can exploit constraints in the
problem to reduce an exponential complexity problem into a polynomial complexity problem. In
many cases, such as in Constraint Satisfaction Problems, one can dramatically reduce the search
space by means of Constraint propagation, that is efficiently implemented in Constraint
programming languages. The search space for problems can also be reduced by replacing the full
problem with a simplified version. For example, in computer chess, rather than computing the
full minimax tree of all possible moves for the remainder of the game, a more limited tree of
minimax possibilities is computed, with the tree being pruned at a certain number of moves, and
e remainder of the tree being approximated by a static evaluation function.

Learning Outcome 1.11 Use Randomized Algorithms Type

1.11.1 introduction to randomized algorithms
a. Definition

An algorithm that uses random numbers to decide what to do next anywhere in its logic is called
a Randomized Algorithm. For example, in Randomized Quick Sort, we use a random number to
pick the next pivot (or we randomly shuffle the array).

~ 85 ~
Examples:

 In Quicksort, using a random number to choose a pivot

 Trying to factor a large prime by choosing random numbers as possible divisors

b. Types of randomized algorithm

There are two main types of randomized algorithms: Las Vegas algorithms and Monte-Carlo
algorithms.

Las Vegas algorithms, the algorithm may use the randomness to speed up the computation, but
the algorithm must always return the correct answer to the input.

Monte-Carlo algorithms do not have the former restriction, that is, they are allowed to
give wrong return values. However, returning a wrong return value must have a small
probability, otherwise that Monte-Carlo algorithm would not be of any use.

1.11.2 Computational complexity

Computational complexity, a measure of the amount of computing resources (time and space)
that a particular algorithm consumes when it runs. Computer scientists use mathematical
measures of complexity that allow them to predict, before writing the code, how fast
an algorithm will run and how much memory it will require. Such predictions are important
guides for programmers implementing and selecting algorithms for real-world applications.

1.11.3 Derandomization
Derandomization is the process of taking a randomized algorithm and turning it into a
deterministic algorithm. This is useful both for practical reasons (deterministic algorithms are
more predictable, which makes them easier to debug and gives hard guarantees on running time)
and theoretical reasons (if we can derandomize any randomized algorithm we could show
results , which would reduce the number of complexity classes that complexity theorists
otherwise have to deal with).

Learning Outcome 1.12: Write algorithm pseudocode

An algorithm is made mainly of the following parts:
The variable declaration line

~ 86 ~
The beginning of an algorithm
The instructions part
The end
1.12.1 Description of algorithm pseudocode
 It can be understood as one of the methods that helps in the representation of an
algorithm.
 It is a simpler version of coding in a programming language.
 It is written in plain English, and uses short phrases to write the functionalities that
specific line of code would do.
 There is no specific syntax which is actually present in other programming languages.
 This means it can't be executed on a computer.
 There are many formats that could be used to write pseudo-codes.
 Most of these formats take the structure from languages such as C, LISP, FORTRAN,
and so on.
 Pseudocode is not actually a programming language.
 Control structures such as 'while', 'if-then-else', 'repeat-until', and so on can be used.

1.12.2 Difference Between Algorithm and Pseudocode

An algorithm is defined as a well-defined sequence of steps that provides a solution for a given
problem, whereas a pseudocode is one of the methods that can be used to represent an
algorithm.

While algorithms are generally written in a natural language or plain English language,
pseudocode is written in a format that is similar to the structure of a high-level programming
language. Program on the other hand allows us to write a code in a particular programming
language.

Algorithm Flowchart

Algorithm is step by step procedure Flowchart is a diagram created by different shapes

1 to solve the problem. to show the flow of data.

~ 87 ~
 2. Algorithm is complex to understand. Flowchart is easy to understand.

3. In algorithm plain text are used. In flowchart, symbols/shapes are used.

4. Algorithm is easy to debug. Flowchart it is hard to debug.

5. Algorithm is difficult to construct. Flowchart is simple to construct.

6. Algorithm does not follow any rules. Flowchart follows rules to be constructed.

Algorithm is the pseudo code for the

7. program.

So, as depicted above you can clearly see how the algorithm is used to generate the pseudocode
which is further expanded by following a particular syntax of a programming language to create
the code of the program.

Example: An Algorithm and Pseudocode that add two numbers entered by the User

Algorithm

Step 1: Start

Step 2: Declare variables num1, num2 and sum.

Step 3: Read values num1 and num2.

Step 4: Add num1 and num2 and assign the result to sum.

sum←num1+num2

Step 5: Display sum

Step 6: Stop

Pseudocode

Var s1, s2, sum As Integer

~ 88 ~
BEGIN

OUTPUT ("Input number1:")

INPUT s1

OUTPUT ("Input number2:")

INPUT s2

sum=s1+s2

OUTPUT sum

END

1.12.3 Use of pseudocode syntax

a. Operators in algorithm

a) Arithmetic operators

+ Addition

- Subtraction

* Multiplication

/ Division

↑or ̂ Power

b) Comparison operators

> Greater than

< Less than

>= Greater than or equal to

<= Less than or equal to

= Equal to

! = Not equal to

~ 89 ~
c) Logic operators

AND operator

OR operator

d) Assignment operator

To put a value in a variable we use an assignment operator which has the following symbol: ←

b. Read and write functions

a) Read function (Inputs)

A read function is a function which is used for inputs. It helps to receive the value entered by a
user and assign it to a variable.

Syntax of read function:

Read ()

Example:

Write an algorithm which receives a number entered by a user.

Answer:

Var A as Integer

Start

read(A)

End

b) Write function

Write function is used for Outputs; it displays the content of a variable or displays messages.

Syntax of write function:

write ()

Example:

~ 90 ~
Write an algorithm which displays a value stored in a variable.

Answer:

Var B as Integer

Start

B←5

Write (“The content of the variable is: ”)

write(B)

End

c. Tests

There are situations in which a set of instructions are executed in one situation and entirely
another set of instructions to be executed in a different situation.

In this kind of situations, a decision control instruction (test) is used. We can define a test as a
structure which controls the flow of instructions of a program during its execution. We can also
define it as a structure which helps us to evaluate a condition.

a) Structure of a test

The structure of a test is made of two main parts: the part which evaluate a condition, and a part
of one instruction or a block of instructions.

b) Conditions (if, if…else, switch)

If statement

Syntax:

If (condition) then

Instructions

End if

~ 91 ~
The if statement is used to make a decision. The block of instructions following the if executes if
the decision is true, and the block does not execute otherwise.

Example 1:

start

If the light is green, then

Go

End if

End

Example 2:

start

If the light is red, then

Stop

End if

End

Each of these statements is conditional. If the condition is true, the instruction following the
condition go in the first example and stop in the second example are executed. In case the
condition evaluates to false nothing is done.

Example 3:

Write an algorithm which receives a number and informs the user when it is positive.

Answer:

Var A as integer

Start

Write (“enter a number”)

~ 92 ~
Read(A)

If (A>0) then

Write (“the number is positive”)

End if

End

To this question when the condition evaluates true it displays the instruction: the number is
positive but when it evaluates for false it displays nothing.

If…else statement

Syntax

If (condition) then

Instructions

Else

Instructions

End if

End

The if…else statement is used to make a decision and gives the alternative when the condition
evaluates to false. The block of instructions following the if executes if the decision is true, and
the block after else when the condition evaluates to false.

Example 1:

start

If the light is green, then

Go

else

~ 93 ~
Stop

End if

End

If the condition is true, the instruction following the condition go is executed, when it evaluates
to false the instruction stop which follows else is executes.

Example 2:

Write an algorithm which receives a number and informs the user whether it is positive or
negative.

Answer:

Var A as integer

Start

Write (“enter a number”)

Read(A)

If (A>0) then

Write (“the number is positive”)

else

Write (“the number is negative”)

End if

End

To this question when the condition evaluates true it displays the message the number is positive
when it evaluates to false it displays the message the number is negative.

Nested Ifs

If statement may be used inside another if statement, in such case we call it a nested if.

~ 94 ~
Example:

Write an algorithm which receives student note and it displays the grade as follows:

Note form 16 and above: Grade A

Note 14-16 : Grade B

Note 12-14 : Grade C

Note below 12 : Grade D

Answer:

Var Note as integer

Start

Write (“enter the note”)

Read(Note)

If (Note>=16) then

Write (“Grade A”)

Else if(Note>=14) then

Write (“Grade B”)

Else if (Note>=12) then

Write (“Grade C”)

Else

Write (“Grade D”)

End if

end

Multiple choice using ‘switch’

~ 95 ~
A multiple choice using switch helps to solve the problem caused by nested if statement in case
there are many conditions to be tested. Switch receives a variable then it evaluates it using
several Cases.

Syntax:

Menu explaining to the user how to make a choice

Switch(variable)

Case 1

Instruction

Case 2

Instruction

….

Case n

Instruction

Default

Instruction

End switch

Example:

Write an algorithm which receives note and displays the student’s grade.

16 and above: grade A

14-16: grade B

12-14: grade C

Less than 12: grade D

Answer:

~ 96 ~
Var Note as integer

Start

Write (“Use number to choose the range of your note”)

Write (“enter 1 for note ranging from 16 and above”)

Write (“enter 2 for note ranging from 14 to16”)

Write (“enter 3 for note ranging from 12 to14”)

Write (“enter 4 for note less than 12”)

Write (“enter your choice now using number:”)

Read(Note)

Switch(Note)

Case 1

Write (“You have grade A”)

break

Case 2

Write (“You have grade B”)

break

Case 3

Write (“You have grade C”)

break

Case 4

Write (“You have grade D”)

Default

Write (“Your choice is not listed, try again”)

~ 97 ~
End switch

End

d. Loops

a) What is a loop?

A loop helps to repeat instruction or block of instructions. It assists in the algorithm where you
want to carry out an activity for a certain number of times.

b) Do while loop

The do-While loop execute its statements at least once even if the condition fails for the first
time.

It tests the condition at the end of loop body.

Syntax

Variable=<start value>

Do while <variable><comparison operator><end value>

Instruction or block of instructions

Variable=variable+1

Loop

Example:

Write an algorithm which use do while loop and displays numbers from 1 to 10

Answer:

Var A as integer

Start

A=1

Do while A<=10

~ 98 ~
Write(A)

A=A+1

Loop

End

c) Do… loop Until

Do Until Loop means to do something until the condition becomes TRUE. It is like a logical
function that works based on TRUE or FALSE. This is the opposite of the Do While loop where
Do while runs the loops as long as the condition is TRUE.

Syntax:

<Variable>=<start value>

Do

Instruction or block of instructions

Variable=variable+1

Loop until while <variable><comparison operator><end value>

Example:

Write an algorithm which use do loop until and displays numbers from 1 to 10

Answer:

Var A as integer

Start

A=1

Do

Write(A)

A=A+1

~ 99 ~
Loop until A>10

End

d) For loop

The for loop is an iterative loop, it specifies some elements about the loop in one single line.

Setting a loop counter to an initial value.

End which determine whether its value has reached the number of repetitions desired

The value of the loop counter will be increased each time (iteration), and segment within the
loop will be executed.

Syntax:

for (<initialize counter> to <end of repetitions desired>) do

Instruction or bloc of instructions

end for

Example:

Write an algorithm which ask a user to enter a number and it displays the 10 next numbers.

Var I, A as integer

Start

Write (“enter a number”)

Read(I)

For (A=1 to 10) do

I<-I+1

Write(I)

End for

End

~ 100 ~
e) Loops in Loops

Loops in loops refer to what we call nested loops. These are loops that are such that when one
increment by one the other continues inside the first.

Example:

Var I, J as Integer

start

For I = 1 To 9 do

For J = 1 To I do

Write(J)

End for

End for

End

e. Arrays

a) Use of Arrays

An array is a variable with elements of the same data type. To access the array elements, we use
the array index.

For example, if you need to record notes of 20 students in a given course, you will have to
declare 20 variables as follows:

Var N1, N2, N3, N4, N5, N6, N7, N8, N9, N10, N11, N12, N13, N14, N15, N16, N17, N18,
N19, N20 as integer

Writing these variables and assigning values to them is hard.

We can use one variable called an array to hold all these numbers.

~ 101 ~
b) Declaring an array

Syntax

Var <array name> <size> as <data type>

Example:

Var N (19) as integer

This array will look as follows:

Variable i is used in a loop to move from index 0 of the array to index 19 performing given
instructions on the array

C) How do we assign values to an array?

Let us declare an array which will hold five numbers and assign to it 5 numbers of our choice.

Var N(4) as integer

Start

N (0) ←8

N (1) ← 10

N (2) ← 12

N (3) ← 6

N (4) ← 5

End

To display the content of this array we will need a loop.

Var i as integer

For i=0 to 4

~ 102 ~
Write N(i)

End for

If we put together these parts we will have

Var N (4) as integer

Var i as integer

Start

N (0) ←8

N (1) ←10

N (2) ←12

N (3) ←6

N (4) ←5

For i=0 to 4 do

Write N(i)

End for

End

In case we are told that the user we enter numbers in array we will use another array for input,
and our algorithm will change as follows:

Var N (4) as integer

Var I as integer

Start

For I=0 to 4 do

read N(I)

End for

~ 103 ~
For I=0 to 4 do

Write N(I)

End for

End

d) Arrays dimensions

A dimension is a direction in which you can vary the specification of an array's elements.

One-dimensional array

Two-dimensional array

Three-dimensional array

~ 104 ~
Suppose you want to track sales amounts for every day of the present month. You might declare
a one- dimensional array with 31 elements, one for each day of the month, as the following
example shows.

Dim salesAmounts(30) As Double

Now suppose you want to track the same information not only for every day of a month but also
for every month of the year. You might declare a two-dimensional array with 12 rows (for the
months) and 31 columns (for the days), as the following example shows.

Dim salesAmounts(11, 30) As Double

Now suppose you decide to have your array hold information for more than one year. If you
want to track sales amounts for 5 years, you could declare a three-dimensional array with 5
layers, 12 rows, and 31 columns, as the following example shows.

Dim salesAmounts(4, 11, 30) As Double

Learning Outcome 1.13: Write algorithm flowchart

1.13.1 Description of algorithm flowchart

a. Flowchart definition

A flowchart is simply a graphical representation of steps. It shows steps in sequential order and
is widely used in presenting the flow of algorithms, workflow or processes. Typically,
a flowchart shows the steps as boxes of various kinds, and their order by connecting them with
arrows.
The process of drawing a flowchart for an algorithm is known as “flowcharting”.
Flowchart is drawn according to defined rules. It is called a flowchart since it charts the flow of
the program. If the flow is in correct order, then program execution turns out to be in proper
order.

~ 105 ~
b. Advantages of using Flowcharts
As we discussed flow chart is used for representing algorithm in pictorial form. This pictorial
representation of a solution/system is having many advantages. These advantages are as follows:
1. Communication: A Flowchart can be used as a better way of communication of the logic of a
system and steps involve in the solution, to all concerned particularly to the client of system.
2. Effective analysis: A flowchart of a problem can be used for effective analysis of the
problem.
3. Documentation of Program/System: Program flowcharts are a vital part of a good program
documentation. Program document is used for various purposes like knowing the components in
the program, complexity of the program etc.
4. Efficient Program Maintenance: Once a program is developed and becomes operational it
needs time to time maintenance. With help of flowchart maintenance become easier.
5. Coding of the Program: Any design of solution of a problem is finally converted into
computer program. Writing code referring the flowchart of the solution become easy.

c. Flowchart Symbols
There are 6 basic symbols commonly used in flowcharting of assembly language Programs:
Terminal, Process, input/output, Decision, Connector and Predefined Process. This is not a
complete list of all the possible flowcharting symbols, it is the ones used most often in the
structure of Assembly language programming.

~ 106 ~
d. General Rules for flowcharting
1. All boxes of the flowchart are connected with Arrows. (Not lines)
2. Flowchart symbols have an entry point on the top of the symbol with no other entry points.
The exit point for all flowchart symbols is on the bottom except for the Decision symbol.
3. The Decision symbol has two exit points; these can be on the sides or the bottom and one side.
4. Generally a flowchart will flow from top to bottom. However, an upward flow can be shown
as long as it does not exceed 3 symbols.
5. Connectors are used to connect breaks in the flowchart. Examples are:
• From one page to another page.
• From the bottom of the page to the top of the same page.
• An upward flow of more than 3 symbols
6. Subroutines and Interrupt programs have their own and independent flowcharts.
7. All flow charts start with a Terminal or Predefined Process (for interrupt programs
or subroutines) symbol.
8. All flowcharts end with a terminal or a contentious loop.

~ 107 ~
Flowcharting uses symbols that have been in use for a number of years to represent the type of
operations and/or processes being performed. The standardized format provides a common
method for people to visualize problems together in the same manner. The use of standardized
symbols makes the flow charts easier to interpret, however, standardizing symbols is not as
important as the sequence of activities that make up the process.

1.13.2 Difference Between Algorithm and Flowchart

Algorithm Flowchart

Algorithm is step by step procedure Flowchart is a diagram created by different shapes

1 to solve the problem. to show the flow of data.

2. Algorithm is complex to understand. Flowchart is easy to understand.

3. In algorithm plain text are used. In flowchart, symbols/shapes are used.

4. Algorithm is easy to debug. Flowchart it is hard to debug.

5. Algorithm is difficult to construct. Flowchart is simple to construct.

6. Algorithm does not follow any rules. Flowchart follows rules to be constructed.

Algorithm is the pseudocode for the

7. program.

1.13.3 Examples of flowchart

Example 1: A flowchart to find the area of a circle of radius r.

~ 108 ~
Example 2: Draw a flowchart to find the greater number between two numbers and display the
message accordingly.

Example 3: Draw a flowchart to find the largest value of any three numbers

~ 109 ~
Example 4: A flowchart to display numbers from 1 to 10 using a loop

Exercises

~ 110 ~
1. An algorithm and Flowchart that add two numbers, calculate their average and display the
result.
2. Write algorithm and draw a flowchart to find the result of equation:

3. Write an algorithm and draw a flowchart which receives student’s marks and it displays the
grade as follows:

Marks form 16 and above: Grade A

Marks ranging from 14 to16: Grade B

Marks ranging from 12 to14: Grade C

Marks below 12: Grade D

4. Write an algorithm to initialize the variable language by 10 and print the message C in case
of 1, C# in case of 2, C++ in case of 3 otherwise print “Other programming language”. Use
switch statement.
5. An algorithm and flowchart to find the sum of 5 numbers using for loop

6. Write an algorithm and draw a flowchart for program that display the Multiplication table
for a given number N.

Learning outcome 1.14 Apply Algorithm complexity to

measure its speed in execution
Complexity theory is the study of the amount of time taken by an algorithm to run as a function of
the input size. It’s very useful for software developers to understand so they can write code
efficiently. There are two types of complexities:
 Space complexity: How much memory an algorithm needs to run.
 Time complexity: How much time an algorithm needs to run.
We usually worry more about time complexity than space complexity because we can reuse the
memory an algorithm needs to run, but we can’t reuse the time it takes to run. It’s easier to buy

~ 111 ~
memory than it is to buy time. If you need more memory — you can rent server space from
providers like Amazon, Google, or Microsoft. You could also buy more computers to add more
memory without renting server space.
How Do We Measure Time Complexity?

A new computer will usually be faster than an old computer, and desktops will usually be faster
than smartphones — so how do we really know the absolute time an algorithm takes?

To measure the absolute time, we consider the number of operations the algorithm performs. The
building blocks of any algorithm are if-statements and loops. They answer the questions: (1)
When should we do operations? (2) How many times should we do them? We want to write code
using as few if-statements and loops as possible for maximum efficiency on any machine.
For analyzing algorithms, we consider the input size n — the number of input items. We want to
make a good guess on how the algorithm’s running time relates to the input size n. This is
the order of growth: how the algorithm will scale and behave given the input size n.

1. Input 10 items -> 10 ms

2. Input 100 items -> 100 ms (Good, linear growth)

3. Input 1,000 items -> 10,000 ms (Bad, exponential growth)

In the above example, when we input 10 items, it takes 10 ms to run. When we input 100 items,
it takes 100 ms — which is good since the growth of our input increased proportionally to the
runtime.

However, on the next step, we input 1,000 items, and it takes 10,000 ms. We’re now taking 10
times longer to run relative to the increase in our input size n. Now we have exponential growth
of our runtime instead of linear growth. To better understand the different orders of growth, we’ll
cover the Big-O notation.
 Linear Growth Rate

~ 112 ~
A linear growth rate is a growth rate where the resource needs and the amount of data is
directly proportional to each other. That is the growth rate can be described as a straight line
that is not horizontal.
 Exponential Growth Rate

An exponential growth rate is one where each extra unit of data requires a doubling of
resource.
all exponential functions belong to the same order of growth regardless of the base of
the exponent. Exponential functions grow very quickly, so exponential algorithms are only
useful for small problems.

 Big O notation
Big O notation is one of the most fundamental tools for computer scientists to analyze the cost
of an algorithm. It is a good practice for software engineers to understand in-depth as well.

Exercises

1. Write short notes on Algorithm

2. Write short notes on flowchart diagram
3. Differentiate algorithm and pseudocode
4. Write an algorithm pseudocode to find the average of the marks of 5 subjects inputted
from the keyboard and display the display the following:
• If Average<=100 and >=50 the program should display “PASS!!!!!!!!!!!”
• If Average<50 the program should display “FAIL!!!!!!!!!!!!!”
5. Write an algorithm pseudocode (using switch) which has the following menus

MAIN MENU
-------------------
PRESS 1 TO CHECK NUMBER
PRESS 2 TO DISPLAY THE SQUARE OF A NUMBER

~ 113 ~
 PRESS 3 TO EXIT THE PROGRAM
• If a user presses 1 the program should display where a number inputted from the
keyboard is old or even number.
• If a user presses 2 the program should display the square of a number inputted from the
keyboard.
• If a user presses 3 the program should display “END OF PROGRAM”
• If a user presses any other key, the program should display “TRY AGAIN”
6. Write an Algorithm (using a loop of your choice) to print the numbers from 10 up 30.
7. Write short notes on one types of Algorithm of your choice.
8. Write an Algorithm to initialize an array of 6 integers by the values of your choice then
display the first, second and the third integer (number).
9. Write an algorithm and draw a flowchart for program that display the Multiplication table for
a given number N.
10. Write an algorithm and draw a flowchart to find the sum of 5 numbers using do while loop

LEARNING UNIT 2: APPLY C PROGRAMMING

FUNDAMENTALS
Learning Outcomes: 2.1 Setup the environment of C
programming
2.2 Use of C Syntax (Character Set,
Identifiers, Keywords, Comments, …)
2.3 Describe data Types
2.4 Use Variables
2.5 Use Constants
2.6 Use Operators
2.7 Use Conditions
2.8 Use Loops
2.9 Use Arrays

~ 114 ~
 2.10 Use Functions.
2.11 Manage memory using pointers
2.12 Use structure
2.13 Use file I/O

Learning Outcome 2.1. Setup the environment of C

programming
2.1.1 Introduction to C
a. Introduction`
C language has been designed and developed by Dennis Ritchie at Bell Laboratories in 1972. It
is an offspring of the “Basic combined programming language” called ‘B’ developed in the year
1960 at Cambridge University. This language is associated closely with Unix operating system.
The source code for the Unix operating system is coded in C.

C is a simple and structure oriented programming language. C is also called mother

Language of all programming Language. It is the most widely used computer programming
language, this language is used for develop system software and Operating System. All other
programming languages were derived directly or indirectly from C programming concepts.
Here we discuss complete C Tutorial in simple and easy way. C is a programming language
that serves as a medium for programmer to instruct computer to do a job or making
programs/software.

b. Programming Language Description

A computer program can be defined as a set of step-by-step computer instructions that are
designed to tell a computer what and how to accomplish a task or achieve particular expected
results.
Language: is a set of characters, symbols and rules of their assembling for communication
purposes. Communication is assured between different individuals with the help of language
(spoken, written, sign, symbols).
There are 2 types of languages:

~ 115 ~
  Natural language: spoken by human being or animals
e.g: Swahili, English, French, etc.
 Artificial language: used to simplify communication especially in computer
programming.
There’re similarities between those languages. Each language has its own grammatical rules
which must be obeyed in order to write valid programs just as natural language has its own
grammatical rules for forming sentences.
A computer programming language therefore, can be defined as the process of writing and
maintaining step-by-step instructions which can be interpreted by a computing system to perform
a meaningful task.

Computer programming languages are mainly divided into two main categories: Low-level
programming languages and High-level programming language

Low-level programming languages are sometimes divided into two categories: first generation,
and second generation.

A low-level programming language is a language that provides little or no abstraction from a

computer's microprocessor.

The word "low" does not imply that the language is inferior to high-level programming
languages but rather refers to the small or nonexistent amount of abstraction between the
language and machine language; because of this, low-level languages are sometimes described as
being "close to the hardware."

a) First Generation Language(1GL) called machine language

It is the only language a microprocessor can understand directly.

Currently, programmers almost never write programs directly in machine code, because not only
it requires attention to numerous details which a high-level language would handle
automatically, but also it requires memorizing or looking up numerical codes for every
instruction that is used.

For this reason, second generation programming languages abstract the machine code one level.

~ 116 ~
b) Second Generation Language(2GL) called assembly language
It is considered a second-generation language because while it is not a microprocessor's native
language, an assembly language programmer must still understand the microprocessor's unique
architecture (such as its registers and instructions).

These simple instructions are then compiled directly into machine code.

High-level programming language is a programming language that, in comparison to low-level

programming languages, may be more abstract, easier to use, or more portable across platforms.

The term "high-level language" does not imply that the language is always superior to low-level
programming languages rather "high-level language" refers to the higher level of abstraction
from machine language.

High-level languages make complex programming simpler while low-level languages tend to
produce more efficient code.

A computer program's source code is the collection of files needed to convert from human-
readable form to some kind of computer-executable form. The source code may be converted
into an executable file (object code) by a compiler.

In summary, there are five generation of Programming languages. They are:

1. First Generation Languages:
These are low-level languages like machine language.
2. Second Generation Languages:
These are low-level assembly languages used in kernels and hardware drives, but more
commonly used for video editing and video games.
3. Third Generation Languages:
These are high-level languages like C, C++, Java, Visual Basic and JavaScript.
4. Fourth Generation Languages:
These are languages that consist of statements that are similar to statements in the
human language. These are used mainly in database programming and scripting.

~ 117 ~
 Example of these languages include Perl, PHP, Python, Ruby, SQL, MatLab (Matrix
Laboratory).
5. Fifth Generation Languages:
These are the programming languages that have visual tools to develop a program.
Examples of fifth generation language include Mercury, OPS5, and Prolog.
The first two generations are called low level languages. The next three generations are called
high level languages.

c. Stages in program development

1. To define or understand a problem:

First of all, you must understand a problem, if you don’t know the problem, you can’t find a
solution.

2. To analyze the problem:

Once you know what the problem is, you can analyze it and make a plan to resolve it.

3. Develop an algorithm and flowchart:

This is a process whereby a set of instructions are used to produce a solution to a given problem.

Any computer program contains instructions in 3 main categories:

-Input instructions: used for supplying data to a program inside the computer.

-Processing instructions: used for manipulating data inside the computer like addition,

multiplication, subtraction...

-Output instructions: used for getting out information.

INPUT PROCESSING OUTPUT

Another method used to specify small algorithm is called flowchart which consists of symbols
connected by arrows.

4. Implementation (writing the computer’s code):

This is the next step where you write the codes for the program to make it work.

~ 118 ~
5. Compiling and debugging the program:

Once the program coding is completed, you compile your program means you translate the
source code to object code and if there are errors, you debug them.

6. Running a program:

To run an application means to execute it and check, if using some data, it is working with the
correctness of the program.

7. Documentation:

When those steps are achieved, you could implement your application. You may add the
explanation on how program works and how to use it.

2.1.2 Description of the environment of C programming

There are many compilers available for C and C++ such as Borland C++, turbo C++, codeblocks
and Dev C++. You need to download any one. Here, we are going to use Dev C++. It will work
for both C and C++.

Dev-C++ is a fully featured graphical IDE (Integrated Development Environment) that uses the
MinGw compiler system to create Windows as well as Console based C/C++ applications. It can
also be used with any other GCC-based compiler like Cygwin.
Dev-C++ is free software and is distributed under the GNU General Public License. Thus we can
distribute or modify the IDE freely. It was originally developed by “Bloodshed Software”. It has
been forked by Orwell after it was abandoned by Bloodshed in 2006.

2.1.3 Steps to install tool to compile and execute C programs

a. A link to Download Dev C++
[Link]

b. The stepwise installation for Dev-C++ is given below.

#1) The first step while we start the installer is to select the language of our choice as shown in
the below screenshot

~ 119 ~
#2) Once you select the appropriate language, you have to agree to the license agreement that
pop-ups next.

#3) Next, we are asked to select the components that we need to install as a part of the Dev-C++
installation.

~ 120 ~
As shown in the above screenshot, we are provided with a list of components available for
installation and a checkbox against each component. We can check/uncheck each box to indicate
which components to install. Click next once the components are selected.
#4) Now the installer prompts the user for the destination folder where the Dev-C++
files/libraries etc. are to be copied.

~ 121 ~
Once we provide the destination folder path, click on Install.
#5) The following screenshot shows the progress of the installation.

~ 122 ~
Once the installation is over, a “finish” dialog that signals the end of the installation appears. We
click finish and then we can launch the dev-C++ IDE.
Now let’s see the working of this C++ IDE in detail.
Development Using Dev-C++ IDE

Configuring Dev C++

Click next and Click OK, once done.

2.1.4 Some commonly used shortcut keys of Dev-C ++

 Restore Ctrl + Z
 Redo Ctrl + Y
 Cut Ctrl + X
 Copy Ctrl + C
 Paste Ctrl + V
 Search and replace content Ctrl + F
 Select all Ctrl + A
 Compile F9
 Run F10
 compile and run F11

~ 123 ~
  Set comment Ctrl + / Cancel comment and repeat again
 Copy line Ctrl + E
 delete line Ctrl + D
 Shift one-tab position to the left overall shift + tab
 Move one-tab position to the right as a whole tab
 The overall code is indented and aligned Ctrl + Shift + A
 Shortcut key setting and viewing: Click "Tools" in the top row, and then click
"Shortcut Key Options".

2.1.5 Some C compilers for UNIX/LINUX Operating System

AOCC (AMD Optimizing C/C++ and Fortran Compilers), LLVM and CLANG

Learning Outcome 2.2 Use C Syntax

2.2.1 Structure of a C program

Every C program contains number of several building blocks known as functions. Each function
of it performs task independently.

A C program comprises the following different sections.

~ 124 ~
Include header file section

Global Declaration Section

/* comments */

main() Function name

/* comments*/

Declaration part

Executable part

User-defined functions

a) Include header file section

C program depends upon some header files for function definition that are used in program. Each
header file by default is extended with .h. The file should be included using # include directive
as given below.

Example: #include <stdio.h>

In this example <stdio.h> file is included i.e. all definitions and prototypes of function defined in
this file are available in the current program.

b) Global declaration

This section declares some variables that are used in more than one function. These variables are
known as global variables. This section must be declared outside of all the functions.

~ 125 ~
c) Function main

Every program written in C language must contain main () function. Empty parentheses after
main are necessary. The function main () is a starting point of every ‘C’ program.

The execution of a program always begins with the function main ().

The program execution starts from the opening brace ({) and ends with the closing brace ( }).
Between these two braces the program should declare the declaration and the executable part.

d) Declaration part

The declaration part declares the entire variables that are used in executable part. The
initialization of variables are also done in this section. The initialization means providing initial
values to the variables.

e) Executable part

This part contains the statements following the declaration of the variables. This part part
contains a set of statements or a single statement. These statements are enclosed between the
braces.

f) User-defined function

The functions defined by the user are called user-defined functions. These functions are
generally defined after the main () function. They can also be defined before main () function.

g) Comments

Comments are not necessary in the program. However, to understand the flow of programs the
programmer can include comments in the program. Comments are used for documentation.

Comments are nothing but some kind of statements which are placed between delimiters /* and
*/.

The compiler does not execute comments. Thus, we can say that comments are not the part of
executable programs.

There are two ways in which we can write comments.

~ 126 ~
1. Using //……………... This is used to write a single line comment.

2. Using /*……………*/: The statements enclosed within /* and */, are used to write multi-
line comments.
Note: When we are working with the multiple line comments then nested comments are not
possible.
Example: First C Program

Let's walk through this program and start to see what different lines are doing:

#include <stdio.h>
main()
{
printf("Hello!");
}
When executed, this program instructs the computer to print out the line "Hello!"

Here is what happened when you compiled the program:

 This C program starts with #include <stdio.h>.

This line includes the "Standard I/O library" into your program. The standard I/O
library lets you read input from the keyboard (called "standard in"), write output to the
screen (called "standard out"). It is an extremely useful library. C has a large number of
standard libraries such as math, string libraries and so on.

A library is simply a package of code that someone else has written to make your life
easier. The line main() declares the main function. Every C program must have a
function named main somewhere in the code. At run time, program execution starts at
the first line of the main function.

 In C, the {and} symbols mark the beginning and end of a block of code.
 The printf statement in C allows you to send output to standard out (for us, the screen). The
portion in quotes “Hello!” is called the format string and describes how the data is to be
formatted when printed.

~ 127 ~
2.2.2 Programming rules
A programmer while writing a program should follow the following rules.

1. C is case-sensitive. That is, upper case and lower case characters are different. All statements
should be written in lower case letters. Upper case letters are only used for symbolic
constants.
2. Blank spaces may be inserted between words. This improves the readability of statements.
However, it is not used while declaring a variable, keyword, constant and function.
3. It is not necessary to fix the position of statement in the program i.e. the programmer can
write the statement anywhere between the two braces following the declaration part.
The user can also write one or more statements in one line separating them with a semicolon
(;). Hence, it is often called a free-form language. The following statements are valid.

a=b+c;

d=b*c;

or

a=b+c; d=b*c;

4. The opening and closing braces should be balanced i.e. for example, if opening braces are
four; then closing braces should also be four.
5. All C statements must end with semicolon.

6. Comments cannot be nested.

For example, /* Welcome to C , /* programming*/ */

2.2.3 The ‘C’ Character Set

The characters used to form words, numbers and expressions depend upon the computer on
which the program runs. The characters in C are classified in the following categories:

1) Letters
2) Digits
3) White spaces

~ 128 ~
 4) Special characters
The whole character set is listed below:

1) Letters 2) Digits 3) White spaces

Capital A to Z All decimal digits 0 to 9 Blank space

Small a to z Horizontal tab

Vertical tab

New line

Form feed

4) Special Characters
, Comma & Ampersand

. Period or dot ^ Caret

; Semi-colon * Asterisk

: Colon - Minus

` Apostrophe + Plus

`` Quotation mark < Less than

! Exclamation mark > Greater than

| Vertical bar () Parenthesis left / right

/ Slash [] Bracket left / right

\ Back slash {} Braces left / right

~ Tilde % Percent

_ Underscore # Number sign or Hash

$ Dollar = Equal to

? Question Mark @ At the rate

~ 129 ~
2.2.4 Delimiters
Language pattern of C uses special kind of symbols, which are called as delimiters.

Delimiters Use

: Colon Use for label

; Semi colon Terminates statement

( ) Parenthesis Used in expression and function

[ ] Square Bracket Used for array declaration

{ } Curly Brace Scope of a statement

# Hash Preprocessor

, comma Variable separator

2.2.5 The ‘C’ keywords

The C keywords are reserved words by the compiler. All the C keywords have been assigned
fixed meaning. The keywords cannot be used as variables names because they have been
assigned fixed jobs.

However, few C compilers allow constructing variable names which exactly coincide with the
keywords. It is suggested not to mix up keywords with variable names.

For utilizing the keywords in a program, no header file is to be included.

auto double int struct

break else long switch

case enum register typedef

char extern return union

const float short unsigned

continue for signed void

~ 130 ~
 default goto sizeof volatile

do if static while

2.2.6 Identifiers
Identifiers are names of variables, functions, and arrays. They are user-defined names, consisting
of sequence of letters and digits, with the letter as the first character. Lower case letters are
preferred.

However, the upper case letters are also permitted. The (_) under score symbol can be used as an
identifier. In general, under score is used as a link between two words in long identifiers.

Examples: User-defined identifiers are as follows.

a) #define N 10
b) #define a 15
Here, ‘N’ and ‘a’ are user-defined identifiers.

2.2.7 Input and Output in c

Two main tasks of any program are to read the data from the input devices and to display the
results on screen.

When a program needs data, it takes the data through the input functions and sends results
obtained through the output functions.

a. Printf( ) Function: Writing Output Data

The printf( ) function is used to write information to standard output(normally monitor screen).

The structure of this function is printf(“format string”, list of arguments);

The format string contains the following:

1. Characters that are simply printed on the screen.

2. Specifications that begin with a % sign and define the output format for display of
each item.
3. Escape sequence characters that begin with a \ sign such as \n, \t, \b etc.
Escape sequences
~ 131 ~
 Escape Sequence Use

\n New line

\b Backspace

\f Form feed

\’ Single quote

\\ Backslash

\0 Null

\t Horizontal Tab

\r Carriage Return

\a Alert

\” Double quote

\v Vertical tab

\? Question Mark

b. Scanf( ) Function: getting user input

The real power of a technical C program is its ability to interact with the program user. This
means that the program gets input values for variables from users.

The scanf( ) function is a built-in C function that allows a program to get user input from the
keyboard. The structure of this function is

scanf(“format string” ,&list of arguments);

Examples: scanf (“%d” , &a);

scanf (“%d %c %f “,&a, &b, &c);

Example of a program : A C program to calculate the average of three numbers supplied using
the keyboard.

~ 132 ~
 #include<stdio.h> #include<conio.h>
main()
{
int a,b,c,average;
printf(“Enter the three numbers”);
scanf(“%d %d %d”,&a,&b,&c);
average= (a+ b +c)/3;
printf(“The average=%d”,average);
getch();

Learning Outcome 2.3: Describe Data Types

2.3.1 Overview of Data types
All C compilers support a variety of data types. This enables the programmer to select the
appropriate data type as per the need of the application. Generally, data is represented using
numbers or characters. The numbers may be integers or real. The different compilers support the
different data types.

a. Definition

A data-type in C programming is a set of values and is determined to act on those values. C

provides various types of data-types which allow the programmer to select the appropriate type
for the variable to set its value.

b. Importance of data types

C Data Types are used to:

 Identify the type of a variable when it declared.

 Identify the type of the return value of a function.
 Identify the type of a parameter expected by a function.

2.3.2. Description of 4 Data types in C

There are 4 data types in C language.

~ 133 ~
 Types Data Types

Basic Data Type int, char, float, double

Derived Data Type array, pointer, structure, union

Enumeration Data Type enum

Void Data Type void

a. Basic Data Type

They are called Fundamental, primary, build-in or Primitive data type these are the data types
whose variable can hold maximum one value at a time
Example

int a; // valid
a = 10,20,30; // invalid

Following are the examples of some very common data types used in C:
 char: The most basic data type in C. It stores a single character and requires a single byte
of memory in almost all compilers.
 int: As the name suggests, an int variable is used to store an integer.
 float: It is used to store decimal numbers (numbers with floating point value) with single
precision.
 double: It is used to store decimal numbers (numbers with floating point value) with
double precision.
b. Derived Data Type

These data type are derived from fundamental data type. Variables of derived data type allow
us to store multiple values of same type in one variable but never allows to store multiple
values of different types. These are the data type whose variable can hold more than one value
of similar type. In C language it can be achieve by array.
Example

~ 134 ~
 int a[] = {10,20,30}; // valid
int b[] = {100, 'A', "ABC"}; // invalid

c. Enumeration Data Type

Enumeration is a user defined datatype in C language. It is used to assign names to the integral
constants which makes a program easy to read and maintain. The keyword “enum” is used to
declare an enumeration.
Here is the syntax of enum in C language,

enum enum_name{const1, const2, ....... };

The enum keyword is also used to define the variables of enum type. There are two ways to
define the variables of enum type as follows.
// In both of the below cases, "day" is defined as the variable of type week.

enum week {Mon, Tue, Wed};

enum week day;

// Or
enum week {Mon, Tue, Wed} day;

d. Void Data Type

The void data type is an empty data type that refers to an object that does not have a value of
any type. Here are the common uses of void data type.
 When it is used as a function return type.

void myFunction(int i);

Void return type specifies that the function does not return a value.
 When it is used as a function's parameter list:

int myFunction(void);

~ 135 ~
Void parameter specifies that the function takes no parameters.
 When it is used in the declaration of a pointer variable:

void *ptr;

It specifies that the pointer is "universal" and it can point to anything. When we want to access
data pointed by a void pointer, first we have to type cast it.
2.3.3 Data type modifiers in C
In c language Data Type Modifiers are keywords used to change the properties of current
properties of data type. Data type modifiers are classified into following types.
 long
 short
 unsigned
 signed
Modifiers are prefixed with basic data types to modify (either increase or decrease) the amount
of storage space allocated to a variable.
For example, storage space for int data type is 4 bytes for 32-bit processor. We can increase the
range by using long int which is 8 bytes. We can decrease the range by using short int which is
2 bytes.

long:

This can be used to increased size of the current data type to 2 more bytes, which can be
applied on int or double data types. For example, int occupy 2 byte of memory if we use long
with integer variable then it occupies 4 byte of memory.

~ 136 ~
Syntax

long a; --> by default which represent long int.

short

In general int data type occupies different memory spaces for a different operating system; to
allocate fixed memory space short keyword can be used.
Syntax

short int a; --> occupies 2 bytes of memory space in every operating system.

unsigned

This keyword can be used to make the accepting values of a data type is positive data type.
Syntax

unsigned int a =100; // right

unsigned int a=-100; // wrong

Signed

This keyword accepts both negative or positive value and this is default properties or data type
modifiers for every data type.
Example

int a=10; // right

int a=-10; // right
signed int a=10; // right
signed int a=-10; // right

Note:

~ 137 ~
 1. In real time no need to write signed keyword explicitly for any data type.
2. The storage representation and machine instructions differ from machine to
machine. sizeof operator can use to get the exact size of a type or a variable on a
particular Platform.

2.3.4. Entire Data Types in C

The entire data types supported by the ‘C’.

Data type Size ( bytes) Range Control String

Char 1 -128 to 127 %c

Unsigned char 1 0 to 255 %c

Short or int 2 - 32 768 to 32 767 %d or %i

Unsigned int 2 0 to 655 355 %u

Long 4 -2 147 438 648 to2 147 438 647 %ld

Unsigned long 4 0 to 4 294 967 295 %lu

Float 4 -3.4e10-38 to +3.4e10+38 %f or %g

Double 8 -1.7e10-308 to +1.7e10+308 %lf

Long double 10 -1.7e10-4 932 to +1.7e10+4 932 %lf

2.3.5 Examples of Application of data types

Example 1:
#include <stdio.h>
int main()
{
int a = 4000; // positive integer data type
float b = 5.2324; // float data type
char c = 'Z'; // char data type
long d = 41657; // long positive integer data type

~ 138 ~
 long e = -21556; // long -ve integer data type
int f = -185; // -ve integer data type
short g = 130; // short +ve integer data type
short h = -130; // short -ve integer data type
double i = 4.1234567890; // double float data type
float j = -3.55; // float data type
}
Example 2:
#include <stdio.h>
#include <limits.h>
int main()
{
printf("Storage size for int is: %d \n", sizeof(int));
printf("Storage size for char is: %d \n", sizeof(char));
return 0;
}

Learning Outcome 2.4: Use variables

2.4.1 Description of variables
a. Definition

A variable is a data name used for storing a data value. Its value may be changed during the
program execution. The variables value keeps on changing during the execution of a program.

In other words, a variable can be assigned different values at different times during the execution
of a program.

A variable name may be declared based on the meaning of the operation. Some meaningful
variable names are as follows.

Example: height, average, sum etc.

b. Rules for defining variables

1) They must begin with a letter without spaces but underscore is permitted.

~ 139 ~
2) The length of the variable varies from compiler to compiler. Generally most of the compilers
support 8 characters excluding extension. However, the ANSI standard recognizes the
maximum length of a variable up to 31 characters.
3) The variable should not be a C keyword
4) The variable names may be a combination of upper and lower characters. For example suM
and sum are not the same.
5) The variable name should not start with a digit.

c. Declaring variables

The declaration of variables should be done in the declaration part of the program. The variables
must be declared before they are used in the program.

Declaration provides two things:

1) Compiler obtains the variable name.

2) It tells to the compiler data type of the variable being declared and helps in allocating the
memory.
The syntax of declaring a variable is as follows:

Syntax

Data_typevariable_name;

Example:

int age;

char m;

float s;

double k;

int a,b,c;

d. Initializing variables

~ 140 ~
Variables declared can be assigned or initialized using an assignment operator ‘=’. The
declaration and initialization can also be done in the same line.

Syntax:

Variable_name = constant;

or

data_type variable_name = constant;

Example:

x=2; where x is an integer variable.

int y=2;

int x=y=z=1; more variables have been initialized with one value.

Note: If no input values are assigned by the user than system will gives a default value called
garbage value.
Garbage value can be any value given by system and that is no way related to correct
programs. This is a disadvantage of C programming language and in C programming it can
overcome using variable initialization.
2.4.2 Key Differences between Identifier and Variable

1. Both an identifier and a variable are the names allotted by users to a particular entity in a
program. The identifier is only used to identify an entity uniquely in a program at the time of
execution whereas, a variable is a name given to a memory location, that is used to hold a
value.
2. Variable is only a kind of identifier, other kinds of identifiers are function names, class
names, structure names, etc. So it can be said that all variables are identifiers whereas, vice
versa is not true.

~ 141 ~
As identifier and variable names are user-defined names, it should be taken care that no two
identifiers or no two variable names in a program should be the same. It will create a problem of
ambiguity in a program.

2.4.3 Types of Variable

There are many types of variables in c:
1. local variable
2. global variable
3. static variable
4. automatic variable
5. external variable
a. Local Variable
A variable that is declared inside the function or block is called a local variable.
It must be declared at the start of the block.
void function1(){
int x=10;//local variable
}
You have to initialize the local variable before it is used.
b. . Global Variable
A variable that is declared outside the function or block is called a global variable. Any function
can change the value of the global variable. It is available to all the functions.
It must be declared at the start of the block.

int value=20;//global variable

void function1(){
int x=10;//local variable
}
c. . Static Variable
A variable that is declared with the static keyword is called static variable.
It retains its value between multiple function calls.

void function1(){
int x=10;//local variable
static int y=10;//static variable

~ 142 ~
x=x+1;
y=y+1;
printf("%d,%d",x,y);
}
If you call this function many times, the local variable will print the same value for each
function call, e.g, 11,11,11 and so on. But the static variable will print the incremented
value in each function call, e.g. 11, 12, 13 and so on.
d. Automatic Variable
All variables in C that are declared inside the block, are automatic variables by default. We can
explicitly declare an automatic variable using auto keyword.
void main(){
int x=10;//local variable (also automatic)
auto int y=20;//automatic variable
}

e. External Variable
We can share a variable in multiple C source files by using an external variable. To declare an
external variable, you need to use extern keyword.
myfile.h
extern int x=10;//external variable (also global)
program1.c
#include "myfile.h"
#include <stdio.h>
void printValue(){
printf("Global variable: %d", x);
}

Learning Outcome 2.5: Use Constants

2.5.1 Description of constants in C
a. Definition
Constant is a name given to the variable whose values can’t be altered or changed. A constant is
very similar to variables in the C programming language, but it can hold only a single variable

~ 143 ~
during the execution of a program. It means that once we assign value to the constant, then we
can’t change it throughout the execution of a program- it stays fixed.
There are several types of constants in C.

Constants

Character Constants
Numeric Constants

Integer Real constants Single Character Constants String Constants

Constants
b. Numerical Constants

1) Integer constants

These are the sequence of numbers from 0 to 9 without decimal points or fractional part or any
other symbols.

It requires minimum two bytes and maximum four bytes.

Integer constants could either be positive or negative or may be zero. The number without a sign
is assumed as positive.

Example 10, 20, +30, -44 etc.

2) Real constants

Real constants are often known as floating point constants. Integer constants are unfit to
represent many quantities. Many parameters or quantities are defined not only in integers but
also in real numbers. For example, length, height, prize etc. are measured in real numbers.

Example 2.5, 5.521 etc.

c. Character Constant

~ 144 ~
1) Single character constants

A character constant is a single character. They are also represented with a single digit or a single
special symbol or white space enclosed within a pair of single quote marks.

Example‘a’, ‘8’, ‘’ etc.

Character constants have integer values known as ASCII (American Standard Code for
Information Interchange) values. For example, the statement printf( “%c %d”, 65, ‘B’) will
display the characters ‘A’ and 66.

2) String constants

String constants are sequence of characters enclosed within a double quote marks. The string
may be a combination of all kinds of symbols.

Example “Hello”, “a”,”IPRC MUSANZE” etc.

2.5.2 Creation and Use of Constants in C

We can create constants in the C programming language by using two of the concepts mentioned
below:

 By using the ‘#define’ preprocessor

 By using the ‘const’ keyword.

a. Use of the ‘const’ Keyword

The ‘const’ keyword is used to create a constant of any given datatype in a program. For creating
a constant, we have to prefix the declaration of the variable with the ‘const’ keyword. Here is the
general syntax that we follow when using the ‘const’ keyword:

const datatype constantName = value ;

OR

const datatype constantName ;

Example:

~ 145 ~
const int a = 10 ;

In this case, a is an integer constant that has a fixed value of 10.

The program will run as follows:

#include<stdio.h>
#include<conio.h>
void main(){
int q = 9 ;
const int a = 10 ;
q = 15 ;
a = 100 ; // creates an error
printf(“q = %d\n a = %d”, q, a ) ;
}
The program given above creates an error. It is because we are trying to change the value of the
constant variable (a = 100).

b. Use of the ‘#define’ preprocessor

One can also use the ‘#define’ preprocessor directive to create the constants. And when we
create the constants by making use of the preprocessor directive, we must define it in the very
beginning of the program. It is because we must write all the preprocessor directives before the
global declaration.

Here is the syntax that we must use for creating a constant by making use of the ‘#define’
preprocessor directive:

#define CONSTANTNAME value

Example:

#define PI 3.14

In this above-mentioned case, PI is a constant, and it has a value of 3.14.

We can run a program for this as follows:

~ 146 ~
#include<stdio.h>
#include<conio.h>
#define PI 3.14
void main(){
int a, area ;
printf(“Enter the radius of the given circle here : “) ;
scanf(“%d”, &a) ;
area = PI * (a * a) ;
printf(“The area of the circle is = %d”, area) ;
}

Learning Outcome 2.6: Use operators

2.6.1. Description and application of operators in C

In order to perform different kinds of operations, C uses different types of operators.

An operator indicates an operation to be performed on data that yields a value. Using various
operators in C one can link the variables and constants.

An operand is a data item on which operators perform the operations.

Some operators require two operands, while others act upon only one operand. The operators are
classified into unary, binary and ternary depending on whether they operate on one, two or three
operands respectively.

Types of operators

Type of Operator Symbolic Representation

Arithmetic operators +, -, *, / and %

Relational operators >, <, = =, >=, <= and !=

Logical operators &&, || and !

~ 147 ~
 Increment and decrement ++ and --

Assignment operator =

Bitwise operators &, |, ^,>>,<< and ~

Comma operator ,

Conditional operator ?:

Size of () and ‘&’ operator sizeof() and &

a. Arithmetic operators

These operators are commonly used in most of the computer languages. These arithmetic
operators are used for numerical calculations between two values. They are so called Binary
Arithmetic Operators.

Arithmetic Operator Operator explanation Example

+ Addition 4+8=12

- Subtraction 8-7=1

* Multiplication 6*5=30

/ Division -6/3=-2

% Modular division 11%3=2 (Remainder is

2)

b. Relational operators

These operators are used to distinguish between two variables depending on their relations.
These operators provide the relationship between the two expressions. If the relation is true then
it returns a value 1 otherwise 0 for false relation.

~ 148 ~
Relational operators

Operator Description or Action Example Return Value

> Greater than 5>4 1

< Less than 10<9 0

<= Less than or equal than 10<=10 1

>= Greater than or equal to 11>=5 1

== Equal to 2= = 3 0

!= Not equal to 3!=3 0

A program to use various relational operators and display their return values

#include <stdio.h>

#include <conio.h>

main()

printf(“\n Condition : Return Values\n”);

printf(“\n 10!=10 : %d”,10!=10);

printf(“\n 10==10 : %d”,10= =10);

printf(“\n 10>=10 : %d”,10>=10);

printf(“\n 10<=100 : %d”,10<=10);

printf(“\n 10!=9 : %d”,10!=9);

getch();

Output:

~ 149 ~
Condition: Return Values

10! =10 :0

10==10 :1

10>=10 :1

10<=100 :1

10! =9 :1

c. Logical Operators

Logical operators are used to join two expressions. After checking the conditions, logical true (1)
or false (0) is provided. The operands could be constants, variables and expressions.

Operator Description or Action Example Return Value

&& Logical AND 5>3 && 5<10 1

|| Logical OR 8>5 || 8<2 1

! Logical Not !(8= =8) 0

The logical AND (&&) operator provides true result when both expressions are true otherwise 0.

The logical OR (||) operator provides true result when one of the expressions is true otherwise 0.

The logical NOT (!) operator provides 0 if the condition is true otherwise 1.

A program to illustrate the use of logical operators

#include <stdio.h>

#include <conio.h>

main()

printf(“\n Condition : Return Values\n”);

printf(“\n 5>3 && 5<10”, : %5d”, 5>3 && 5<10);

~ 150 ~
printf(“\n 8>5 || 8<2 : %5d”, 8>5 || 8<2);

printf(“\n !(8= = 8) : %5d”, !(8= = 8));

getch();

Output:

Condition: Return Values

5>3 && 5<10 : 1

8>5 || 8<2 : 1

!(8= = 8) : 0

d. Increment (++) & Decrement (--) Operators

The operator ++ adds one to its operand whereas the operator -- subtracts one from its operand.

x=x+1 can be written as x++

x=x-1 can be written as x--

Both these operators may either follow or precede the operand. That is, x=x+1; can be
represented as x++ or ++x.

If ++ or -- are used as a suffix to the variable name then the post increased/ decreased operations
take place.

Example: x=20;

y=10;

z=x*y++;

In the above equation the current value of y is used for the product. The

result is 200,which is assigned to ‘z’. After multiplication, the value of y is

increased by one.

~ 151 ~
If ++ or -- are used as a prefix to the variable name then the pre increased/ decreased operations
take place.

Example: x=20;

y=10;

z=x*++y;

In the above equation the value of y is increased and then used for multiplication. The result is
220 which is assigned to ‘z’.

A program to show the effect of increment operator as a suffix

#include <stdio.h>

#include <conio.h>

main()

int a,z,x=10,y=20;

z=x*y++ ;

a=x*y ;

printf(“\n %d %d”,z,a);

Output:

200 210

A program to show the effect of increment operator as a prefix

#include <stdio.h>

#include <conio.h>

main()

~ 152 ~
{

int a,z,x=10,y=20;

z=x*++y ;

a=x*y ;

printf(“\n %d %d”,z,a);

Output:

210 210

e. Assignment operators

In addition to usual assignment operator =, C has a set of shorthand operators, that simplifies the
coding of a certain type of assignment statement.

It is of the form:

var op = exp;

where var is a variable, op is a C binary arithmetic operator and exp is an expression.

Statement Equivalent Statement

a+=b a=a+b
a-=b a=a-b
a*=b a=a*b
a*=b+c a = a * ( b+ c)
a%=b a=a%b
a*=a a=a*a

f. Bitwise operators

~ 153 ~
C supports a set of bitwise operators. The lowest logical element in the memory is bit. C allows
the programmer to interact directly with the hardware of a particular system through bitwise
operators and expression.

These operators work only with int and char datatypes and cannot be used with float and double
type.

The following table shows the bitwise operators that are available in C.

Operator Meaning

>> Right shift

<< Left shift

^ Bitwise xor (Exclusive OR)

~ One’s complement

& Bitwise AND

| Bitwise OR

A program to shift input data by two bits right

#include <stdio.h>

#include <conio.h>

main()

int x,y;

printf(“\n Read the integer from the keyboard (x):”);

scanf(“%d”,&x);

x>>=2;

~ 154 ~
y=x;

printf(“The right shifted data is =%d”,y);

Output:

Read the integer from the keyboard (x):8

The right shifted data is =2

g. Comma operator (,)

The comma operator is used to separate two or more expressions. The comma operator has the
lowest priority among all the operators.

A program to illustrate the use of comma ( , ) operator

# include < stdio.h>

# include <conio.h>

main()

printf(“ Addition = %d \n Subtraction =%d”,2+3,5-4);

Output:

Addition =5

Subtraction =1

h. Conditional operator (?: )

The conditional operator contains a condition followed by two statements or values. If the
condition is true the first statement is executed otherwise the second statement.

~ 155 ~
The conditional operator ( ? ) and ( : ) are sometimes called ternary operators because they take
three arguments.

Syntax: Condition? (expression1): (expression 2);

Two expressions are separated by a colon. If the condition is true expression1 gets evaluated
otherwise expression2. The condition is always written before question mark ( ?).

A program to use the conditional operator with two values.

#include <stdio.h>

#include <conio.h>

main()

printf(“Result as a value =%d”,2= = 3?4:5);

Output:

Result as a value= 5

Write a program to use the conditional operator with two statements.

#include <stdio.h>

#include <conio.h>

main()

clrscr();

3>2?printf(“True”):printf(“False);

Output:

~ 156 ~
True

i. Sizeof () and ‘&’ operator

The size of () gives the bytes occupied by a variable. The number of bytes occupied by a variable
to variable depends upon its data type.

The ‘&’ operator prints address of the variable in the memory.

Write a program to use ‘&’ and ‘size of’ operator and determine the size of integer and float
variables.

#include <stdio.h>

#include <conio.h>

main()

short int x=2 ;

float y=4 ;

printf(“\n Sizeof(x)=%d”,sizeof(x));

printf(“\n Sizeof(y)=%d”,sizeof(y));

printf(“\n Address of x=%u and y=%u”,&x,&y);

Output:

Sizeof(x)=2

Sizeof(y)=4

Address of x= 65524 and y=65522

~ 157 ~
2.6.2 Priority of Operations and their Clubbing
Various relational operations have different priorities or precedence. If an arithmetic expression
contains more operators, then the execution will be performed according to their priorities. The
precedence is set for different operators in C.

List of operators with priority wise

Operators Operation Clubbing Priority

() Function call Left to right 1st

[] Array expression

Or Square bracket

-> Structure operator

. Structure operator

+ Unary plus Right to left 2nd

- Unary minus

++ Increment

-- Decrement

! Not operator

~ Ones complement

* Pointer operator

& Address operator

Sizeof Size of an object

Type Type cast

* Multiplication Left to right 3rd

/ Division

+ Addition Left to right 4th

~ 158 ~
 -

Subtraction

<< Left shift Left to right 5th

>> Right shift

< Less than Left to right 6th

<= Less than or equal to

> Greater than

>= Greater than or equal to

== Equality Left to right 7th

!= Inequality

& Bitwise AND Left to right 8th

^ Bitwise XOR Left to right 9th

! Bitwise OR Left to right 10th

&& Logical AND Left to right 11th

|| Logical OR Left to right 12th

?: Conditional operator Right to left 13th

=, *=, - =, &=, += Assignment Operators Right to left 14th

^=, |=, <<=, >>=

, Comma operator Left to right 15th

When two operators of the same priority are found in the expression, precedence is given to the
extreme left operator.

Example x= 5 * 4 + 8 / 2;

~ 159 ~
 1 2

Here, 5*4 is solved first, * and / have the same priority and the operator * occurs before /.

If there are more sets of parenthesis in the expression, the innermost parenthesis will be solved
first, followed by the second and so on.

Example y= ( 8 / (2 *( 2 * 2) ) );

3 2

Learning Outcome 2.7: Use conditions

2.7.1 Description of Decision control statements in C
The decision statements of a language determine the order in which the statements are executed.
We also need to be able to specify that a statement, or a group of statements, is to be carried out
conditionally, only if some condition is true.

2.7.2 Application of Decision Control statements

A decision statement or a conditional structure can be implemented in C using
The if statement
The if-else statement
The nested if-else statement
The switch statement.
a. The if Condition
Syntax for the simplest if statement

~ 160 ~
 if (condition) /*no semi-colon*/
statement;
Suppose if it is required to include more than one statement, then a compound statement is used,
in place of single statement.

The form of compound statement is

if (condition)
{
statement1;
statement2;
}
The statement is executed only when the condition is true. In case the condition is false the
compiler skips the line within the if block.

A program to check equivalence of two numbers. Use if statement.

#include<stdio.h>
#include<conio.h>
main()
{
clrscr();
int m,n;
printf("\n Enter two numbers :");
scanf("%d %d",&m,&n);
if(m-n= =0)
printf("\n Two numbers are equal");
getch();
}
Output
Enter two numbers: 8 8

~ 161 ~
Two numbers are equal
b. The if…..else Statement
The if….else statement takes care of true as well as false conditions. It has two blocks. One
block is for if and it is executed when the condition is true and the other block of else is executed
when the condition is false.
It’s syntax:
if (condition is true)
execute the statement1;
else
execute the statement2;

Example:
Write a program to check whether the year is Leap or Not. Use if…else statement.
#include<stdio.h>
#include<conio.h>
main()
{
clrscr();
int year;
printf("\n Enter year :");
scanf("%d “,&year);
if(year % 4= =0)
printf("\n Leap year.");
else
printf(“\n Not Leap Year.”);
getch();
}
Output
Enter year: 2020

~ 162 ~
Leap year.

c. Nested if-else statement

In the case of many logical conditions, nested if-else function is used.
When a series of conditions are involved, we can use more than one if-else statement in nested
form.
This form is also known as if-else if-else statements. The general form of if-else if-else
statement is :
if(condition)
statements;
else if(condition)
statements;
else
statements;
Note that a program contains a number of else if statements and must be ended with else
statement
A program to calculate energy bill. Read the starting and ending meter reading.
The charges are as follows:
No of Units consumed Rates in RWF
200-500 3.50
100-200 2.50
Less than 100 1.50
#include<stdio.h>
#include<conio.h>
main()
{
int initial,final,consumed;
float total;
printf("\n Enter the initial and final readings:");

~ 163 ~
scanf("%d %d",&initial,&final);
consumed=final-initial;
if(consumed>=200&&consumed<=500)
total=consumed*3.50;
else if(consumed>=100&&consumed<200)
total=consumed*2.50;
else
total=consumed*1.50;
printf("\n Total bill for %d units is %f",consumed,total);
getch();
}
Output:
Enter the initial and final readings: 800 850
Total bill for 50 units is 75.000000
d. The switch statement
The switch statement is a multi-way branch statement. In the program if there is a possibility to
make a choice from a number of options, this structure is useful.

The switch statement requires only one argument of any data type, which is checked with
number of case options. The switch statement evaluates expression and then looks for its value
among the case constants. If the value matches with case constant, this particular case statement
is executed; if not, default is executed.

Switch, case and default are reserved keywords. Every case statement terminates with a colon’:’,
the break statement is used to exit from the current case structure.

switch (variable or expression)

{
case constant A:
statement;

~ 164 ~
 break;
case constant B:
statement;
break;
…
default:
statement;
}
Example:
Write a program to provide multiple functions such as 1. Addition [Link]
[Link] 4. Division [Link] by using switch() statement.

#include<stdio.h>
#include<conio.h>
main()
{
clrscr();
int a,b,c,ch;
printf("\t ============");
printf("\n\t MENU");
printf("\n\t ============");
printf("\n\t[1] Addition");
printf("\n\t[2] Subtraction");
printf("\n\t[3] Multiplication");
printf("\n\t[4] Division");
printf("\n\t[5] Reminder");
printf("\n\t[0] Exit");
printf("\n\t ============");
printf("\n Enter two numbers:");

~ 165 ~
scanf("%d %d",&a,&b);
printf("\n\n\t Enter your choice:");
scanf("%d",&ch);
if(ch<=5&ch>=0)
switch(ch)
{
case 1:
c=a+b;
printf("\n Addition:%d",c);
break;
case 2:
c=a-b;
printf("\n Subtraction:%d",c);
break;
case 3:
c=a*b;
printf("\n Multiplication:%d",c);
break;
case 4:
c=a/b;
printf("\n Division:%d",c);
break;
case 5:
c=a%b;
printf("\n Reminder:%d",c);
break;
case 0:
printf("\n Terminated by choice");

~ 166 ~
default:
printf("\n Invalid Choice");
}
getch();
}
Output:
============
MENU
============
[1] Addition
[2] Subtraction
[3] Multiplication
[4] Division
[5] Reminder
[0] Exit
============
Enter two numbers: 8 3
Enter your choice: 5
Reminder: 2

Learning Outcome 2.8: Use Loops

2.8.1 Description of loops in C programming
We need to be able to carry out a statement or a group of statements repeatedly based on certain
conditions. This kind of situations is described in C using Loop Control structures.

A loop is defined as a block of statements which are repeatedly executed for a certain number of
times.

Loop control structures can be implemented in C using:

~ 167 ~
for loop

while loop

do-while loop

2.8.2 Application of loop control statements

a. The for loop

The for loop is used to repeat the execution statement for some fixed number of times.

The syntax of for loop is:

for(initialization; condition; increment/decrement)

statement;

where the statement is single or compound statement.

initialization is the initialization expression, usually an assignment to the loop-control variable.

This is performed once before the loop actually begins execution.

condition is the test expression, which evaluated before each iteration of the loop, which
determines when the loop will exist.

Increment/decrement is the modifier expression, which changes the value of loop control
variable. This expression is executed at the end of each loop.

Various Formats of ‘for’ loop

Syntax Output Remarks

1) for(;;) Infinite loop No arguments

2) for (a=0;a<=20;) Infinite loop ‘a’ is neither increased or decreased

3) for(a=0;a<=10;a++) Displays value ‘a’ is increased from 0 to 10. Curly

braces are not necessary. Default
printf(“%d”,a); from 0 to 10
scope of for loop is one statement
after for loop.

4) for(a=10;a>=0;a--) Displays value ‘a’ is decreased from 10 to 0

~ 168 ~
 printf(“%d”,a); from 10 to 0

A program to display even numbers from 0 to 14 using for loop.

#include <stdio.h>

#include <conio.h>

void main()

int i;

for(i=0;i<=15;i+=2)

printf("%5d",i);

getch();

Output:

0 2 4 6 8 10 12 14

b. While loop.

The while loop is best suited to repeat a statement or a set of statements as long as some
condition is satisfied.

The syntax of while loop is:

initial expression;

while(conditional-expression)

statement;

~ 169 ~
increment/decrement; }

where the statement (body of the loop) may be a single statement or a compound statements.
The conditional-expression (test condition) must results zero or non-zero.

A program to display even numbers from 0 to 14 using while loop.

#include <stdio.h>

#include <conio.h>

void main()

clrscr();

int i=0;

while(i<=15)

printf("%5d",i);

i+=2;

getch();

Output:

2 4 6 8 10 12 14

c. Do while loop.

The while loop is best suited to repeat a statement or a set of statements as long as some
condition is satisfied.

The general form of do while loop is

~ 170 ~
initial expression;

do

statement;

increment/decrement;

} while(conditional-expression);

where the statement (body of the loop) may be a single statement or a compound statements.
The conditional-expression (test condition) must results zero or non-zero.

Write a program to display even numbers from 0 to 14 using do while loop.

#include <stdio.h>

#include <conio.h>

void main()

int i=0;

do

printf("%5d",i);

i+=2;

while(i<=15);

getch();

Output:

~ 171 ~
0 2 4 6 8 10 12 14

d. Nested loop

C programming allows to use one loop inside another loop. The following shows a few examples
to illustrate the concept.

Syntax:

The syntax for a nested for loop statement in C is as follows

for ( init; condition; increment ) {

for ( init; condition; increment ) {

statement(s);

statement(s);

The syntax for a nested while loop statement in C programming language is as follows

while(condition) {

while(condition) {

statement(s);

} statement(s);

The syntax for a nested do...while loop statement in C programming language is as follows

do {

statement(s);

do {

statement(s);

~ 172 ~
 }while( condition );

}while( condition );

A final note on loop nesting is that you can put any type of loop inside any other type of loop.
For example, a 'for' loop can be inside a 'while' loop or vice versa.

Example:

A program to display the stars as shown below.

**

***

****

*****

#include<stdio.h>

#include<conio.h>

main()

int x,i,j;

printf("How many lines stars (*) should be printed ?:");

scanf("%d",&x);

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

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

~ 173 ~
 printf("*");

printf("\n");

getch();

Output:

How many lines stars (*) should be printed? :5

**

***

****

*****

d. Control /Jumping statements

C supports the following control statements.

a) Break statement

The break statement in C programming has the following two usages:

~ 174 ~
  When a break statement is encountered inside a loop, the loop is immediately
terminated and the program control resumes at the next statement following the
loop.
 It can be used to terminate a case in the switch statement (covered in the preceding
chapter).

If you are using nested loops, the break statement will stop the execution of the innermost loop
and start executing the next line of code after the block.

The syntax for a break statement in C is as follows:

break;

Example:

#include <stdio.h>
main ()
{
int a = 10;
while( a < 20 )
{
printf("value of a: %d\n", a);
a++;
if( a > 15)
{
/* terminate the loop using break statement */
break;
}
}
}
b) Continue statement

~ 175 ~
The continue statement in C programming works somewhat like the break statement. Instead of
forcing termination, it forces the next iteration of the loop to take place, skipping any code in
between.

For the for loop, continue statement causes the conditional test and increment portions of the
loop to execute. For the while and do...while loops, continue statement causes the program
control to pass to the conditional tests.

The syntax for a continue statement in C is as follows:

continue;

Example:

#include <stdio.h>
main () {
int a = 10;
do
{
if( a == 15)
{
/* skip the iteration */
a = a + 1;
continue;
}
printf("value of a: %d\n", a);
a++;
}while( a < 20 ); }

c) Goto statement
A goto statement in C programming provides an unconditional jump from the ‘goto’ to a labeled
statement in the same function.

The syntax for a goto statement in C is as follows:

~ 176 ~
goto label;

.. ..

label:

statement;

Here label can be any plain text except C keyword and it can be set anywhere in the C program
above or below to goto statement.

NOTE: Use of goto statement is highly discouraged in any programming language because it
makes difficult to trace the control flow of a program, making the program hard to understand
and hard to modify. Any program that uses a goto can be rewritten to avoid them.

#include <stdio.h>
main ()
{
int a = 10;
LOOP:
do
{
if( a == 15)
{
a = a + 1;
goto LOOP;
}
printf("value of a: %d\n", a);
a++;
}while( a < 20 ); }

Learning Outcome 2.9: Use arrays

2.9.1 Description of arrays in C programming
a. Definition

~ 177 ~
An Array is a collection of same data type. The elements of an array are referred by a common
name and are differentiate from one another by their position within an array. The elements of an
array can be of any data type but all elements in an array must be of the same type.

b. Characteristic of an array
 The declaration int a[5] is nothing but creation of 5 variables of integer types in the memory.
 All the elements of an array share the same name and they are distinguished from one
another with the help of an element number.
 The element number in an array plays major role for calling each element.
 Any particular element of an array can be modified separately without disturbing other
elements.
int a[5]={1,2,3,4,8};
If a programmer needs to replace 8 with 10, he/she doesn’t require to change all other
numbers expect 8. To carry out this task, the statement a[4]=10 can be used. Here all other
three elements are not disturbed.
 Any element of an array a[] can be assigned/equated to another ordinary variable or array of
its type.

For example

b=a[2];

a[2]=a[3];

In the statement b=a[2] or vice versa, value of a[2] is assigned to ‘b’ where b is an
integer.

In the statement a[2]=a[3] or vice versa, value of a[3] is assigned to a[2] where both
statements are of the same array.

 The array elements are stored in continuous memory locations. The amount of storage
required for holding elements of the array depends on its type and size. The total size in
bytes for a single dimensional array is computed as shown below.

Total bytes=sizeof(data type) X size of array

~ 178 ~
 c. Types of array

Arrays are of 2 types. They are:

A) Single Dimensional Array

Single or One Dimensional array is used to represent and store data in a linear form.

Array having only one subscript variable is called One-Dimensional array

It is also called as Single Dimensional Array or Linear Array

B) Multi Dimensional Array

Array having more than one subscript variable is called Multi-Dimensional array.

Multi-Dimensional Array is also called as Matrix

2.9.2 Single Dimensional Array

a. Declaring Arrays syntax

The general form of declaring an array is

type array_name[size];

where type is a valid datatype, array_name is the name of the array and size is the number of
elements that array_name contains.

Example:

int A[100];

int - data type of elements that an array contains

A - name of array

100 - size of an array

b. Initializing Arrays

Initialization of arrays during declaration

Similar to other datatypes, the array also can be initialized at the time of declaration.

~ 179 ~
int num[5] ={3,2,1,5,4};

char name[ ] = { ‘c ‘,’ o ‘,’ m’ , ‘p’ , ‘u ‘, ‘t’ , ‘e’ , ‘r’ , ‘s’ };

float rate[ ] = {20.5,15.75,12.34};

a. Accessing Array Elements

The individual elements of an array can be referenced by means of its subscript (or index).

Suppose A is an array of 20 elements, we can reference each element as

A[0] refers to 1st element

A[1] refers to 2nd element

A[2] refers to 3rd element

A[19] refers to 20th element

Note: Subscript enclosed within a pair of curly square brackets.

In C subscript starts from 0. That is, if we declare an array of size n, then we can refer the
elements from 0 to (n-1)th element.

Example:

A program to compute and display addition of even numbers and product of odd numbers for an
array of 5 numbersof your choice

#include <stdio.h>
#include <conio.h>
main()
{
int n,m[5]={6,8,9,10,12},i,a=0,s=1;

~ 180 ~
for(i=0;i<5;i++)
{
if(m[i]%2= =0)
{
printf("\n Even number:%d",m[i]);
a=a+m[i];
}
else
{
printf("\n Odd number :%d",m[i]);
s=s*m[i];
}
}
printf("\n\n\n Addition of even numbers:%d",a);
printf("\n Product of odd numbers:%d",s);}
2.9.3 Multi Dimensional Array
C programming language allows multidimensional arrays.

a. Declaring a Multidimensional array

Here is the general form of a multidimensional array declaration.

type name[size1][size2]...[sizeN];

For example, the following declaration creates a three dimensional integer array

int threedim[5][10][4];

b. Two-dimensional Arrays

The simplest form of multidimensional array is the two-dimensional array. A two-dimensional

array is, in essence, a list of one-dimensional arrays. To declare a two-dimensional integer array
of size [x][y], you would write something as follows

~ 181 ~
Type arrayName [ x ][ y ];

Where type can be any valid C data type and arrayName will be a valid C identifier. A two-
dimensional array can be considered as a table which will have x number of rows and y number
of columns. A two-dimensional array a, which contains three rows and four columns can be
shown as follows

Thus, every element in the array a is identified by an element name of the form a[ i ][ j ], where
'a' is the name of the array, and 'i' and 'j' are the subscripts that uniquely identify each element in
'a'.

c. Initializing Two-Dimensional Arrays

Multidimensional arrays may be initialized by specifying bracketed values for each row.
Following is an array with 3 rows and each row has 4 columns.

int a[3][4] = { {0, 1, 2, 3} , /* initializers for row indexed by 0 */

{4, 5, 6, 7} , /* initializers for row indexed by 1 */

{8, 9, 10, 11} /* initializers for row indexed by 2 */ };

The nested braces, which indicate the intended row, are optional. The following initialization is
equivalent to the previous example −

int a[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11};

d. Accessing Two-Dimensional Array Elements

An element in a two-dimensional array is accessed by using the subscripts, i.e., row index and
column index of the array. For example −

int val = a[2][3];

~ 182 ~
The above statement will take the 4th element from the 3rd row of the array. You can verify it in
the above figure. Let us check the following program where we have used a nested loop to
handle a two-dimensional array

#include <stdio.h>

int main () {

/* an array with 5 rows and 2 columns*/

int a[5][2] = { {0,0}, {1,2}, {2,4}, {3,6},{4,8}};

int i, j;

/* output each array element's value */

for ( i = 0; i < 5; i++ ) {

for ( j = 0; j < 2; j++ ) {

printf("a[%d][%d] = %d\n", i,j, a[i][j] );

return 0;

When the above code is compiled and executed, it produces the following result

a[0][0]: 0

a[0][1]: 0

a[1][0]: 1

a[1][1]: 2

a[2][0]: 2

a[2][1]: 4

~ 183 ~
a[3][0]: 3

a[3][1]: 6

a[4][0]: 4

a[4][1]: 8

As explained above, you can have arrays with any number of dimensions, although it is likely
that most of the arrays you create will be of one or two dimensions.

Learning Outcome 2.10: Use functions in C Programming

2.10.1 Description of functions
The C program is nothing but a combination of one or more functions. Every C program starts
with user defined function main(). Each time when a new program is started, main() function
must be defined. The main() calls for another function to share the work.

a. Definition of a function

A function: is a self-contained block or sub-program of one or more statements that

performs a special task when called.

b. Types of functions

The C language supports two types of functions:

 Library functions
 User defined functions

A) Library functions

The library functions are pre-defined set of functions. Their task is limited. A user can not
understand the internal working of these functions. The user can only use the functions but can’t
change or modify them.

For example sqrt (81) gives result 9. Here, the user doesn’t need to worry about its source code
but the result should be provided by the function.

~ 184 ~
Example:

#include <stdio.h>
#include <conio.h>
#include <math.h>
main()
{
float x,y;
printf("\n Enter a number:");
scanf("%f",&x);
y=sqrt(x);
printf("\n square root %f is %f ",x,y);
}
Output:

The library functions are created by the designers of compilers. All C standard library functions
are defined inside the different header files saved with the extension .h. We need to include these
header files in our program to make use of the library functions defined in such header files.

For example, to use the library functions such as printf/scanf we need to include stdio.h in our
program which is a header file that contains all the library functions regarding standard
input/output.

The list of mostly used header files is given in the following table.

S Header Description
N file

1 stdio.h This is a standard input/output header file. It contains all the library functions
regarding standard input/output.

~ 185 ~
 2 conio.h This is a console input/output header file.

3 string.h It contains all string related library functions like gets(), puts(),etc.

4 stdlib.h This header file contains all the general library functions like malloc(),
calloc(), exit(), etc.

5 math.h This header file contains all the math operations related functions like sqrt(),
pow(), etc.

6 time.h This header file contains all the time-related functions.

7 ctype.h This header file contains all character handling functions.

8 stdarg.h Variable argument functions are defined in this header file.

9 signal.h All the signal handling functions are defined in this header file.

10 setjmp.h This file contains all the jump functions.

11 locale.h This file contains locale functions.

12 errno.h This file contains error handling functions.

13 assert.h This file contains diagnostics functions.

Math Library Functions

Math library functions perform common mathematical calculations

#include <math.h>

Format for calling functions

~ 186 ~
FunctionName( argument );

If multiple arguments, use comma-separated list

E.g: printf( "%.2f", sqrt( 900.0 ) );

Calls function sqrt, which returns the square root of its argument

All math functions return data type double e.g the sqrt function takes an argument of type double
and returns a result of type double

Arguments may be constants, variables, or expressions.

Forgetting to include the math header file when using math library functions can cause strange
results

Some C math library functions

acos() returns arc cosine of arg

asin() returns arc sine of arg

atan() returns arc tangent of arg

cos() returns cosine of arg

exp() returns natural logarithim e

fabs() returns absolute value of num

sqrt() returns square root of num

Example:

/* Testing the math library functions */

#include <stdio.h>

#include <math.h>

int main()

~ 187 ~
 printf( "sqrt(%.1f) = %.1f\n", 900.0, sqrt( 900.0 ) );

printf( "sqrt(%.1f) = %.1f\n", 9.0, sqrt( 9.0 ) );

printf( "exp(%.1f) = %f\n", 1.0, exp( 1.0 ) );

printf( "exp(%.1f) = %f\n", 2.0, exp( 2.0 ) );

printf( "log(%f) = %.1f\n", 2.718282, log( 2.718282 ) );

printf( "log(%f) = %.1f\n", 7.389056, log( 7.389056 ) );

printf( "log10(%.1f) = %.1f\n", 1.0, log10( 1.0 ) );

printf( "log10(%.1f) = %.1f\n", 10.0, log10( 10.0 ) );

printf( "log10(%.1f) = %.1f\n", 100.0, log10( 100.0 ) );

printf( "ceil(%.1f) = %.1f\n", 9.2, ceil( 9.2 ) );

printf( "ceil(%.1f) = %.1f\n", -9.8, ceil( -9.8 ) );

printf( "floor(%.1f) = %.1f\n", 9.2, floor( 9.2 ) );

printf( "pow(%.1f, %.1f) = %.1f\n", 2.0, 7.0,

pow( 2.0, 7.0 ) );

printf( "pow(%.1f, %.1f) = %.1f\n", 9.0, 0.5,

pow( 9.0, 0.5 ) );

printf( "sin(%.1f) = %.1f\n", 0.0, sin( 0.0 ) );

printf( "cos(%.1f) = %.1f\n", 0.0, cos( 0.0 ) );

printf( "tan(%.1f) = %.1f\n", 0.0, tan( 0.0 ) );

return 0;

Output:

~ 188 ~
 B) User defined functions

These are the functions defined by the user according to his/her requirement. The user can
modify the function according to the requirement. The user can only understand the internal
working of the function. The user has full scope to implement his/her own ideas in the function.
Thus the set of such user-defined functions can be useful to another programmer. One should
include the file in which user-defined functions are stored to call function in the program.

For example: square (9) is a user-defined function that gives the result 81. Here the user knows
the internal working of the square () function as its source code is visible, this is the major
difference between the two types of functions.

2.10.2 Using of functions syntaxes

a. Declaration of function and function prototypes

Function is declared as per format given below.

function_name (argument/parameter list)

argument declaration;

local variable declaration;

statement1;

~ 189 ~
statement2;

return(value);

b. Working of function:

main()

…………………..
…………………..
abc(x,y,z) Function Call
…………………..
………………….. Actual argument
}

abc(l,k,j) Function definition

……………………
…………………… Formal argument
return() ; Return value
}
A) Actual argument

The elements of calling functions are actual arguments. The variables ‘x’,’y’ and ‘z’ are actual
arguments.

B) Formal argument

The arguments of called function are formal arguments. The variables ‘l’, ’k’, ’j’ are formal
arguments.

C) Function name

~ 190 ~
A function must follow the same rule as we use for variable naming.

Example: sum (int a, int b);

Where sum () is a user defined function and ‘a’ and ‘b’ are integer variable arguments. The
function name must be ended by a semi-colon (;).

D) Argument/parameter list

The argument list means variable names enclosed within the parenthesis. They must be separated
by a comma (,). The formal arguments receive values from the actual argument.

E) Function call.

A compiler executes the function when a semi-colon (;) is followed by function name. A
function can be called simply using its name like other C statement, terminated by semicolon (;).

Example: Write a program to show how user-defined function is called, the function returns one
value.

#include <stdio.h>
#include <conio.h>
main()
{
int add(int a,int b),a=5,b=1,s;
s=add(a,b);
printf("\n Result in calling function");
printf("\n =========================");
printf("\n Sum=%d",s);
printf("\n In calling function;a=%d and b=%d",a,b);
}
add(int x,int y)
{
return (x+y);
}

~ 191 ~
Output:

2.10.3 Category of functions

A function, depending on whether arguments are present or not and whether a value is returned
or not, may belong to one of the following categories:

Category 1: Functions with no arguments and no return values.

Category 2: Functions with arguments and no return values.

Category 3: Functions with arguments and return values.

Category 4: Recursive Functions

Recursion is a technique to be used to call itself. In C, it is possible for the functions to call
themselves. A function is called recursive if a statement with in the body of a function calls the
same function itself.

Examples:

1. Functions with no arguments and no return values

#include<stdio.h>
#include<conio.h>
//Function Declaration
void printline();
void main()
{
printline(); // function declaration
printf(“This illustrate the use of C functions”);
printline();
getch();
}

~ 192 ~
void printline() //return type and function name
{
int i;
for (i=1; i<=40;i++)
printf(“- \n”);
}
2. Arguments but no Return values

#include<stdio.h>
#include<conio.h>
void swap(int,int);
void main()
{
int a,b;
printf(“Enter two number”);
scanf(“%d %d”,&a,&b);
swap(a,b);
getch();
}
void swap(int x, int y)
{
int sup ;
sup=x ;
x=y ;
y=sup ;
printf(“After swapping %d and %”, x, y ) ;
}

3. Arguments with Return Values

#include<stdio.h>

~ 193 ~
#include<conio.h>
{
int a,b,max;
printf (“Enter numbers: “) ;
scanf(“ %d %d “,&a,&b);
max = big(a,b);
printf(“\n The biggest number is:%d”,max);
getch();
}
int big(int x, int y)
{
if (x>y)
return x;
else
return y;
}
4. Recursion

#include<stdio.h>

#include<conio.h>

long int fact(int);

void main()

int n;

long int res;

printf Enter a positive number: ;

scanf %d ,&n);

res = fact(n);

~ 194 ~
printf The factorial is:%ld ,res);

getch();

}
long int fact (int n)

{
long int f;

if(n==1)

return 1;

else

f = n*fact(n-1);

return f;

}
2. 10.4 Important points about functions

 All C programs must contain at least one function. [The main() function serves this rule]
 A function can return only one value. Thus we should not specify two values to return.
 The return type in function declaration is optional. If no return type is specified it is
assumed to be an integer which is default.
 When a function is not returning any value, void type can be used as return type.
 Parameter list is optional.
 C provides a statement return
return expression
 Return statement is used in function definition to communicate the return value to the
calling function. Return statement indicates exit from the function and return to the point
from where the function was invoked.
 There may be any number of return statements in function definition, but only one return
statement will activate in a function call.
 The variable declarations within the function (between braces { }) are local to the
function and are not available outside the function.

~ 195 ~
  If there is no return statement, the program will return to the calling point after it reaches
the end of the function body (}).
 A function call can be used wherever a variable of same type is used (except the left side
of an assignment statement).
 There should be one to one correspondence between the actual and formal parameters in
type, order and number.
 C allows recursion. That is a function can call itself.
 A C function cannot be defined in another function.

2.10.5 Call by value and call by reference

There are two ways in which we can pass arguments to the function:

 Call by value
 Call by reference
a. Call by value

In this type, values of actual arguments are passed to the formal arguments and the operation is
done on formal arguments. Any change made on the formal argument doesn’t affect the actual
arguments because formal arguments are photocopy of actual arguments.

Hence, when function is called by value method, the contents of actual arguments are not being
affected. Changes made on formal arguments are local to the block of the called function. Once
the control returns back to the calling function, the changes made vanish.

A program in which arguments are passed to the function by call by value that returns “No
value”.

#include <stdio.h>
#include <conio.h>
main()
{
int x,y,change(int ,int);
printf("Enter two numbers x and y:");
scanf("%d %d",&x,&y);
change(x,y);
~ 196 ~
printf("\n In Main() X=%d Y=%d",x,y);
return 0;
}
change(int a,int b)
{
int k;
k=a;
a=b;
b=k;
printf("\n In Change() X=%d Y=%d",a,b);
}
Output:

B) Call by reference

In this type, instead of passing values, addresses (reference) are passed. Function operates on
address rather than values. Here, the formal arguments are pointers to the actual arguments. In
this type, formal arguments point to the actual argument; hence, changes made in the arguments
are permanent.

A program in which arguments are passed to the function by call by reference that returns “more
than one value”.

#include <stdio.h>
#include <conio.h>
main()
{
int x,y,add,sub,change(int *,int*, int*,int*);
clrscr();

~ 197 ~
printf("Enter two numbers x and y:");
scanf("%d %d",&x,&y);
change(&x,&y,&add,&sub);
printf("\n Addition :%d",add);
printf("\n Subtraction :%d",sub);
return 0;
}
change(int *a,int *b,int *c,int *d)
{
*c=*a+*b;
*d=*a-*b;
}
Output:

A program in which both call by value and call by reference have been used.

#include <stdio.h>
#include <conio.h>
main()
{
int k,m,other(int,int*);
clrscr();
printf("\n Address of k & m in main():%u %u",&k,&m);
other(k,&m);
return 0;
}
other(int k,int *m)
{

~ 198 ~
printf("\n Address of k & m in other():%u %u",&k,&m);
}
Output:

C) Difference between call by value and call by reference in c

call by value call by reference

This method copy original value into function This method copy address of arguments into
as arguments. function as arguments.

Changes made to the parameter affect the

Changes made to the parameter inside the
argument. Because address is used to access
function have no effect on the argument.
the actual argument.

Actual and formal arguments will be created Actual and formal arguments will be created
in different memory location in same memory location

2.10.6 Storage class

When we declare a variable, it is available only to specific part or block of the program, the
remaining block or other function cannot get access to the variable.

The area or block of the C program from where the variable can be accessed is known as the
scope of variable.

The area or scope of the variable depends on its storage class. ie where and how the variable is
declared.

The storage class of a variable tells the compiler:

~ 199 ~
  Storage area of a variable
 Initial value of a variable if not initialized
 Scope of a variable
 Life of a variable ie how long the variable would be active in the program.

C has 4 storage classes:

 Automatic variables known as local variables

 External variables known as global variables
 Static variables
 Register variables
a. Automatic variables or local variables

Auto variables are defined inside the function. A variable declared inside the function without
storage class name by default is an auto variable.

The scope of a variable is local to the block in which they are defined.

Once the execution of the function takes place and return turns off the function, the contents and
existence of the auto or local variables vanish.

Auto variables are safety i.e they can not be accessed directly by other functions.

Example:

#include <stdio.h>
#include <conio.h>
main()
{
int add(int a,int b),a=5,b=1,s;
s=add(a,b);
printf("\n Result in calling function");
printf("\n =========================");
printf("\n Sum=%d",s);
printf("\n In calling function;a=%d and b=%d",a,b);

~ 200 ~
}
add(int x,int y)
{
int a=20,b=10;
printf("\n In Called function;a=%d and b=%d",a,b);
return (x+y);
}

Output:

b. External variable or global variable

The variable is available to all functions. The variable is called external or global variable and is
declared outside the function body.

In case both external and auto variables are declared with the same name, the first priority is
given to auto variables and the compiler doesn’t allocate memory for these variables.

Example:

#include <stdio.h>
#include <conio.h>
int a=5,b=1;
main()
{
int add(int a,int b);
int subtra(int a,int b);
int s,t;

~ 201 ~
s=add(a,b);
t=subtra(a,b);
printf("\n Result in calling function");
printf("\n =========================");
printf("\n Sum=%d \n Subtraction=%d",s,t);
printf("\n In calling function;a=%d and b=%d",a,b);
}
add(int x,int y)
{
printf("\n In ADDITION Called function;a=%d and b=%d",a,b);
return (x+y);
}
subtra(int x,int y)
{
int a=20,b=10;
printf("\n In SUBTRACTION Called function;a=%d and b=%d",a,b);
return (x-y);
}
Output:

c. Static variable

The static variable may be of an internal or external type, depending upon where it is declared. If
it is declared outside the function of the body it will be static global. In case, it is declared in the
body or block it will be auto variable. When a variable is declared as static its garbage value is

~ 202 ~
removed and initialized to NULL value. The contents stored in these variables remain constant
throughout the program execution.

A static variable is initialized only once; it is never reinitialized. The value of static variable
persists at each call and the last change made in the value of static variable remains throughout
the program execution.

Example:

#include <stdio.h>
#include <conio.h>
main()
{
int x;
static int y;
printf("x=%d & Y=%d",x,y);
}
Output:

d. Register variables

Variables are kept in the CPU registers instead of memory.

Keyword register tells the compiler that the variable list followed by it, is kept on CPU registers
since register access is faster than the memory access.

If the CPU fails to keep the variables in the CPU registers, in that case the variables are assumed
as auto and stored in the memory. CPU registers are limited in numbers; hence, we can not
declare more variables with register variables. However, compiler automatically converts register
variables to non-variables once the limit is reached. The user can not determine the success or
failure of register variables.

We cannot use register class for all types of variables. The CPU registers in microprocessor are
16 bit registers. The data type float and double need space of more than 16 bits. If we define

~ 203 ~
variable of these data type with register class, no errors will be shown. The compiler treats them
as variable of auto class.

Example:

#include <stdio.h>
#include <conio.h>
main()
{
register int x;
for(x=0;x<=5;x++)
printf("%2d",x);
}
Output:

2.10.6 Inline function in C

a. What is Inline function?

The inline function can be substituted at the place where the function call is happening. Function
substitution is always compiler choice.

In an inline function, a function call is replaced by the actual program code.

Most of the Inline functions are used for small computations. They are not suitable for large
computing.

An inline function is similar to a normal function. The only difference is that we place a keyword
inline before the function name.

b. Syntax

Inline functions are created with the following syntax:

inline function_name (){

~ 204 ~
 //function definition

c. Example

Following is the C program for inline functions:

#include<stdio.h>

inline int mul(int a, int b) //inline function declaration

return(a*b);

int main(){

int c;

c=mul(2,3); //inline function call

printf("Multiplication:%d\n",c);

return 0;

Output:

When the above program is executed, it produces the following result:

Another Example:

#include <stdio.h>
// Inline function in C
static inline int foo()
{
return 2;
~ 205 ~
}
// Driver code
int main()
{
int ret;
// inline function call
ret = foo();
printf("Output is: %d\n", ret);
return 0;}

Learning Outcome 2.11: Manage memory using pointers

2.11.1 Memory management in C programming introduction
Almost all computer languages can handle system memory. All the variables used in your
program occupies a precise memory space along with the program itself, which needs some
memory for storing itself (i.e., its own program). Therefore, managing memory utmost care is
one of the major tasks a programmer must keep in mind while writing codes.

When a variable gets assigned in a memory in one program, that memory location cannot be
used by another variable or another program. So, C language gives us a technique of allocating
memory to different variables and programs.

There are two types used for allocating memory. These are: static memory allocations and
dynamic memory allocations.

a. Static memory allocations

In the static memory allocation technique, allocation of memory is done at compilation time, and
it stays the same throughout the entire run of your program. Neither any changes will be there in
the amount of memory nor any change in the location of memory.

b. Dynamic memory allocations

~ 206 ~
In dynamic memory allocation technique, allocation of memory is done at the time of running
the program, and it also has the facility to increase/decrease the memory quantity allocated and
can also release or free the memory as and when not required or used. Reallocation of memory
can also be done when required. So, it is more advantageous, and memory can be managed
efficiently.

2.11.2 Description of pointers in C

Variables are used in C to hold data values during the execution of a program. Every variable
when declared occupies certain memory locations.

In C, it is possible to access and display the address of the memory location variable using &
operator with variable name. The pointer variable is needed to store the memory address of any
variable. The pointer is denoted by (*) asterisk symbol.

a. Definition of a pointer

A pointer is a memory variable that stores a memory address. Pointer can have any name that is
legal for other variable and it is declared in the same fashion like other variables but it is always
denoted by ‘*’ operator.

b. Features of pointers

Pointers save the memory space

Execution time with pointer is faster because data is manipulated with the address i.e direct
access to memory location.

The memory is accessed efficiently with pointers. The pointer assigns the memory space and it
also releases. Dynamically memory is allocated.

Pointers are used with data structures. They are useful for representing two-dimensional and
multi-dimensional arrays.

c. Usage of pointer

There are many applications of pointers in c language.

A) Dynamic memory allocation

~ 207 ~
In c language, we can dynamically allocate memory using malloc() and calloc() functions where
the pointer is used.

B) Arrays, Functions, and Structures

Pointers in c language are widely used in arrays, functions, and structures. It reduces the code
and improves the performance.

2.11.3 Using Operators that are used with Pointers

a. Pointer declaration

In C, every variable must be declared for its type. Since pointer variables contain addresses that
belong to a separate data type, they must be declared as pointers before we use them.

The declaration of a pointer variable takes the following form:

datatype *pt_name;

This tells the compiler three things about the variable pt_name.

The asterisk (*) tells the variablept_nameis a pointer variable.

pt_nameneeds a memory location.

pt_namepoints to a variable of typedatatype.

For example:

int *p;

declares the variable p as a pointervariable that points to an integer data type.

Remember that the type int refers to the data type of the variable being pointed to by p and not
the type of the value of the pointer.

Similarly, the statement

float *x;

declares x as a pointer to a floating point variable.

b. Initializing pointers

~ 208 ~
Once a pointer variable has been declared, it can be made to point to a variable using an
assignment statement such as

p = &quantity;

which causes p to point to quantity. That is, p now contains the address of quantity.

This is known as pointer initialization.

Before a pointer is initialized, it should not be used.

A pointer variable can be initialized in its declaration itself. For example,

int x, *p=&x;

is perfectly valid. It declares x as an integer variable and p as a pointer variable and then

initializes p to the address of x. Note carefully that this is an initialization of p, not *p. And

also remember that the targetvariable x is declared first. Thestatement

int *p=&x, x;

is not valid.

c. Accessing variable through its pointer

Once a pointer has been assigned the address of a variable, the question remains as to how to
access the value of the variable using the pointer. This is done by using another unary operator *
(asterisk), usually known as the indirection operator.

Consider the following statements:

int quantity, *p, n;

quantity = 179;

p = &quantity;

n = *p;

~ 209 ~
The first line declares quantity and n as integer variables and p as a pointer variable pointing to
an integer.

The second line assigns the value 179 to quantity.

The third line assigns the address of quantity to the pointer variable p.

The fourth line contains the indirection operator *.

When the operator * is placed before a pointer variable in an expression, the pointer returns the
value of the variable of which the pointer value is the address.

In this case, *p returns the value of the variable quantity, because p is the address of quantity.
The * can be remembered as value of address. Thus the value of n would be 179.

Example:

int *x;

float *f;

char *y;

In the first statement ‘x’ is an integer pointer and it tells to the compiler that it holds the address
of any integer variable. In the same way ‘f’ is a float pointer that stores the address of any
character variable.

The indirection operator (*) indicates that the value at the memory location stored in the pointer
is to be accessed rather than the address itself.

The’ &’ is the address operator and it represents the address of variable. The %u is used with
printf() function for printing the address of a variable. The address of any variable is a whole
number. The operator ‘&’ immediately preceding the variable returns the address of a variable.

A program to display the value of variable and its location using pointer

#include <stdio.h>

#include <conio.h>

~ 210 ~
main()

int v,*p;

printf("\n Enter a number:");

scanf("%d",&v);

p=&v;

printf("\n The address of v=%u",p);

printf("\n The value of v=%d",*p);

printf("\n Address of p=%u",&p);

getch();

Output:

Explanation

In the above program ‘v’ is an integer variable and its value is 10. The variable ‘p’ is declared as
a pointer variable.

The statement p=&v assigns address of ‘v’ to ‘p’ i.e ‘p’ is the pointer to variable ‘v’. To access
the address and value of ‘v’ pointer ‘p’ can be used. The value of ‘p’ is nothing but the address
of the variable ‘v’.

To display the value stored at that location *p is used.

The pointer variables also have an address and are displayed using ‘&’ operator. The statement
used is (“\n Address of p=%u”,&p);

~ 211 ~
A program to print value of variable using different operator notations.

#include <stdio.h>

#include <conio.h>

main()

clrscr();

int v=10,*p;

p=&v;

printf("v=%d v=%d v=%d",v,*(&v),*p);

getch();

Output:

2.11.4 Application of pointers in C

a. Arithmetic operations with pointers

Arithmetic operations on pointer variables are also possible. Increase, decrease, prefix & postfix
operations can be performed with the help of pointers.

Data Type Initial Operation Address after operations Required

Bytes
Address

int i=10 9630 ++ -- 9632 9628 2

char c=’Z’ 9625 ++ -- 9626 9624 1

float f=67.5 9616 ++ -- 9620 9612 4

~ 212 ~
A program to show the effect of increment on pointers variables. Display the memory locations
of integer, character, and floating point numbers before and after increment of pointers.

#include <stdio.h>

#include <conio.h>

main()

int x, *x1;

char y, *y1;

float z, *z1;

printf("\n Enter integer, character and float values:");

scanf("%d %c %f",&x,&y,&z);

x1=&x;

y1=&y;

z1=&z;

printf("\n Address of x= %u",x1);

printf("\n Address of y= %u",y1);

printf("\n Address of z= %u",z1);

x1++;

y1++;

z1++;

printf("\n After increment on pointers");

printf("\n=============================");

~ 213 ~
printf("\n Now address of x=%u",x1);

printf("\n Now address of y=%u",y1);

printf("\n Now address of z=%u",z1);

printf("\n Size of");

printf("\n=========");

printf("\n Integer:%d",sizeof(*x1));

printf("\n Character:%d",sizeof(*y1));

printf("\n Float:%d",sizeof(*z1));}

Output:

b. Double Pointer (Pointer to Pointer)

As we know that, a pointer is used to store the address of a variable in C. Pointer reduces the
access time of a variable. However, In C, we can also define a pointer to store the address of
another pointer. Such pointer is known as a double pointer (pointer to pointer). The first pointer
is used to store the address of a variable whereas the second pointer is used to store the address
of the first pointer. Let's understand it by the diagram given below.

~ 214 ~
The syntax of declaring a double pointer is given below.

int **p; // pointer to a pointer which is pointing to an integer.

Consider the following example.

#include<stdio.h>

void main ()

int a = 10;

int *p;

int **pp;

p = &a; // pointer p is pointing to the address of a

pp = &p; // pointer pp is a double pointer pointing to the address of pointer p

printf("address of a: %x\n",p); // Address of a will be printed

printf("address of p: %x\n",pp); // Address of p will be printed

printf("value stored at p: %d\n",*p); // value stoted at the address contained by p i.e. 10 will be pr
inted

printf("value stored at pp: %d\n",**pp); // value stored at the address contained by the pointer sto
yred at pp

Output:

address of a: d26a8734

~ 215 ~
address of p: d26a8738

value stored at p: 10

value stored at pp: 10

C double pointer example

Let's see an example where one pointer points to the address of another pointer.

As you can see in the above figure, p2 contains the address of p (fff2), and p contains the address
of number variable (fff4).

#include<stdio.h>

int main(){

int number=50;

int *p;//pointer to int

int **p2;//pointer to pointer

p=&number;//stores the address of number variable

p2=&p;

printf("Address of number variable is %x \n",&number);

printf("Address of p variable is %x \n",p);

printf("Value of *p variable is %d \n",*p);

printf("Address of p2 variable is %x \n",p2);

~ 216 ~
printf("Value of **p2 variable is %d \n",*p);

return 0;

Output:

Address of number variable is fff4

Address of p variable is fff4

Value of *p variable is 50

Address of p2 variable is fff2

Value of **p variable is 50

c. Passing pointer to a function in C

Just like any other argument, pointers can also be passed to a function as an argument. Let’s take
an example to understand how this is done.

Example: Passing Pointer to a Function in C Programming

In this example, we are passing a pointer to a function. When we pass a pointer as an argument
instead of a variable then the address of the variable is passed instead of the value. So any
change made by the function using the pointer is permanently made at the address of passed
variable. This technique is known as call by reference in C.

Try this same program without pointer, you would find that the bonus amount will not reflect in
the salary, this is because the change made by the function would be done to the local variables
of the function. When we use pointers, the value is changed at the address of variable

#include <stdio.h>

void salaryhike(int *var, int b)

~ 217 ~
 *var = *var+b;

int main()

int salary=0, bonus=0;

printf("Enter the employee current salary:");

scanf("%d", &salary);

printf("Enter bonus:");

scanf("%d", &bonus);

salaryhike(&salary, bonus);

printf("Final salary: %d", salary);

return 0;

Output:

Enter the employee current salary:10000

Enter bonus:2000

Final salary: 12000

d. Pointers and arrays

When an array is declared, the compiler allocates a base address and sufficient amount of storage
to contain all the elements of the array in contiguous memory locations.

The base address is the location of the first element (index 0) of the array. The compiler also
defines the array name as a constant pointer to the first element.

~ 218 ~
If we declare p as an integer pointer, then we can make the pointer p to point to the array x by the
following assignment:

p = x;

This is equivalent to

p = &x[0];

When handling arrays, instead of using array indexing, we can use pointers to access array
elements.

Note that *(p+3) gives the value of x[3]. The pointer accessing method ismuch faster than array
indexing.

Array name by itself is an address or pointer. It points to the address of the first element (0th
element of an array). The elements of the array together with their addresses can be displayed by
using array name itself. Array elements are always stored in contiguous memory locations.

Write a program to display array element with their addresses using array name as pointer

#include <stdio.h>

#include <conio.h>

main()

intn,i,x[5];

printf("\n Enter how many number:");

scanf("%d",&n);

for(i=0;i<n;i++)

scanf("%d",&x[i]);

printf("\n Element No. Element Address");

~ 219 ~
for(i=0;i<n;i++)

printf("\n [%d] %4d %3u",i,*(x+i),x+i);

Output:

2.11.5 Use of Static Memory Allocation

Static Memory Allocation: Static Memory is allocated for declared variables by the compiler.
The address can be found using the address of operator and can be assigned to a pointer. The
memory is allocated during compile time.

Dynamic Memory Allocation: Memory allocation done at the time of execution (run time) is
known as dynamic memory allocation. Functions calloc() and malloc() support allocating
dynamic memory. In the Dynamic allocation of memory space is allocated by using these
functions when the value is returned by functions and assigned to pointer variables.

Difference between Static and Dynamic Memory Allocation in C:

S.N Static Memory Allocation Dynamic Memory Allocation

o

1 In the static memory allocation, In the Dynamic memory allocation, variables

variables get allocated permanently, get allocated only if your program unit gets
till the program executes or function active.
call finishes.

2 Static Memory Allocation is done Dynamic Memory Allocation is done during

~ 220 ~
 before program execution. program execution.

3 It uses stack for managing the static It uses heap for managing the dynamic
allocation of memory allocation of memory

4 It is less efficient It is more efficient

5 In Static Memory Allocation, there is In Dynamic Memory Allocation, there is

no memory re-usability memory re-usability and memory can be
freed when not required

6 In static memory allocation, once the In dynamic memory allocation, when

memory is allocated, the memory size memory is allocated the memory size can be
cannot change. changed.

7 In this memory allocation scheme, we This allows reusing the memory. The user
cannot reuse the unused memory. can allocate more memory when required.
Also, the user can release the memory when
the user needs it.

8 In this memory allocation scheme, In this memory allocation scheme, execution

execution is faster than dynamic is slower than static memory allocation.
memory allocation.

9 In this memory is allocated at compile In this memory is allocated at run time.

time.

10 In this allocated memory remains from In this allocated memory can be released at
start to end of the program. any time during the program.

11 Example: This static memory Example: This dynamic memory allocation is

allocation is generally used for array. generally used for linked list.

Stack memory is allocated during compilation time execution. This is known as static memory
allocation.

Whereas, heap memory is allocated at run-time compilation. This is known as dynamic memory
allocation.

~ 221 ~
2.11.6 Use of Dynamic Memory Allocation
a. Overview

Since C is a structured language, it has some fixed rules for programming. One of them includes
changing the size of an array. An array is a collection of items stored at contiguous memory
locations.

As it can be seen that the length (size) of the array above made is 9. But what if there is a
requirement to change this length (size). For Example,

If there is a situation where only 5 elements are needed to be entered in this array. In this case,
the remaining 4 indices are just wasting memory in this array. So there is a requirement to lessen
the length (size) of the array from 9 to 5.

Take another situation. In this, there is an array of 9 elements with all 9 indices filled. But there
is a need to enter 3 more elements in this array. In this case, 3 indices more are required. So the
length (size) of the array needs to be changed from 9 to 12.

This procedure is referred to as Dynamic Memory Allocation in C.

Therefore, C Dynamic Memory Allocation can be defined as a procedure in which the size of a
data structure (like Array) is changed during the runtime.
C provides some functions to achieve these tasks. There are 4 library functions provided by C
defined under <stdlib.h> header file to facilitate dynamic memory allocation in C programming.
They are:

malloc()

calloc()

~ 222 ~
realloc()

free()

Then, the concept of dynamic memory allocation in c language enables the C programmer to
allocate memory at runtime. Dynamic memory allocation in c language is possible by 4
functions of stdlib.h header file.

Now let's have a quick look at the methods used for dynamic memory allocation.

malloc() Allocates single block of requested memory.

calloc() Allocates multiple block of requested memory.

realloc() Reallocates the memory occupied by malloc() or calloc() functions.

free() Frees the dynamically allocated memory.

b. malloc() function in C

The “malloc” or “memory allocation” method in C is used to dynamically allocate a single large
block of memory with the specified size. It returns a pointer of type void which can be cast into a
pointer of any form. It doesn’t Initialize memory at execution time so that it has initializes each
block with the default garbage value initially.

The malloc() function allocates single block of requested memory.

It doesn't initialize memory at execution time, so it has garbage value initially.

The syntax of malloc() function is given below:

ptr=(cast-type*)malloc(byte-size)

For Example:

ptr = (int*) malloc(100 * sizeof(int));

Since the size of int is 4 bytes, this statement will allocate 400 bytes of memory. And,
~ 223 ~
the pointer ptr holds the address of the first byte in the allocated memory.

If space is insufficient, allocation fails and returns a NULL pointer.

Let's see the example of malloc() function.

Example 1:

#include <stdio.h>

#include <stdlib.h>

int main()

// This pointer will hold the

// base address of the block created

int* ptr;

int n, i;

// Get the number of elements for the array

printf("Enter number of elements:");

scanf("%d",&n);

printf("Entered number of elements: %d\n", n);

~ 224 ~
 // Dynamically allocate memory using malloc()

ptr = (int*)malloc(n * sizeof(int));

// Check if the memory has been successfully

// allocated by malloc or not

if (ptr == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using malloc.\n");

// Get the elements of the array

for (i = 0; i < n; ++i) {

ptr[i] = i + 1;

// Print the elements of the array

printf("The elements of the array are: ");

for (i = 0; i < n; ++i) {

printf("%d, ", ptr[i]);

return 0;

~ 225 ~
Example 2:

#include<stdio.h>

#include<stdlib.h>

int main(){

int n,i,*ptr,sum=0;

printf("Enter number of elements: ");

scanf("%d",&n);

ptr=(int*)malloc(n*sizeof(int)); //memory allocated using malloc

if(ptr==NULL)

printf("Sorry! unable to allocate memory");

exit(0);

printf("Enter elements of array:\n");

for(i=0;i<n;++i)

scanf("%d",ptr+i);

sum+=*(ptr+i);

~ 226 ~
printf("Sum=%d",sum);

free(ptr);

return 0;

Output:

c. calloc () function in C

“calloc” or “contiguous allocation” method in C is used to dynamically allocate the specified

number of blocks of memory of the specified type. it is very much similar to malloc() but has
two different points and these are:

It initializes each block with a default value ‘0’.

It has two parameters or arguments as compare to malloc().

If space is insufficient, allocation fails and returns a NULL pointer.

Syntax:

ptr = (cast-type*)calloc(n, element-size);

here, n is the no. of elements and element-size is the size of each element.

For Example:

ptr = (float*) calloc(25, sizeof(float));

This statement allocates contiguous space in memory for 25 elements each with the size of the

float.

~ 227 ~
Example 1:

#include <stdio.h>

#include <stdlib.h>

int main()

{ // This pointer will hold the

// base address of the block created

int* ptr;

int n, i;

// Get the number of elements for the array

n = 5;

printf("Enter number of elements: %d\n", n);

// Dynamically allocate memory using calloc()

ptr = (int*)calloc(n, sizeof(int));

// Check if the memory has been successfully

// allocated by calloc or not

~ 228 ~
 if (ptr == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using calloc.\n");

// Get the elements of the array

for (i = 0; i < n; ++i) {

ptr[i] = i + 1;

// Print the elements of the array

printf("The elements of the array are: ");

for (i = 0; i < n; ++i) {

printf("%d, ", ptr[i]);

return 0;

~ 229 ~
Example 2:

#include<stdio.h>

#include<stdlib.h>

int main(){

int n,i,*ptr,sum=0;

printf("Enter number of elements: ");

scanf("%d",&n);

ptr=(int*)calloc(n,sizeof(int)); //memory allocated using calloc

if(ptr==NULL)

printf("Sorry! unable to allocate memory");

exit(0);

printf("Enter elements of array:\n");

for(i=0;i<n;++i)

scanf("%d",ptr+i);

sum+=*(ptr+i);

}
~ 230 ~
printf("Sum=%d",sum);

free(ptr);

return 0;

Output:

d. C free () method

“free” method in C is used to dynamically de-allocate the memory. The memory allocated using
functions malloc() and calloc() is not de-allocated on their own. Hence the free () method is used,
whenever the dynamic memory allocation takes place. It helps to reduce wastage of memory by
freeing it.

Syntax:

free(ptr);

~ 231 ~
Example:

#include <stdio.h>

#include <stdlib.h>

int main()

{ // This pointer will hold the

// base address of the block created

int *ptr, *ptr1;

int n, i;

// Get the number of elements for the array

n = 5;

printf("Enter number of elements: %d\n", n);

// Dynamically allocate memory using malloc()

ptr = (int*)malloc(n * sizeof(int));

~ 232 ~
 // Dynamically allocate memory using calloc()

ptr1 = (int*)calloc(n, sizeof(int));

// Check if the memory has been successfully

// allocated by malloc or not

if (ptr == NULL || ptr1 == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using malloc.\n");

// Free the memory

free(ptr);

printf("Malloc Memory successfully freed.\n");

// Memory has been successfully allocated

printf("\nMemory successfully allocated using calloc.\n");

// Free the memory

free(ptr1);

printf("Calloc Memory successfully freed.\n");

return 0;

~ 233 ~
 e. C realloc() method

“realloc” or “re-allocation” method in C is used to dynamically change the memory allocation of

a previously allocated memory. In other words, if the memory previously allocated with the help
of malloc or calloc is insufficient, realloc can be used to dynamically re-allocate memory. re-
allocation of memory maintains the already present value and new

blocks will be initialized with the default garbage value.

If memory is not sufficient for malloc() or calloc(), you can reallocate the memory by realloc()
function. In short, it changes the memory size.

Syntax:

ptr = realloc(ptr, newSize);

where ptr is reallocated with new size 'newSize'.

~ 234 ~
If space is insufficient, allocation fails and returns a NULL pointer.

Example:

#include <stdio.h>

#include <stdlib.h>

int main()

// This pointer will hold the

// base address of the block created

int* ptr;

int n, i;

~ 235 ~
// Get the number of elements for the array

n = 5;

printf("Enter number of elements: %d\n", n);

// Dynamically allocate memory using calloc()

ptr = (int*)calloc(n, sizeof(int));

// Check if the memory has been successfully

// allocated by malloc or not

if (ptr == NULL) {

printf("Memory not allocated.\n");

exit(0);

else {

// Memory has been successfully allocated

printf("Memory successfully allocated using calloc.\n");

// Get the elements of the array

for (i = 0; i < n; ++i) {

ptr[i] = i + 1;

~ 236 ~
// Print the elements of the array

printf("The elements of the array are: ");

for (i = 0; i < n; ++i) {

printf("%d, ", ptr[i]);

// Get the new size for the array

n = 10;

printf("\n\nEnter the new size of the array: %d\n", n);

// Dynamically re-allocate memory using realloc()

ptr = realloc(ptr, n * sizeof(int));

// Memory has been successfully allocated

printf("Memory successfully re-allocated using realloc.\n");

// Get the new elements of the array

for (i = 5; i < n; ++i) {

ptr[i] = i + 1;

// Print the elements of the array

~ 237 ~
 printf("The elements of the array are: ");

for (i = 0; i < n; ++i) {

printf("%d, ", ptr[i]);

free(ptr);

return 0;

One another example for realloc() method is:

#include <stdio.h>

#include <stdlib.h>

int main()

{
~ 238 ~
int index = 0, i = 0, n,

*marks; // this marks pointer hold the base address

// of the block created

int ans;

marks = (int*)malloc(sizeof(

int)); // dynamically allocate memory using malloc

// check if the memory is successfully allocated by

// malloc or not?

if (marks == NULL) {

printf("memory cannot be allocated");

else {

// memory has successfully allocated

printf("Memory has been successfully allocated by "

"using malloc\n");

printf("\n marks = %pc\n",

marks); // print the base or beginning

// address of allocated memory

do {

printf("\n Enter Marks\n");

scanf("%d", &marks[index]); // Get the marks

printf("would you like to add more(1/0): ");

scanf("%d", &ans);

~ 239 ~
if (ans == 1) {

index++;

marks = (int*)realloc(

marks,

(index + 1)

* sizeof(

int)); // Dynamically reallocate

// memory by using realloc

// check if the memory is successfully

// allocated by realloc or not?

if (marks == NULL) {

printf("memory cannot be allocated");

else {

printf("Memory has been successfully "

"reallocated using realloc:\n");

printf(

"\n base address of marks are:%pc",

marks); ////print the base or

///beginning address of

///allocated memory

~ 240 ~
 }

} while (ans == 1);

// print the marks of the students

for (i = 0; i <= index; i++) {

printf("marks of students %d are: %d\n ", i,

marks[i]);

free(marks);

return 0;

~ 241 ~
Learning Outcome 2.12: Use structure
2.12.1 Description of structure in C
A variable stores a single value of a data type. Arrays can store many values of similar data type.
In real life, different data types are required for example to maintain employees’ information
such as name, age, salary and so on, all these data types cannot be expressed in a single array.

a. Defining a structure:

Is a collection of one or more variables of different data types, grouped together under a single
name. By using structures, we can make a group of variables, arrays, pointers.

b. Advantages of structures
 To copy elements of one array to another array of same data type, elements are copied
one by one whereas in structure, it is possible to copy the contents of all structure
elements.
 Nesting of structures is possible.
 It is also possible to pass structure elements to a function.
 It is also possible to create structure pointers.

c. Declaration and initialization of structures

struct struct_type

type variable1;

type variable2;

};

Structure declaration starts with struct keyword, struct-type is known as tag or name of
structure. The struct declaration is enclosed within a pair of curly braces. Variable1 and variable2
are variables known as structure members.

The closing brace in the structure type declaration must be followed by a semicolon.

~ 242 ~
It is important to understand that a structure type declaration does not tell the compiler to reserve
any space in memory. All a structure declaration does is, it defines the form of the structure.

Usually structure type declaration appears at the top of the source code file, before any variables
or functions are defined.

d. Accessing Structure Members

The period (.) sign is used to access structure members.

Example of a structure:

struct book

char book[30];

int pages;

float price;

};

e. Initialization:

struct book bk1={”C++”,300,850};

Example 1: A program to display the details of a book by initialization using a structure.

#include <stdio.h>

#include <conio.h>

main()

struct book1

~ 243 ~
char book[30];

int pages;

float price;

};

struct book1 bk1={"C++",300,278.5};

printf("\n Book name: %s",[Link]);

printf("\n No of pages:%d",[Link]);

printf("\n Book price: %f",[Link]);

Output:

Write a program to display the details of a book by entering the name of a book, the number of
pages and the price.

#include <stdio.h>

#include <conio.h>

main()

struct book1

char book[30];

int pages;

float price;

~ 244 ~
};

struct book1 bk1,bk2;

printf("\n Enter book name:");

scanf("%s",&[Link]);

printf("\n Enter No of pages:");

scanf("%d",&[Link]);

printf("\n Enter book price:");

scanf("%f",&[Link]);

printf("\n Book name: %s",[Link]);

printf("\n No of pages:%d",[Link]);

printf("\n Book price: %f",[Link]);

Output:

2.12.2 Use of Array Structures in C

C enables us to declare an array of structures by using which, we can avoid declaring the
different structure variables; instead we can make a collection containing all the structures that
store the information of different entities.

a. Definition

~ 245 ~
An array of structures in C can be defined as the collection of multiple structures variables where
each variable contains information about different entities. The array of structures in C are used
to store information about multiple entities of different data types. The array of structures is also
known as the collection of structures.

b. Difference Between Array and Structure

Array Structure

Array is collection of homogeneous Structure is the collection of

1
data. heterogeneous data.

Structure elements are access using .

2 Array data are access using index.
Operator.

3 Array allocates static memory. Structures allocate dynamic memory.

Array element access takes less time Structure elements takes more time than
4
than structures. Array.

Example:

#include <stdio.h>

#include<conio.h>

#include <string.h>

struct student

int id;

char name[30];

float percentage;

~ 246 ~
};

main()

int i;

struct student record[3];

// 1st student's record

record[0].id=1;

strcpy(record[0].name, “Gaju");

record[0].percentage = 86.5;

// 2nd student's record

record[1].id=2;

strcpy(record[1].name, “Cyuzuzo");

record[1].percentage = 90.5;

// 3rd student's record

record[2].id=3;

strcpy(record[2].name, “UWITONZE");

record[2].percentage = 81.5;

for(i=0; i<3; i++)

printf(" Records of STUDENT : %d \n", i+1);

printf(" Id is: %d \n", record[i].id);

printf(" Name is: %s \n", record[i].name);

printf(" Percentage is: %f\n\n",record[i].percentage); }

~ 247 ~
 getch();

2.12.3 Nested Structure in C

C provides us the feature of nesting one structure within another structure by using which,
complex data types are created. For example, we may need to store the address of an entity
employee in a structure. The attribute address may also have the subparts as city, pin code and
phone. Hence, to store the address of the employee, we need to store the address of the employee
into a separate structure and nest the structure address into the structure employee. Consider the
following program.

#include<stdio.h>

struct address

char city[20];

int pin;

char phone[14];

};

struct employee

char name[20];

struct address add;

};

void main ()

struct employee emp;

~ 248 ~
printf("Enter employee information?\n");

scanf("%s %s %d %s",[Link],[Link], &[Link], [Link]);

printf("Printing the employee information....\n");

printf("name: %s\nCity: %s\nPincode: %d\nPhone: %s",[Link],[Link],[Link],em

[Link]);

Output:

Enter employee information?

Arun

Delhi

110001

1234567890

Printing the employee information....

name: Arun

City: Delhi

Pincode: 110001

Phone: 1234567890

The structure can be nested in the following ways.

a. By separate structure
b. By Embedded structure
a. By Separate structure

Here, we create two structures, but the dependent structure should be used inside the main
structure as a member. Consider the following example.

~ 249 ~
struct Date

int dd;

int mm;

int yyyy;

};

struct Employee

int id;

char name[20];

struct Date doj;

}emp1;

As you can see, doj (date of joining) is the variable of type Date. Here doj is used as a member in
Employee structure. In this way, we can use Date structure in many structures.

b. By Embedded structure

The embedded structure enables us to declare the structure inside the structure. Hence, it requires
less line of codes but it cannot be used in multiple data structures. Consider the following
example.

struct Employee

int id;

char name[20];

struct Date

~ 250 ~
{

int dd;

int mm;

int yyyy;

}doj;

}emp1;

c. Accessing Nested Structure

We can access the member of the nested structure by Outer_Structure.Nested_Structure.member

as given below:

[Link]

[Link]

[Link]

Example:

#include <stdio.h>

#include <string.h>

struct Employee

int id;

char name[20];

struct Date

int dd;

int mm;

~ 251 ~
int yyyy;

}doj;

}e1;

int main( )

//storing employee information

[Link]=101;

strcpy([Link], "Sonoo Jaiswal");//copying string into char array

[Link]=10;

[Link]=11;

[Link]=2014;

//printing first employee information

printf( "employee id : %d\n", [Link]);

printf( "employee name : %s\n", [Link]);

printf( "employee date of joining (dd/mm/yyyy) : %d/%d/%d\n", [Link],[Link],[Link]

y);

return 0;

Output:

employee id : 101

employee name : Sonoo Jaiswal

employee date of joining (dd/mm/yyyy) : 10/11/2014

~ 252 ~
2.12.4 Passing Structure to Function
Just like other variables, a structure can also be passed to a function. We may pass the structure
members into the function or pass the structure variable at once. Consider the following example
to pass the structure variable employee to a function display () which is used to display the
details of an employee.

#include<stdio.h>

struct address

char city[20];

int pin;

char phone[14];

};

struct employee

char name[20];

struct address add;

};

void display(struct employee);

void main ()

struct employee emp;

printf("Enter employee information?\n");

scanf("%s %s %d %s",&[Link],&[Link], &[Link], &[Link]);

~ 253 ~
display(emp);

void display(struct employee emp)

printf("Printing the details....\n");

printf("%s %s %d %s",[Link],[Link],[Link],[Link]);

Output:

2.12.5 Pointers to Structures in C

Pointer to structure holds the address of the entire structure.

It is used to create complex data structures such as linked lists, trees, graphs and so on.

The members of the structure can be accessed using a special operator called as an arrow
operator ( -> )

a. Difference between Structure and Pointer in C

Structure in C refer to a collection of various data types for example you create a structure
named "Student" which contains his name, roll no, DOB etc. Name is string, Roll no is int.

While pointer refer to address in C & symbol is used to point some particular place in C
memory.

b. Declaration

Following is the declaration for pointers to structures in C programming:

~ 254 ~
struct tagname *ptr;

For example: struct student *s

c. Accessing

It is explained below how to access the pointers to structures.

Ptr-> membername;

For example: s->sno, s->sname, s->marks;

d. Example in Program

The following programs shows the usage of pointers to structures:

Example 1:

#include<stdio.h>

struct student{

int sno;

char sname[30];

float marks;

};

main ( ){

struct student s;

struct student *st;

printf("enter sno, sname, marks:");

scanf ("%d%s%f", & [Link], &[Link], &s. marks);

st = &s;

printf ("details of the student are");

printf ("Number = %d\n", st ->sno);

~ 255 ~
 printf ("name = %s\n", st->sname);

printf ("marks =%f\n", st ->marks);

getch ( );

Output:

Let us run the above program that will produce the following result:

enter sno, sname, marks:1 Lucky 98

details of the student are:

Number = 1

name = Lucky

marks =98.000000

Example 2:

Consider another example which explains the functioning of pointers to structures.

#include<stdio.h>

struct person{

int age;

float weight;

};

int main(){

struct person *personPtr, person1;

personPtr = &person1;

printf("Enter age: ");

scanf("%d", &personPtr->age);

~ 256 ~
 printf("Enter weight: ");

scanf("%f", &personPtr->weight);

printf("Displaying:\n");

printf("Age: %d\n", personPtr->age);

printf("weight: %f", personPtr->weight);

return 0;

Output:

Let us run the above program that will produce the following result:

Enter age: 45

Enter weight: 60

Displaying:

Age: 45

weight: 60.000000

2.12.6 typedef in C
a. Definition

The typedef is a keyword used in C programming to provide some meaningful names to the
already existing variable in the C program. It behaves similarly as we define the alias for the
commands. In short, we can say that this keyword is used to redefine the name of an already
existing variable.

Syntax of typedef

typedef <existing_name> <alias_name>

In the above syntax, 'existing_name' is the name of an already existing variable while 'alias
name' is another name given to the existing variable.

~ 257 ~
For example, suppose we want to create a variable of type unsigned int, then it becomes a
tedious task if we want to declare multiple variables of this type. To overcome the problem, we
use a typedef keyword.

typedef unsigned int unit;

In the above statements, we have declared the unit variable of type unsigned int by using a
typedef keyword.

Now, we can create the variables of type unsigned int by writing the following statement:

unit a, b;

instead of writing:

unsigned int a, b;

Till now, we have observed that the typedef keyword provides a nice shortcut by providing an
alternative name for an already existing variable. This keyword is useful when we are dealing
with the long data type especially, structure declarations.

Let's understand through a simple example.

#include <stdio.h>

int main()

typedef unsigned int unit;

unit i,j;

i=10;

j=20;

printf("Value of i is :%d",i);

printf("\nValue of j is :%d",j);

return 0;

~ 258 ~
}

Output:

Value of i is :10

Value of j is :20

b. Using typedef with structures

Consider the below structure declaration:

struct student

char name[20];

int age;

};

struct student s1;

In the above structure declaration, we have created the variable of student type by writing the
following statement:

struct student s1;

The above statement shows the creation of a variable, i.e., s1, but the statement is quite big. To
avoid such a big statement, we use the typedef keyword to create the variable of type student.

struct student

char name[20];

int age;

};

typedef struct student stud;

~ 259 ~
stud s1, s2;

In the above statement, we have declared the variable stud of type struct student. Now, we can
use the stud variable in a program to create the variables of type struct student.

The above typedef can be written as:

typedef struct student

char name[20];

int age;

} stud;

stud s1,s2;

From the above declarations, we conclude that typedef keyword reduces the length of the code
and complexity of data types. It also helps in understanding the program.

Let's see another example where we typedef the structure declaration.

#include <stdio.h>

typedef struct student

char name[20];

int age;

}stud;

int main()

stud s1;

printf("Enter the details of student s1: ");

~ 260 ~
printf("\nEnter the name of the student:");

scanf("%s",&[Link]);

printf("\nEnter the age of student:");

scanf("%d",&[Link]);

printf("\n Name of the student is : %s", [Link]);

printf("\n Age of the student is : %d", [Link]);

return 0;

Output:

Learning Outcome 2.13: Use file I/O in C

2.13.1 Description of file I/O

Applications generally involve tremendous amount of data to be read and written to an auxiliary
[Link] save such information on the disk we use data files.

Files allow us to store information permanently in the disk; access and further it can be altered depending
upon the needs.

a. Definition of a file:

File is a set of records that can be accessed through the set of library functions.

b. Types of files

~ 261 ~
 Sequential File Random Access File

Data are kept sequentially Data can be read and modified randomly

For reading the last record, we need to read all For reading the last record, we can directly
the records before that record (the last one). access it.

It takes more time. Less time compared to sequential file.

2.13.2 Steps for File Operations

Like most other languages, C supports a number of functions that have the ability to perform basic file
operations, which include:

a. Opening of file

b. Reading or writing file

c. Closing file

a. Defining and opening a file

A file has to be opened before beginning of read and write operations.

Opening of a file creates a link between the operating system and the file functions.

FILE *fp where fp is file pointer.

Function fopen() is used to open a file.

Syntax for opening the file.

FILE *fp;

fp=fopen(“[Link]”,”r”);

The first statement declares the variable fpas a pointer to the data typeFILE. As stated earlier, FILE is a
structure that is defined in the I/O library.

The second statement opens the file named filename and assigns asidentifier to the FILE the pointer fp.
This pointer which contains all theinformation about the file is subsequently used as a communication
link between the system and the program.

~ 262 ~
The second statement also specifies the purpose of opening this file. Themode does this job. Mode can be
one of the following:

Mode Meaning of Mode During Inexistence of file

r Open for reading. If the file does not exist, fopen() returns NULL.

If the file exists, its contents are overwritten. If the

w Open for writing.
file does not exist, it will be created.

Open for append. i.e, Data is

a If the file does not exists, it will be created.
added to end of file.

Open for both reading and If the file does not exist, fopen() returns NULL.
r+
writing.

Open for both reading and If the file exists, its contents are overwritten. If the
w+
writing. file does not exist, it will be created.

Open for both reading and

a+ If the file does not exists, it will be created.
appending.

b. Reading or writing file

Once a file is opened, reading out of or writing to it is accomplished using the standard I/O routines that
are listed.

The functions fprintf() and fscanf() are the file version of printf() and fscanf(). The only difference while
using fprintf() and fscanf() is that, the first argument is a pointer to the structure FILE

#include<stdio.h>

int main()

~ 263 ~
int n;

FILE *fptr;

fptr=fopen("C:\\[Link]","w");

if(fptr==NULL){

printf("Error!");

printf("Enter n: ");

scanf("%d",&n);

fprintf(fptr,"%d",n);

fclose(fptr);

getch();

return0;

This program takes the number from user and stores in file. After you compile and run this program, you
can see a text file [Link] created in C drive of your computer. When you open that file, you can see
the integer you entered.

Similarly, fscanf() can be used to read data from file.

c. Reading from file

#include<stdio.h>

int main()

int n;

FILE *fptr;

if((fptr=fopen("C:\\[Link]","r"))==NULL){

printf("Error! opening file");

~ 264 ~
}

fscanf(fptr,"%d",&n);

printf("Value of n=%d",n);

fclose(fptr);

If you have run program above to write in file successfully, you can get the integer back entered in that
program using this program.

Other functions like fgetchar(), fputc() etc. can be used in similar way.

d. Closing a file

This statement closes the file associated with file pointer.

fclose(fptr);

It closes one file at a time

To close one or more files at a time, the function fcloseall() is used.

A program to write a string in a file named [Link]

#include <stdio.h>

#include <conio.h>

main()

FILE *fp;

char text[30];

fp=fopen("[Link]","w");

printf("Enter text here:");

gets(text);

fprintf(fp,"%s",text);

~ 265 ~
fclose(fp);

A program to write and read a string in a file named [Link]

#include <stdio.h>

#include <conio.h>

main()

FILE *fp;

char text[30];

fp=fopen("[Link]","w+");

printf("Enter text here:");

gets(text);

fprintf(fp,"%s",text);

printf("\n Name:");

fscanf(fp,"%s",text);

printf("\n%s",text);

fclose(fp);

Exercises

~ 266 ~
 1. Write a C program to calculate the Water bill. As per the following rules

Meters Rate

500 and above 15%

300 up to 499 10%

100 up to 299 7.5%

Bellow 100 5%

2. Write a C program to display numbers from 10 to 20 except 16 horizontally by

leaving a space of 5 characters.
3. Write a C program to take integer elements of two matrices(A and B) of the order
3x2 , calculate their sum and display them on the output.
4. Write a C program that uses a structure to take the information about an employe(
i.e ID, name, age, salary and address), initialize the structure by 001,AAA,
30,100000 and Musanze and display them on the screen.

LEARNING UNIT 3: APPLY DATA STRUCTURE USING C

Learning Outcomes: 3.1 Use data structure type to use solving a problem
3.2 Use array data structure using C programming
~ 267 ~
 techniques
3.3 Use stack data structure using C programming
techniques
3.4 Use queue data structure using C programming
techniques
3.5 Use linked List data structure using C
programming techniques.
3.6 Use trees data structure using C programming
techniques.
3.7 Use hashing data structure using C programming
techniques
3.8 Use graph data structure using C programming
techniques

Learning outcome 3.1 Use Data Structure Type to use

Solving a Problem

3.1.1 Description of Data Structures using C

a. Definition
Made up of 2 words : “DATA” + “STRUCTURES”
It is a way to arrange data in computers.
A data structure is a technique of storing and organizing the data in such a way that the data can
be utilized in an efficient manner. In short, Data structure is logical or mathematical organization
of data.
b. Types of data structure
There are two types of data structures: Primitive data structure and Non-primitive data Structure.

Primitive Data structure

The primitive data structures are primitive data types. The int, char, float, double, and Pointer
are the primitive data structure that can hold a single value.

~ 268 ~
Non-Primitive Data structure
Non-Primitive Data structure is classified into two categories:
 Linear data structure: Data structures where data elements are arranged sequentially or
linearly where the elements are attached to its previous and next adjacent in what is called
a linear data structure. In linear data structure, single level is involved. Therefore, we can
traverse all the elements in single run only. Linear data structures are easy to implement
because computer memory is arranged in a linear way. Its examples
are array, stack, queue, linked list, etc.
 Non-linear data structure: Data structures where data elements are not arranged sequentially
or linearly are called non-linear data structures. In a non-linear data structure, single level
is not involved. Therefore, we can’t traverse all the elements in single run only. Non-linear
data structures are not easy to implement in comparison to linear data structure. It utilizes
computer memory efficiently in comparison to a linear data structure. Its examples
are trees and graphs.
Example: You might want to store data in
 Linear fashion – Array/ Linked List
 One on the other – Stacks
 Hierarchical Fashion – Trees
 Connect nodes – Graph

~ 269 ~
 Linear Data structure Non-Linear Data structure

Basic In this structure, the elements are In this structure, the elements are arranged
arranged sequentially or linearly hierarchically or non-linear manner.
and attached to one another.

Types Arrays, linked list, stack, queue Trees and graphs are the types of a non-linear
are the types of a linear data data structure.
structure.

implementation Due to the linear organization, Due to the non-linear organization, they are
they are easy to implement. difficult to implement.

Traversal As linear data structure is a The data items in a non-linear data structure
single level, so it requires a cannot be accessed in a single run. It requires
single run to traverse each data multiple runs to be traversed.
item.

Arrangement Each data item is attached to the Each item is attached to many other items.
previous and next items.

Levels This data structure does not In this, the data elements are arranged in

~ 270 ~
 contain any hierarchy, and all the multiple levels.
data elements are organized in a
single level.

Memory In this, the memory utilization is In this, memory is utilized in a very efficient
utilization not efficient. manner.

Time The time complexity of linear The time complexity of non-linear data
complexity data structure increases with the structure often remains same with the increase
increase in the input size. in the input size.

Applications Linear data structures are mainly Non-linear data structures are used in image
used for developing the software. processing and Artificial Intelligence.

c. Major Operations

The major or the common operations that can be performed on the data structures are:
 Searching: We can search for any element in a data structure.
 Sorting: We can sort the elements of a data structure either in an ascending or
descending order.
 Insertion: We can also insert the new element in a data structure.
 Updating: We can also update the element, i.e., we can replace the element with another
element.
 Deletion: We can also perform the delete operation to remove the element from the data
structure.
d. Factors for Choosing Data Structure

Some factors are considered for choosing the data structure:

 What type of data needs to be stored? It might be a possibility that a certain data
structure can be the best fit for some kind of data.
 Cost of operations: If we want to minimize the cost for the operations for the most
frequently performed operations. For example, we have a simple list on which we have to
perform the search operation; then, we can create an array in which elements are stored in

~ 271 ~
 sorted order to perform the binary search. The binary search works very fast for the
simple list as it divides the search space into half.
 Memory usage: Sometimes, we want a data structure that utilizes less memory.

e. Advantages of Data structures

The following are the advantages of a data structure:

 Efficiency: If the choice of a data structure for implementing a particular
Abstract data types (ADT) is proper, it makes the program very efficient in terms of time
and space.
 Reusability: The data structure provides reusability means that multiple client programs
can use the data structure.
 Abstraction: The data structure specified by an ADT also provides the level of
abstraction. The client cannot see the internal working of the data structure, so it does not
have to worry about the implementation part. The client can only see the interface.

3.1.2 Searching
Searching is the process of finding some particular element in the list. If the element is present in
the list, then the process is called successful and the process returns the location of that element,
otherwise the search is called unsuccessful.
There are two popular search methods that are widely used in order to search some item into the
list. However, choice of the algorithm depends upon the arrangement of the list.
 Linear Search
 Binary Search
a. What is a linear search?
A linear search is also known as a sequential search that simply scans each element at a time.
Suppose we want to search an element in an array or list; we simply calculate its length and do
not jump at any item.
Let's consider a simple example.
Suppose we have an array of 10 elements as shown in the below figure:

~ 272 ~
The above figure shows an array of character type having 10 values. If we want to search 'E',
then the searching begins from the 0th element and scans each element until the element, i.e., 'E'
is not found. We cannot directly jump from the 0 th element to the 4th element, i.e., each element is
scanned one by one till the element is not found.
We access list elements, starting with the first, and compare each element with search key. If we
find a match, the search is successful. In this case we return the index of the list element and still
no match, and then the search is unsuccessful.

the search is unsuccessful

~ 273 ~
b. Complexity of Linear search
As linear search scans each element one by one until the element is not found. If the number of
elements increases, the number of elements to be scanned is also increased. We can say that
the time taken to search the elements is proportional to the number of elements. Therefore, the
worst-case complexity is O(n)
c. What is a Binary search?
A binary search is a search in which the middle element is calculated to check whether it is
smaller or larger than the element which is to be searched. The main advantage of using binary
search is that it does not scan each element in the list. Instead of scanning each element, it
performs the searching to the half of the list. So, the binary search takes less time to search an
element as compared to a linear search.
The one pre-requisite of binary search is that an array should be in sorted order, whereas the
linear search works on both sorted and unsorted array. The binary search algorithm is based on
the divide and conquer technique, which means that it will divide the array recursively.
There are three cases used in the binary search:

~ 274 ~
Case 1: data<a[mid] then left = mid+1.
Case 2: data>a[mid] then right=mid-1
Case 3: data = a[mid] // element is found
In the above case, 'a' is the name of the array, mid is the index of the element calculated
recursively, data is the element that is to be searched, left denotes the left element of the array
and right denotes the element that occur on the right side of the array.
Let's understand the working of binary search through an example.
Suppose we have an array of 10 size which is indexed from 0 to 9 as shown in the below figure:
We want to search for 70 element from the above array.
Step 1: First, we calculate the middle element of an array. We consider two variables, i.e., left
and right. Initially, left =0 and right=9 as shown in the below figure:

The middle element value can be calculated as:

Therefore, mid = 4 and a[mid] = 50. The element to be searched is 70, so a[mid] is not equal to
data. The case 2 is satisfied, i.e., data>a[mid].

~ 275 ~
Step 2: As data>a[mid], so the value of left is incremented by mid+1, i.e., left=mid+1. The value
of mid is 4, so the value of left becomes 5. Now, we have got a subarray as shown in the below
figure:

Now again, the mid-value is calculated by using the above formula, and the value of mid
becomes 7. Now, the mid can be represented as:

In the above figure, we can observe that a[mid]>data, so again, the value of mid will be
calculated in the next step.
Step 3: As a[mid]>data, the value of right is decremented by mid-1. The value of mid is 7, so the
value of right becomes 6. The array can be represented as:

The value of mid will be calculated again. The values of left and right are 5 and 6, respectively.
Therefore, the value of mid is 5. Now the mid can be represented in an array as shown below:

~ 276 ~
In the above figure, we can observe that a[mid]<data.
Step 4: As a[mid]<data, the left value is incremented by mid+1. The value of mid is 5, so the
value of left becomes 6.
Now the value of mid is calculated again by using the formula which we have already discussed.
The values of left and right are 6 and 6 respectively, so the value of mid becomes 6 as shown in
the below figure:

We can observe in the above figure that a[mid]=data. Therefore, the search is completed, and the
element is found successfully.
d. Differences between Linear search and Binary search

~ 277 ~
The following are the differences between linear search and binary search:

Basis of Linear search Binary search

comparison

Definition The linear search starts searching from It finds the position of the searched
the first element and compares each element by finding the middle element
element with a searched element till the of the array.
element is not found.

Sorted data In a linear search, the elements don't The pre-condition for the binary search
need to be arranged in sorted order. is that the elements must be arranged in
a sorted order.

Implementation The linear search can be implemented The implementation of binary search is
on any linear data structure such as an limited as it can be implemented only
array, linked list, etc. on those data structures that have two-
way traversal.

Approach It is based on the sequential approach. It is based on the divide and conquer
approach.

Size It is preferable for the small-sized data It is preferable for the large-size data
sets. sets.

Efficiency It is less efficient in the case of large- It is more efficient in the case of large-
size data sets. size data sets.

Worst-case In a linear search, the worst- case In a binary search, the worst-case
scenario scenario for finding the element is O(n). scenario for finding the element is
O(log2n).

Best-case In a linear search, the best-case scenario In a binary search, the best-case
scenario for finding the first element in the list is scenario for finding the first element in

~ 278 ~
 O(1). the list is O(1).

Dimensional It can be implemented on both a single It can be implemented only on a

array and multidimensional array. multidimensional array.

e. Implementation of Linear Search

#include<stdio.h>
void main ()
{
int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};
int item, i,flag;
printf("\nEnter Item which is to be searched\n");
scanf("%d",&item);
for (i = 0; i< 10; i++)
{
if(a[i] == item)
{
flag = i+1;
break;
}
else
flag = 0;
}
if(flag != 0)
{
printf("\nItem found at location %d\n",flag);
}
else
{
printf("\nItem not found\n");
}
}

~ 279 ~
f. Implementation of Binary Search using Recursion
#include<stdio.h>
int binarySearch(int[], int, int, int);
void main ()
{
int arr[10] = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};
int item, location=-1;
printf("Enter the item which you want to search ");
scanf("%d",&item);
location = binarySearch(arr, 0, 9, item);
if(location != -1)
{
printf("Item found at location %d",location);
}
else
{
printf("Item not found");
}
}
int binarySearch(int a[], int beg, int end, int item)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
if(a[mid] == item)
{
return mid+1;
}

~ 280 ~
else if(a[mid] < item)
{
return binarySearch(a,mid+1,end,item);
}
else
{
return binarySearch(a,beg,mid-1,item);
}

}
return -1;
}

g. Interpolation Search
Interpolation search is an improved variant of binary search. This search algorithm works on the
probing position of the required value. For this algorithm to work properly, the data collection
should be in a sorted form and equally distributed.
Binary search has a huge advantage of time complexity over linear search. Linear search has
worst-case complexity of Ο(n) whereas binary search has Ο(log n).
There are cases where the location of target data may be known in advance. For example, in
case of a telephone directory, if we want to search the telephone number of Mark. Here,
linear search and even binary search will seem slow as we can directly jump to memory
space where the names start from 'M' are stored.
Positioning in Binary Search
In binary search, if the desired data is not found then the rest of the list is divided in two parts,
lower and higher. The search is carried out in either of them.

~ 281 ~
Even when the data is sorted, binary search does not take advantage to probe the position of the
desired data.
Position Probing in Interpolation Search
Interpolation search finds a particular item by computing the probe position. Initially, the probe
position is the position of the middle most item of the collection.

If a match occurs, then the index of the item is returned. To split the list into two parts, we use
the following method −
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list
If the middle item is greater than the item, then the probe position is again calculated in the sub-
array to the right of the middle item. Otherwise, the item is searched in the subarray to the left of
the middle item. This process continues on the sub-array as well until the size of subarray
reduces to zero.
Runtime complexity of interpolation search algorithm is Ο(log (log n)) as compared to Ο(log
n) of BST in favorable situations.

~ 282 ~
Algorithm
As it is an improvisation of the existing BST algorithm, we are mentioning the steps to search
the 'target' data value index, using position probing −
Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new middle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.
Pseudocode

A → Array list
N → Size of A
X → Target Value

Procedure Interpolation_Search()

Set Lo → 0
Set Mid → -1
Set Hi → N-1

While X does not match

if Lo equals to Hi OR A[Lo] equals to A[Hi]

EXIT: Failure, Target not found
end if

Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While

End Procedure
[Link] of interpolation search

~ 283 ~
#include<stdio.h>

#define MAX 10

// array of items on which linear search will be conducted.

int list[MAX] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };

int find(int data) {

int lo = 0;
int hi = MAX - 1;
int mid = -1;
int comparisons = 1;
int index = -1;

while(lo <= hi) {

printf("\nComparison %d \n" , comparisons ) ;
printf("lo : %d, list[%d] = %d\n", lo, lo, list[lo]);
printf("hi : %d, list[%d] = %d\n", hi, hi, list[hi]);

comparisons++;

// probe the mid point

mid = lo + (((double)(hi - lo) / (list[hi] - list[lo])) *
(data - list[lo]));
printf("mid = %d\n",mid);

// data found
if(list[mid] == data) {
index = mid;
break;
} else {
if(list[mid] < data) {
// if data is larger, data is in upper half
lo = mid + 1;
} else {
// if data is smaller, data is in lower half
hi = mid - 1;
}
}
}

printf("\nTotal comparisons made: %d", --comparisons);

return index;
}

int main() {
//find location of 33
int location = find(33);

~ 284 ~
 // if element was found
if(location != -1)
printf("\nElement found at location: %d" ,(location+1));
else
printf("Element not found.");

return 0;
}

You can change the search value and execute the program to test it.
3.1.3 List of Data Structures using C
 Array

 Linked List
 Stack
 Queue
 Tree
 Heap
 Hashing
 Graph

Learning output 3.2 Use Array Data Structure Using C

Programming Techniques

3.2.1 Description of array data structure

 Linear Data Structure

 Elements are stored in contiguous memory locations

~ 285 ~
  Can access elements randomly using index
 Stores homogeneous elements i.e, similar elements
a. Advantages
 Random access
 Easy sorting and iteration
 Replacement of multiple variables
b. Disadvantages
 Size is fixed
 Difficult to insert and delete
 If capacity is more and occupancy less, most of the array gets wasted
 Needs contiguous memory to get allocated

3.2.2 Application of array structure using C

 For storing information in a linear fashion

 Suitable for applications that require frequent searching
Syntax:
 Array declaration
Datatype varname [size] ;
 Can also do declaration and initialization at once
Datatype varname [] = {ele1, ele2, ele3, ele4};

3.2.3 Using arrays data structure operations

#include <stdio.h>
int main() {
//array declaration
int rollNo[10];
//taking inputs
for(int i=0;i<10;i++)

~ 286 ~
 scanf("%d",&rollNo[i]);
//printing
for(int i=0;i<10;i++)
printf("%d ",rollNo[i]);
return 0;
}

Input:
12 13 34 56 12 87 56 78 23 10

Output:

12 13 34 56 12 87 56 78 23 10

Learning outcome 3.3 Use Linked List Data Structure Using

C Programming Techniques
3.3.1 Description of use of stack data structure using C
 Linear Data Structure

 Elements can be stored as per memory availability

 Can access elements on linear fashion only
 Stores homogeneous elements i.e, similar elements
 Dynamic in size
 Easy insertion and deletion
 Starting element or node is the key which is generally termed as the head.
 Linked List can be defined as collection of objects called nodes that are randomly
stored in the memory.
 A node contains two fields i.e. data stored at that particular address and the pointer
which contains the address of the next node in the memory.
 The last node of the list contains pointer to the null.

~ 287 ~
a. Advantages
 Dynamic in size.
 No wastage as capacity and size is always equal.
 Easy insertion and deletion as 1 link manipulation is required.
 Efficient memory allocation.
 The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
b. Disadvantages
 If the head node is lost, the linked list is lost
 No random access possible
c. Why use linked list over array?
Till now, we were using array data structure to organize the group of elements that are to be
stored individually in the memory. However, Array has several advantages and disadvantages
which must be known in order to decide the data structure which will be used throughout the
program.
Array contains following limitations:
1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand the
size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory. Inserting any
element in the array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations of an array. Using
linked list is useful because,

~ 288 ~
 1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available memory
space.
3.3.2 Applications of stack
 Suitable where memory is limited

 Suitable for applications that require frequent insertion and deletion

3.3.3 Types of Linked List
 Singly Linked list
 Doubly Linked list
 Circular Linked list
 Doubly Circular Linked list
a. Singly Linked List
It is the commonly used linked list in programs. If we are talking about the linked list, it means it
is a singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is
the data part, and the other one is the address part, which contains the address of the next or the
successor node. The address part in a node is also known as a pointer.
Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:

We can observe in the above figure that there are three different nodes having address 100, 200
and 300 respectively. The first node contains the address of the next node, i.e., 200, the second
node contains the address of the last node, i.e., 300, and the third node contains the NULL value

~ 289 ~
in its address part as it does not point to any node. The pointer that holds the address of the initial
node is known as a head pointer.
The linked list, which is shown in the above diagram, is known as a singly linked list as it
contains only a single link. In this list, only forward traversal is possible; we cannot traverse in
the backward direction as it has only one link in the list.
Representation of the node in a singly linked list
struct node
{
int data;
struct node *next;
}
In the above representation, we have defined a user-defined structure named a node containing
two members, the first one is data of integer type, and the other one is the pointer (next) of the
node type.
To know more about a singly linked list, click on the link given below:
[Link]
b. Doubly linked list
As the name suggests, the doubly linked list contains two pointers. We can define the doubly
linked list as a linear data structure with three parts: the data part and the other two address part.
In other words, a doubly linked list is a list that has three parts in a single node, includes one data
part, a pointer to its previous node, and a pointer to the next node.
Suppose we have three nodes, and the address of these nodes are 100, 200 and 300, respectively.
The representation of these nodes in a doubly-linked list is shown below:

~ 290 ~
As we can observe in the above figure, the node in a doubly-linked list has two address parts;
one part stores the address of the next while the other part of the node stores the previous node's
address. The initial node in the doubly linked list has the NULL value in the address part, which
provides the address of the previous node.
Representation of the node in a doubly linked list
struct node
{
int data;
struct node *next;
struct node *prev;
}
In the above representation, we have defined a user-defined structure named a node with three
members, one is data of integer type, and the other two are the pointers, i.e., next and prev of
the node type. The next pointer variable holds the address of the next node, and the prev
pointer holds the address of the previous node. The type of both the pointers, i.e., next and
prev is struct node as both the pointers are storing the address of the node of the struct
node type.
To know more about doubly linked list, click on the link given below:
[Link]
c. Circular linked list
A circular linked list is a variation of a singly linked list. The only difference between the singly
linked list and a circular linked list is that the last node does not point to any node in a singly
linked list, so its link part contains a NULL value. On the other hand, the circular linked list is a
list in which the last node connects to the first node, so the link part of the last node holds the
first node's address. The circular linked list has no starting and ending node. We can traverse in
any direction, i.e., either backward or forward. The diagrammatic representation of the circular
linked list is shown below:
struct node
{
int data;
struct node *next;

~ 291 ~
}
A circular linked list is a sequence of elements in which each node has a link to the next node,
and the last node is having a link to the first node. The representation of the circular linked list
will be similar to the singly linked list, as shown below:

To know more about the circular linked list, click on the link given below:
[Link]
Doubly Circular linked list
The doubly circular linked list has the features of both the circular linked list and doubly linked
list.

The above figure shows the representation of the doubly circular linked list in which the last
node is attached to the first node and thus creates a circle. It is a doubly linked list also because
each node holds the address of the previous node also. The main difference between the doubly
linked list and doubly circular linked list is that the doubly circular linked list does not contain
the NULL value in the previous field of the node. As the doubly circular linked contains three

~ 292 ~
parts, i.e., two address parts and one data part so its representation is similar to the doubly linked
list.
struct node
{
int data;
struct node *next;
struct node *prev;
}
To know more about the doubly circular linked list, click on the link given below:
[Link]
3.3.4 Basic Operations on Linked List
 Traversal: To traverse all the nodes one after another.

 Insertion: To add a node at the given position.

 Deletion: To delete a node.
 Searching: To search an element(s) by value.
 Updating: To update a node.
 Sorting: To arrange nodes in a linked list in a specific order.
 Merging: To merge two linked lists into one.
[Link]
// Linked list operations in C
#include <stdio.h>
#include <stdlib.h>
// Create a node
struct Node {
int data;
struct Node* next;
};
// Insert at the beginning
void insertAtBeginning(struct Node** head_ref, int new_data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// insert the data

~ 293 ~
 new_node->data = new_data;
new_node->next = (*head_ref);
// Move head to new node
(*head_ref) = new_node;
}
// Insert a node after a node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
printf("the given previous node cannot be NULL");
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
// Insert the the end
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
while (last->next != NULL) last = last->next;
last->next = new_node;
return;
}
// Delete a node

~ 294 ~
void deleteNode(struct Node** head_ref, int key) {
struct Node *temp = *head_ref, *prev;
if (temp != NULL && temp->data == key) {
*head_ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key is not present
if (temp == NULL) return;
// Remove the node
prev->next = temp->next;
free(temp);
}
// Search a node
int searchNode(struct Node** head_ref, int key) {
struct Node* current = *head_ref;
while (current != NULL) {
if (current->data == key) return 1;
current = current->next;
}
return 0;
}
// Sort the linked list
void sortLinkedList(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;

~ 295 ~
 if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
// Print the linked list
void printList(struct Node* node) {
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}
// Driver program
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);

~ 296 ~
 insertAtEnd(&head, 4);
insertAfter(head->next, 5);

printf("Linked list: ");

printList(head);

printf("\nAfter deleting an element: ");

deleteNode(&head, 3);
printList(head);

int item_to_find = 3;
if (searchNode(&head, item_to_find)) {
printf("\n%d is found", item_to_find);
} else {
printf("\n%d is not found", item_to_find);
}
sortLinkedList(&head);
printf("\nSorted List: ");
printList(head);
}
3.3.5 Demonstration of Linked List in a C program
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
struct node *next;
}*p,*tmp,*tmp1;
void insert_end(int);
void insert_beg(int);
void ldelete(int);

~ 297 ~
void display();
void main()
{
int val,n;
p=NULL;
do
{printf("\n************************* MENU ************************");
printf("\[Link] AT END");
printf("\[Link] AT BEG");
printf("\[Link] A PARTICULAR ELE");
printf("\[Link] FROM BEG");
printf("\[Link] FROM END");
printf("\[Link]");
printf("\[Link]");
printf("\n enter ur choice : ");
scanf("%d",&n);
switch(n)
{case 1: printf("\nenter the value ");
scanf("%d",&val);
insert_end(val);
break;
case 2: printf("\nenter the value");
scanf("%d",&val);
insert_beg(val);
break;
case 3: printf("\nenter the value");
scanf("%d",&val);
l_delete(val);
break;
case 4:
delete_beg();

~ 298 ~
 break;
case 5:
delete_end();
break;
case 6: display();
break;
case 7: exit(0);
break;
default: printf("\n Wrong Choice!");
break;
}
printf("\n do u want to cont... ");
}while('y'==getch());
}
void insert_end(int ele)
{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=NULL;
if(p==NULL)
p=tmp1;
else
{
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=tmp1;
}
}
void insert_beg(int ele)
{

~ 299 ~
 tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=p;
p=tmp1;
}

void l_delete(int ele)

{
tmp=p;
struct node *pre=tmp;
while(tmp!=NULL)
{if(tmp->data==ele)
{ if(tmp==p)
{p=tmp->next;
free(tmp);
return;
}
else
{pre->next=tmp->next;
free(tmp);
return;
}
}
else
{ pre=tmp;
tmp=tmp->next;
}
}
printf("\n no match found!! ");
}

~ 300 ~
void delete_beg()
{
tmp=p;
if(p==NULL)
printf("\n no element to be deleted!! ");
else
{
printf("\nelement deleted - %d", p->data);
p=p->next;
}

void delete_end()
{
tmp=p;
struct node* pre;
if(p==NULL)
printf("\n no element to be deleted!! ");
else if(p->next==NULL)
{
printf("\nelement deleted - %d", p->data);
p=NULL;
}
else
{
while(tmp->next!=NULL){
pre=tmp;
tmp=tmp->next;
}

~ 301 ~
 pre->next=NULL;
printf("\nelement deleted - %d", tmp->data);
}
}
void display()
{
tmp=p;
while(tmp!=NULL)
{printf("\n %d",tmp->data);
tmp=tmp->next;
}
}
Output:
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter your choice : 1

enter the value 23

do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG

~ 302 ~
[Link] FROM END
[Link]
[Link]
enter ur choice :
1

enter the value 12

do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice :
2

enter the value67

do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]

~ 303 ~
enter ur choice :
2

enter the value90

do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice :
6

90
67
23
12
do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice : 3

~ 304 ~
enter the value67

do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice :
6

90
23
12
do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice :
4

element deleted - 90

~ 305 ~
do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice : 5

element deleted - 12
do u want to cont...
************************* MENU ************************
[Link] AT END
[Link] AT BEG
[Link] A PARTICULAR ELE
[Link] FROM BEG
[Link] FROM END
[Link]
[Link]
enter ur choice : 6

23
do u want to cont...

Learning outcome 3.4. Use Stack Data Structure Using C

Programming Techniques
3.4.1 Description of use of stack data structure using C

~ 306 ~
  It is a type of Linear Data Structures using C
 Follows LIFO: Last In First Out
 Only the top elements are available to be accessed
 Insertion and deletion takes place from the top
Eg: a stack of plates, chairs, Undo/Redo stacks in Excel or Word, etc.

a. Working of Stack in C

A stack is a container of objects that are inserted and removed according to the Last-in First-
Out (LIFO) principle. Both operation insert and deletion perform in stack only from TOP.
b. Real life example of stack

A most popular example of stack is plates in marriage party. Fresh plates are pushed onto to
the top and popped from the top.

c. Stack Representation

The following diagram depicts a stack and its operations

~ 307 ~
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we are going to
implement stack using arrays, which makes it a fixed size stack implementation.

d. Advantages

 Maintains data in a LIFO manner

 The last element is readily available for use
 All operations are of O(1) complexity
e. Disadvantages

 Manipulation is restricted to the top of the stack

 Not much flexible
3.4.2 Applications of stack
 Recursion

 Parsing
 Editors
 Expression evaluation
 Backtracking (game playing, finding paths, exhaustive searching)
 Memory management, run-time environment for nested language features.

~ 308 ~
  To reverse a word. You push a given word to stack - letter by letter - and then pop
letters from the stack.
 An "undo" mechanism in text editors; this operation is accomplished by keeping all
text changes in a stack.
 space for parameters and local variables is created internally using a stack.
 compiler's syntax check for matching braces is implemented by using stack.
 Back/Forward on browsers are perform using stacks.
3.4.3 Operations on Stack
 push() – used to insert element at top

 pop() – removes the top element from stack

 isEmpty() – returns true is stack is empty
 peek() – to get the top element of the stack
 isFull() – to check if stack is full
 All operation works in constant time i.e, O(1)
3.4.4 Demonstration of Stack – using Array

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct stackk {
int top;
unsigned size;
int* array;
};
struct stackk* create(unsigned size)
{
struct stackk* stackk = (struct stackk*)malloc(sizeof(struct stackk));
stackk->size = size;
stackk->top = -1;
stackk->array = (int*)malloc(stackk->size * sizeof(int));

~ 309 ~
 return stackk;
}

int isFull(struct stackk* stackk)

{
return stackk->top == stackk->size - 1;
}

int isEmpty(struct stackk* stackk)

{
return stackk->top == -1;
}
void push(struct stackk* stackk, int item)
{
if (isFull(stackk))
return;
stackk->array[++stackk->top] = item;
}
int pop(struct stackk* stackk)
{
if (isEmpty(stackk))
return -1;
return stackk->array[stackk->top--];
}

int peek(struct stackk* stackk)

{
if (isEmpty(stackk))
return INT_MIN;
return stackk->array[stackk->top];
}

~ 310 ~
int main()
{
int val,n;
struct stackk* stackk = create(100);
do
{printf("\n************************* MENU ************************");
printf("\[Link]");
printf("\[Link]");
printf("\[Link]");
printf("\n4 IS EMPTY");
printf("\[Link]");
printf("\n enter ur choice : ");
scanf("%d",&n);
switch(n)
{
case 1:
printf("\nenter the value ");
scanf("%d",&val);
push(stackk , val);
break;
case 2:
printf("\n popped element : %d",pop(stackk));
break;

case 3:
printf("\n top element : %d",peek(stackk));
break;
case 4: printf("\n is empty : %d",isEmpty(stackk));
break;
case 5: exit(0);
break;

~ 311 ~
 default: printf("\n Wrong Choice!");
break;
}
printf("\n do u want to cont... ");
}while('y'==getch());

}
Output:
************************* MENU ************************
[Link]
[Link]
[Link]
4 IS EMPTY
[Link]
enter ur choice :
1
enter the value
45
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link]
4 IS EMPTY
[Link]
enter ur choice :
1
enter the value
56
do u want to cont...
************************* MENU ************************

~ 312 ~
[Link]
[Link]
[Link]
4 IS EMPTY
[Link]
enter ur choice :
3
top element : 56
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link]
4 IS EMPTY
[Link]
enter ur choice :
4
is empty : 0
do u want to cont...

3.4.5 Demonstration of Stack – using LinkedList

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
struct node *next;
}*p,*tmp,*tmp1,*end;
void insert_end(int);
void display();

~ 313 ~
void delete_end();
void isEmpty();
int main()
{
int val,n;
p=NULL;
do
{printf("\n************************* MENU ************************");
printf("\[Link]");
printf("\[Link]");
printf("\n3 IS EMPTY");
printf("\[Link]");
printf("\[Link]");
printf("\nenter ur choice : ");
scanf("%d",&n);
switch(n)
{
case 1:
printf("\nenter the value ");
scanf("%d",&val);
insert_end(val);
break;
case 2:
delete_end();
break;
case 3:
isEmpty();
break;
case 4: display();
break;
case 5: exit(0);

~ 314 ~
 break;
default: printf("\n Wrong Choice!");
break;
}
printf("\ndo u want to cont... ");
}while('y'==getch());
}
void insert_end(int ele)
{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=NULL;
if(p==NULL)
p=tmp1;
else
{
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=tmp1;
}
end=tmp1;
}
void delete_end()
{
tmp=p;
struct node* pre;
if(p==NULL)
printf("\n no element to be deleted!! ");
else if(p->next==NULL)
{

~ 315 ~
 printf("\nelement deleted - %d", p->data);
p=NULL;
end=NULL;
}
else
{
while(tmp->next!=NULL){
pre=tmp;
tmp=tmp->next;
}
pre->next=NULL;
end=pre;
printf("\nelement deleted - %d", tmp->data);
}
}
void isEmpty(){
if(p==NULL)
printf("Stack is Empty");
else
{
printf("Stack is Not Empty");
}
}
void display()
{
tmp=p;
while(tmp!=NULL)
{printf("\n %d",tmp->data);
tmp=tmp->next;
}
}

~ 316 ~
Output
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]
enter ur choice : 1

enter the value 56

do u want to cont...
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]
enter ur choice :
1

enter the value 67

do u want to cont...
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]
enter ur choice :

~ 317 ~
3
Stack is Not Empty
do u want to cont...
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]
enter ur choice :
4

56
67
do u want to cont...
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]
enter ur choice : 2

element deleted - 67
do u want to cont...
************************* MENU ************************
[Link]
[Link]
3 IS EMPTY
[Link]
[Link]

~ 318 ~
enter ur choice : 4

56
do u want to cont...

Learning outcome 3.5 Use Queue Data Structure Using C

Programming Techniques
3.5.1 Description of queue data structure using C

 Linear Data Structures using C

 Follows FIFO: First In First Out
 Insertion can take place from the rear end.
 Deletion can take place from the front end.
 Eg: queue at ticket counters, bus station
 Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a
queue is open at both its ends. One end is always used to insert data (enqueue) and
the other is used to remove data (dequeue). Queue follows First-In-First-Out
methodology, i.e., the data item stored first will be accessed first.
a. Working of Queue in C

Queue is work on the principal of First-In-First-Out (FIFO), it means first entered item remove
first. Queue have two end front and rear, from front you can insert element and from rear you can
delete element.

~ 319 ~
 b. Real life example of stack

A common example of queue is movie theater ticket counter, there first person who stand in
front of ticket window take ticket first and remove from line and new person always stand in line
from end.

Single-Lane One-Way Road: First car go first

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first,
exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops

Ticket Counter: First person get ticket first and go out first

c. Some other Real-Life Examples of Queue

 Queue of processes in OS.

 Queue of people at any service point such as ticketing etc.

~ 320 ~
  Queue of packets in data communication.
 Queue of air planes waiting for landing instructions.

d. Queue Representation

As we now understand that in queue, we access both ends for different reasons. The following
diagram given below tries to explain queue representation as data structure −

As in stacks, a queue can also be implemented using Arrays, Linked-lists, Pointers and
Structures. For the sake of simplicity, we shall implement queues using one-dimensional array.
e. Advantages

 Maintains data in FIFO manner

 Insertion from beginning and deletion from end takes O(1) time
f. Applications

 Scheduling
 Maintaining playlist
 Interrupt handling
3.5.2 Operations on Queue
 enqueue() – used to insert element at top

 dequeue () – removes the top element from queue

 peekfirst() – to get the first element of the queue
 peeklast() – to get the last element of the queue
 isfull() − Checks if the queue is full.
 All operation works in constant time i.e, O(1)
3.5.3 Demonstration of Queue- using Array
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

~ 321 ~
struct que
{
int front, rear, size;
unsigned actualSize;
int* arr;
};
struct que* createque(unsigned actualSize)
{
struct que* que = (struct que*) malloc(sizeof(struct que));
que->actualSize = actualSize;
que->front = que->size = 0;
que->rear = actualSize - 1;
que->arr = (int*) malloc(que->actualSize * sizeof(int));
return que;
}
int isFull(struct que* que)
{ return (que->size == que->actualSize); }

void enqueue(struct que* que, int item)

{
if (isFull(que))
return;
que->rear = (que->rear + 1)%que->actualSize;
que->arr[que->rear] = item;
que->size = que->size + 1;
printf("%d enqueued to que\n", item);
}
int isEmpty(struct que* que)
{ return (que->size == 0); }

int dequeue(struct que* que)

~ 322 ~
{
if (isEmpty(que))
return INT_MIN;
int item = que->arr[que->front];
que->front = (que->front + 1)%que->actualSize;
que->size = que->size - 1;
return item;
}
int front(struct que* que)
{
if (isEmpty(que))
return INT_MIN;
return que->arr[que->front];
}
int rear(struct que* que)
{
if (isEmpty(que))
return INT_MIN;
return que->arr[que->rear];
}
int main()
{
int val,n;
struct que* que = createque(1000);

do
{printf("\n************************* MENU ************************");
printf("\[Link]");
printf("\[Link]");
printf("\[Link] EMPTY");
printf("\[Link] FULL");

~ 323 ~
printf("\[Link] ELE");
printf("\[Link] ELE");
printf("\[Link]");
printf("\nenter ur choice : ");
scanf("%d",&n);
switch(n)
{case 1: printf("\nenter the value ");
scanf("%d",&val);
enqueue(que,val);
break;
case 2:
dequeue(que);
break;
case 3:
printf("\nIsEmpty : %d",isEmpty(que));
break;
case 4:
printf("\nIsFull : %d",isFull(que));
break;
case 5:
printf("\nFront element: %d",front(que));
break;
case 6:
printf("\nLast element : %d", rear(que));
break;
case 7: exit(0);
break;
default: printf("\n Wrong Choice!");
break;
}
printf("\ndo u want to cont... ");

~ 324 ~
 }while('y'==getch());
}
Output:
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL
[Link] ELE
[Link] ELE
[Link]
enter ur choice : 1

enter the value 23

23 enqueued to que

do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL
[Link] ELE
[Link] ELE
[Link]
enter ur choice :
1

enter the value 45

45 enqueued to que

~ 325 ~
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL
[Link] ELE
[Link] ELE
[Link]
enter ur choice : 3

IsEmpty : 0
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL
[Link] ELE
[Link] ELE
[Link]
enter ur choice :
4

IsFull : 0
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL

~ 326 ~
[Link] ELE
[Link] ELE
[Link]
enter ur choice : 5

Front element: 23
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link] FULL
[Link] ELE
[Link] ELE
[Link]
enter ur choice : 6

Last element : 45
do u want to cont...

3.5.4 Demonstration of Queue- using LinkedList

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{int data;
struct node *next;
}*p,*tmp,*tmp1;
void insert_end(int);
void delete_beg();

~ 327 ~
void display();
void isEmpty();
int main()
{
int val,n;
p=NULL;
do
{printf("\n************************* MENU ************************");
printf("\[Link]");
printf("\[Link]");
printf("\[Link] EMPTY");
printf("\[Link]");
printf("\[Link]");
printf("\nenter ur choice : ");
scanf("%d",&n);
switch(n)
{case 1: printf("\nenter the value ");
scanf("%d",&val);
insert_end(val);
break;
case 2:
delete_beg();
break;
case 3:
isEmpty();
break;
case 4: display();
break;
case 5: exit(0);
break;
default: printf("\n Wrong Choice!");

~ 328 ~
 break;
}
printf("\ndo u want to cont... ");
}while('y'==getch());

void insert_end(int ele)

{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=NULL;
if(p==NULL)
p=tmp1;
else
{
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=tmp1;
}
}

void insert_beg(int ele)

{
tmp=p;
tmp1=(struct node*)malloc(sizeof(struct node));
tmp1->data=ele;
tmp1->next=p;
p=tmp1;
}

~ 329 ~
void isEmpty(){

if(p==NULL)
printf("Queue is Empty");
else
{
printf("Queue is Not Empty");
}
}

void ldelete(int ele)

{
tmp=p;
struct node *pre=tmp;
while(tmp!=NULL)
{if(tmp->data==ele)
{ if(tmp==p)
{p=tmp->next;
free(tmp);
return;
}
else
{pre->next=tmp->next;
free(tmp);
return;
}
}
else
{ pre=tmp;
tmp=tmp->next;

~ 330 ~
 }
}
printf("\n no match found!! ");
}

void delete_beg()
{
tmp=p;
if(p==NULL)
printf("\n no element to be deleted!! ");
else
{
printf("\nelement deleted - %d", p->data);
p=p->next;
}

void delete_end()
{
tmp=p;
struct node* pre;
if(p==NULL)
printf("\n no element to be deleted!! ");
else if(p->next==NULL)
{
printf("\nelement deleted - %d", p->data);
p=NULL;

~ 331 ~
 else
{
while(tmp->next!=NULL){
pre=tmp;
tmp=tmp->next;
}
pre->next=NULL;
printf("\nelement deleted - %d", tmp->data);
}
}

void display()
{
tmp=p;
while(tmp!=NULL)
{printf("\n %d",tmp->data);
tmp=tmp->next;
}
}

Output

************************* MENU ************************

[Link]
[Link]
[Link] EMPTY
[Link]
[Link]
enter ur choice : 1

enter the value 45

~ 332 ~
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link]
[Link]
enter ur choice :
1

enter the value 67

do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link]
[Link]
enter ur choice : 4

45
67
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link]
[Link]

~ 333 ~
enter ur choice : 3
Queue is Not Empty
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link]
[Link]
enter ur choice : 2

element deleted - 45
do u want to cont...
************************* MENU ************************
[Link]
[Link]
[Link] EMPTY
[Link]
[Link]
enter ur choice : 4

67
do u want to cont...

Learning Outcome 3.6 Use Trees Data Structure Using C

Programming Techniques

3.6.1 Description of tree data structure

~ 334 ~
Recursively, we find that a tree is a collection of n nodes, one of which is the root, and n-1
edges. That there are n-1 and every node except the root has one parent.
A tree is a collection of nodes. A tree consists of a distinguished node r, called the root, and
zero or more (sub) trees T1, T2… TK, each of whose roots are connected by a directed edge to r.
the root of each subtree is said to be a child of r, and r is the parent of each subtree root. Every
node except the root has one parent. Nodes with no children are known as leaves. Nodes
with the same parent are siblings. Grandparents are grandchild relations can be defined in a
similar manner.
A tree is also one of the data structures that represent hierarchical data. Suppose we want to show
the employees and their positions in the hierarchical form then it can be represented as shown
below:
A Tree is a non-linear data structure that consists of various linked nodes. It has a hierarchical
tree structure that forms a parent-child relationship. The diagrammatic representation of
a tree data structure is shown below:

~ 335 ~
For example, the posts of employees are arranged in a tree data structure like managers, officers,
clerk. In the above figure, A represents a manager, B and C represent the officers, and other
nodes represent the clerks.
3.6.2 General tree
The general tree is one of the types of tree data structure. In the general tree, a node can have
either 0 or maximum n number of nodes. There is no restriction imposed on the degree of the
node (the number of nodes that a node can contain). The topmost node in a general tree is known
as a root node. The children of the parent node are known as subtrees.

~ 336 ~
The above tree shows the organization hierarchy of some company. In the above
structure, john is the CEO of the company, and John has two direct reports named
as Steve and Rohan. Steve has three direct reports named Lee, Bob, Ella where Steve is a
manager. Bob has two direct reports named Sal and Emma. Emma has two direct reports
named Tom and Raj. Tom has one direct report named Bill. This particular logical structure is
known as a Tree. Its structure is similar to the real tree, so it is named a Tree. In this structure,

~ 337 ~
the root is at the top, and its branches are moving in a downward direction. Therefore, we can
say that the Tree data structure is an efficient way of storing the data in a hierarchical way.
3.6.3 Important Terms

Following are the important terms with respect to tree.

 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one root per tree and
one path from the root node to any node.
 Parent − Any node except the root node has one edge upward to a node called parent.
 Child − The node below a given node connected by its edge downward is called its child
node.
 Leaf − The node which does not have any child node is called the leaf node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control is on the node.
 Traversing − Traversing means passing through nodes in a specific order.
 Levels − Level of a node represents the generation of a node. If the root node is at level
0, then its next child node is at level 1, its grandchild is at level 2, and so on.

~ 338 ~
  keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.
 Internal nodes: A node has at least one child node known as an internal
 Ancestor node: An ancestor of a node is any predecessor node on a path from the root to
that node. The root node doesn't have any ancestors. In the tree shown in the above
image, nodes 1, 2, and 5 are the ancestors of node 10.
 Descendant: The immediate successor of the given node is known as a descendant of a
node. In the above figure, 10 is the descendant of node 5.
3.6.4 Applications of trees

The following are the applications of trees:

 Storing naturally hierarchical data: Trees are used to store the data in the hierarchical
structure. For example, the file system. The file system stored on the disc drive, the file
and folder are in the form of the naturally hierarchical data and stored in the form of
trees.
 Organize data: It is used to organize data for efficient insertion, deletion and searching.
For example, a binary tree has a logN time for searching an element.
 Trie: It is a special kind of tree that is used to store the dictionary. It is a fast and efficient
way for dynamic spell checking.
 Heap: It is also a tree data structure implemented using arrays. It is used to implement
priority queues.
 B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to implement
indexing in databases.
 Routing table: The tree data structure is also used to store the data in routing tables in
the routers.
3.6.5 Binary Tree
 Hierarchical Data Structures using C

 Topmost element is known as the root of the tree

 Every node can have at most 2 children in the binary tree
 Can access elements randomly using index
Eg: File system hierarchy

~ 339 ~
 a. Types of Binary Tree

There are five types of Binary tree:

 Full/ proper/ strict Binary tree
 Complete Binary tree
 Perfect Binary tree
 Degenerate Binary tree
 Balanced Binary tree
A. Full/ proper/ strict Binary tree

The full binary tree is also known as a strict binary tree. The tree can only be considered as the
full binary tree if each node must contain either 0 or 2 children. The full binary tree can also be
defined as the tree in which each node must contain 2 children except the leaf nodes.
Let's look at the simple example of the Full Binary tree

In the above tree, we can observe that each node is either containing zero or two children;
therefore, it is a Full Binary tree.
B. Complete Binary Tree

The complete binary tree is a tree in which all the nodes are completely filled except the last
level. In the last level, all the nodes must be as left as possible. In a complete binary tree, the
nodes should be added from the left.
Let's create a complete binary tree.

~ 340 ~
The above tree is a complete binary tree because all the nodes are completely filled, and all the
nodes in the last level are added at the left first.
C. Perfect Binary Tree

A tree is a perfect binary tree if all the internal nodes have 2 children, and all the leaf nodes are at
the same level.
Let's look at a simple example of a perfect binary tree.

The below tree is not a perfect binary tree because all the leaf nodes are not at the same
level.

~ 341 ~
 D. Degenerate Binary Tree

The degenerate binary tree is a tree in which all the internal nodes have only one children.
Let's understand the Degenerate binary tree through examples.

The above tree is a degenerate binary tree because all the nodes have only one child. It is also
known as a right-skewed tree as all the nodes have a right child only.

~ 342 ~
The above tree is also a degenerate binary tree because all the nodes have only one child. It is
also known as a left-skewed tree as all the nodes have a left child only.
E. Balanced Binary Tree

The balanced binary tree is a tree in which both the left and right trees differ by atmost 1. For
example, AVL and Red-Black trees are balanced binary tree.

Let's understand the balanced binary tree through examples.

The above tree is a balanced binary tree because the difference between the left subtree and right
subtree is zero.

~ 343 ~
The above tree is not a balanced binary tree because the difference between the left subtree and
the right subtree is greater than 1.
For more Info, use this link: [Link]

b. Common traversal methods

A. Depth First Traversals:

 preorder: root-left-right (A B D G H C E F)
Traverses a tree in a pre-order manner.
 postorder: left-right-root (G H D B C E F A)

~ 344 ~
 Traverses a tree in a post-order manner.
 inorder: left-root-right (G D H B A C E F)
Traverses a tree in an in-order manner.
B. Breadth First or Level Order Traversal: Traverses a tree Level by Level

Breadth First Traversal: 1 2 3 4 5

Implementation of Breadth First Traversal in C:

// Recursive C program for level

// order traversal of Binary Tree
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child and a pointer to right child */
struct node {
int data;
struct node *left, *right;
};
/* Function prototypes */
void printCurrentLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printCurrentLevel(root, i);
}
/* Print nodes at a current level */

~ 345 ~
void printCurrentLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1) {
printCurrentLevel(root->left, level - 1);
printCurrentLevel(root->right, level - 1);
}
}
/* Compute the "height" of a tree -- the number of nodes along the longest path from the
root node down to the farthest leaf node.*/
int height(struct node* node)
{
if (node == NULL)
return 0;
else {
/* compute the height of each subtree */
int lheight = height(node->left);
int rheight = height(node->right);
/* use the larger one */
if (lheight > rheight)
return (lheight + 1);
else
return (rheight + 1);
}
}
/* Helper function that allocates a new node with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}
/* Driver program to test above functions*/
~ 346 ~
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("Level Order traversal of binary tree is \n");

printLevelOrder(root);

return 0;
}

C. Depth First Traversals:

(a) Inorder (Left, Root, Right) : 4 2 5 1 3

(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
Implementation of Depth First Traversal in C:
// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>
/* A binary tree node has data, pointer to left child and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};
/* Helper function that allocates a new node with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

~ 347 ~
 return (node);
}
/* Given a binary tree, print its nodes according to the "bottom-up" postorder traversal.
*/
void printPostorder(struct node* node)
{
if (node == NULL)
return;
// first recur on left subtree
printPostorder(node->left);
// then recur on right subtree
printPostorder(node->right);

// now deal with the node

printf("%d ", node->data);
}
/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;
/* first recur on left child */
printInorder(node->left);
/* then print the data of node */
printf("%d ", node->data);
/* now recur on right child */
printInorder(node->right);
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left subtree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
/* Driver program to test above functions*/
int main()
{
struct node* root = newNode(1);
root->left = newNode(2);

~ 348 ~
 root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);

printf("\nPreorder traversal of binary tree is \n");

printPreorder(root);

printf("\nInorder traversal of binary tree is \n");

printInorder(root);

printf("\nPostorder traversal of binary tree is \n");

printPostorder(root);

getchar();
return 0;
}

Advantages
 Can represent data with some relationship
 Insertion and search are much efficient
Disadvantages
 Sorting is difficult
 Not much flexible
Applications
 File system hierarchy
 Multiple variations of the binary tree have a wide variety of applications
c. Demonstration of Binary Tree

#include<stdio.h>
#include<conio.h>

~ 349 ~
#include<stdlib.h>

struct bst
{
int data;
struct bst *left;
struct bst *right;
};
struct bst * insert(struct bst *,int);
void inorder(struct bst *);
void preorder(struct bst *);
void postorder(struct bst *);
int main ()
{
struct bst *r=NULL;
r=insert(r,30);
r=insert(r,15);
r=insert(r,10);
r=insert(r,20);
r=insert(r,40);
r=insert(r,5);
r=insert(r,45);
r=insert(r,35);
printf("\n display element in inorder:-");
inorder(r);
printf("\n display element in preorder:-");
preorder(r);
printf("\n display element in postorder:-");
postorder(r);
return 1;

~ 350 ~
}
struct bst * insert(struct bst *q,int val)
{
struct bst *tmp;
tmp=(struct bst *)malloc(sizeof(struct bst));

if(q==NULL)
{
tmp->data=val;
tmp->left=tmp->right=NULL;
return tmp;
}
else
{
if(val<(tmp->data))
{
q->left=insert(q->left,val);
}
else
{
q->right=insert(q->right,val);
}
}
return q;
}
void inorder(struct bst *q)
{
if(q==NULL)
{
return;
}

~ 351 ~
 inorder(q->left);
printf(" %d ",q->data);
inorder(q->right);
}
void preorder(struct bst *q)
{

if(q!=NULL)
{
printf(" %d ",q->data);
preorder(q->left);
preorder(q->right);
}

void postorder(struct bst *q)

{

if(q!=NULL)
{
postorder(q->left);
postorder(q->right);
printf(" %d ",q->data);

}
Output

~ 352 ~
display element in inorder:- 35 45 5 40 20 10 15 30
display element in preorder:- 30 15 10 20 40 5 45 35
display element in postorder:- 35 45 5 40 20 10 15 30
--------------------------------
Process exited after 0.04906 seconds with return value 1
Press any key to continue . . .

3.6.6 Binary Search Tree

 A binary tree with the additional restriction

 Restriction:
o The left child must always be less than the root node
o The right child must always be greater than the root node
 Insertion, Deletion, Search is much more efficient than a binary tree

a. Advantages

 Maintains order in elements

 Can easily find the min and max nodes in the tree
 In order traversal gives sorted elements
b. Disadvantages

~ 353 ~
  Random access not possible
 Ordering adds complexity
c. Applications

 Suitable for sorted hierarchical data

d. Demonstration of Binary Search Tree

#include<stdio.h>
#include<stdlib.h>
struct bst
{
int data;
struct bst *left;
struct bst *right;
};

struct bst * insert(struct bst *q,int val)

{
struct bst * temp;
if(q==NULL)
{
temp=(struct bst *)malloc(sizeof(struct bst));
temp->data=val;
temp->left=NULL;
temp->right=NULL;
q=temp;
}
else
{
if(val<q->data)
{
q->left=insert(q->left,val);
}

~ 354 ~
 else
{
q->right=insert(q->right,val);
}
}
return q;
}
void inorder(struct bst *q)
{

if(q==NULL)
{
return;
}
inorder(q->left);
printf("%d\t" , q->data);
inorder(q->right);
}
struct bst *search(struct bst *p, int key, struct bst **y)
{
struct bst *temp;
if( p == NULL)
return(NULL);
temp=p;
*y = NULL;
while( temp != NULL)
{
if(temp->data == key)
return(temp);
else
{

~ 355 ~
 *y = temp; /*store this pointer as root */
if(temp->data > key)
temp = temp->left;
else
temp = temp->right;
}
}
return(NULL);
}

/* A function to delete the node whose data value is given */

struct bst * del(struct bst *p,int val)
{
struct bst *x, *y, *temp;
x = search(p,val,&y);
if( x==NULL)
{
printf("The node does not exists\n");
return(p);
}
else
{
/* this code is for deleting root node*/
if(x==p)
{
temp = x->left;
y = x->right;
p = temp;
while(temp->right != NULL)
temp = temp->right;
temp->right=y;

~ 356 ~
 free(x);
return(p);
}
/* this code is for deleting node having both children */
if( x->left!=NULL && x->right!=NULL)
{

if(y->left==x)
{
temp=x->left;
y->left=x->left;
while(temp->right != NULL)
temp = temp->right;
temp->right=x->right;
x->left=NULL;
x->right=NULL;
}
else
{
temp = x->right;
y->right = x->right;
while(temp->left!= NULL)
temp = temp->left;
temp->left=x->left;
x->left=NULL;
x->right=NULL;
}

free(x);
return(p);
}

~ 357 ~
/* this code is for deleting a node with one child*/
if(x->left== NULL && x->right!= NULL)
{
if(y->left== x)
y->left=x->right;
else
y->right= x->right;
x->right= NULL;
free(x);
return(p);
}

if( x->left!= NULL && x->right== NULL)

{
if(y->left == x)
y->left= x->left ;
else
y->right= x->left;
x->left= NULL;
free(x);
return(p);
}
/* this code is for deleting a node with no child*/
if(x->left==NULL && x->right== NULL)
{
if(y->left== x)
y->left= NULL ;
else
y->right= NULL;
free(x);
return(p);

~ 358 ~
 }
}
}
int main()
{
struct bst *root;
root=NULL; int n,val,num;
printf("\n enter no. of term:- ");
scanf("%d",&n);
while(n!=0)
{
printf("\n enter element:- ");
scanf("%d",&val);
root=insert(root,val);
n--;
}
printf("\n display element:-.......");
inorder(root);
printf("\n enter element to be deleted:- ");
scanf("%d",&num);
del(root,num);
printf("\n display element after deleted:-.......");
inorder(root);
return 1;

}
Output:
enter no. of term:- 5
enter element:- 12
enter element:- 34
enter element:- 56

~ 359 ~
enter element:- 10
enter element:- 23
display element:-.......10 12 23 34 56
enter element to be deleted:- 23
display element after deleted:-.......10 12 34 56
3.6.7 AVL Tree
AVL tree is a binary search tree in which the difference of heights of left and right subtrees of
any node is less than or equal to one. The technique of balancing the height of binary trees was
developed by Adelson, Velskii, and Landi and hence given the short form as AVL tree or
Balanced Binary Tree.
It is one of the types of the binary tree, or we can say that it is a variant of the binary search tree.
AVL tree satisfies the property of the binary tree as well as of the binary search tree.
An AVL tree can be defined as follows:
Let T be a non-empty binary tree with TL and TR as its left and right subtrees. The tree is height
balanced if:
 TL and TR are height balanced
 hL - hR <= 1, where hL - hR are the heights of TL and TR
The Balance factor of a node in a binary tree can have value 1, -1, 0, depending on whether the
height of its left subtree is greater, less than or equal to the height of the right subtree.
a. Advantages of AVL Tree

Since AVL trees are height balance trees, operations like insertion and deletion have low time
complexity. Let us consider an example:
If you have the following tree having keys 1, 2, 3, 4, 5, 6, 7 and then the binary tree will be like
the second figure:

~ 360 ~
To insert a node with a key Q in the binary tree, the algorithm requires seven comparisons, but if
you insert the same key in AVL tree, from the above 1st figure, you can see that the algorithm
will require three comparisons.

b. Representation of AVL Tree

Struct AVLNode
{
int data;
struct AVLNode *left, *right;
int balfactor;
};
c. Algorithm for different Operations on AVL
A. For Insertion

Step 1: First, insert a new element into the tree using BST's (Binary Search Tree) insertion logic.
Step 2: After inserting the elements you have to check the Balance Factor of each node.

~ 361 ~
Step 3: When the Balance Factor of every node will be found like 0 or 1 or -1 then the algorithm
will proceed for the next operation.
Step 4: When the balance factor of any node comes other than the above three values then the
tree is said to be imbalanced. Then perform the suitable Rotation to make it balanced and then
the algorithm will proceed for the next operation.
B. For Deletion:

Step 1: Firstly, find that node where k is stored

Step 2: Secondly delete those contents of the node (Suppose the node is x)
Step 3: Claim: Deleting a node in an AVL tree can be reduced by deleting a leaf. There are three
possible cases:
 When x has no children then, delete x
 When x has one child, let x' becomes the child of x.
 Notice: x' cannot have a child, since subtrees of T can differ in height by at most
one:
o then replace the contents of x with the contents of x'
o then delete x' (a leaf)
Step 4: When x has two children,
 then find x's successor z (which has no left child)
 then replace x's contents with z's contents, and
 delete z
In all of the three cases, you will end up removing a leaf.
d. AVL Rotations

To balance itself, an AVL tree may perform the following four kinds of rotations −
 Left rotation

 Right rotation

 Left-Right rotation

 Right-Left rotation

The first two rotations are single rotations and the next two rotations are double rotations. To
have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's
understand them one by one.

~ 362 ~
 A. Left Rotation

If a tree becomes unbalanced, when a node is inserted into the right subtree of the right subtree,
then we perform a single left rotation −

In our example, node A has become unbalanced as a node is inserted in the right subtree of A's
right subtree. We perform the left rotation by making A the left-subtree of B.

B. Right Rotation

AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree.
The tree then needs a right rotation.

As depicted, the unbalanced node becomes the right child of its left child by performing a right
rotation.

C. Left-Right Rotation

Double rotations are slightly complex version of already explained versions of rotations. To
understand them better, we should take note of each action performed while rotation. Let's first

~ 363 ~
check how to perform Left-Right rotation. A left-right rotation is a combination of left rotation
followed by right rotation.

State Action

A node has been inserted into the right subtree of the left subtree. This
makes C an unbalanced node. These scenarios cause AVL tree to
perform left-right rotation.

We first perform the left rotation on the left subtree of C. This makes A,
the left subtree of B.

Node C is still unbalanced, however now, it is because of the left-

subtree of the left-subtree.

~ 364 ~
 We shall now right-rotate the tree, making B the new root node of this
subtree. C now becomes the right subtree of its own left subtree.

The tree is now balanced.

D. Right-Left Rotation

The second type of double rotation is Right-Left Rotation. It is a combination of right rotation
followed by left rotation.

State Action

A node has been inserted into the left subtree of the right subtree. This
makes A, an unbalanced node with balance factor 2.

~ 365 ~
 First, we perform the right rotation along C node, making C the right
subtree of its own left subtree B. Now, B becomes the right subtree
of A.

Node A is still unbalanced because of the right subtree of its right

subtree and requires a left rotation.

A left rotation is performed by making B the new root node of the

subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

For more Info, Use this Link:

[Link]
3.6.8 Heap
 Binary Heap can be visualized array as a complete binary tree

~ 366 ~
  Arr[0] element will be treated as root
 length(A) – size of array
 heapSize(A) – size of heap
 Generally used when we are dealing with minimum and maximum elements
 For ith node
(i-1)/2 Parent
(2*i)+1 Left child
(2*i)+2 Right Child
a. Advantages

 Can be of 2 types: min heap and max heap

 Min heap keeps smallest and element and top and max keeps the largest
 O(1) for dealing with min or max elements
b. Disadvantages

 Random access not possible

 Only min or max element is available for accessibility
c. Applications

 Suitable for applications dealing with priority

 Scheduling algorithm
 Caching
d. Implementation

#include<stdio.h>

#define MAX_SIZE 15

// returns the index of the parent node

int parent(int i) {
return (i - 1) / 2;
}

// return the index of the left child

int left_child(int i) {
return 2*i + 1;
}

// return the index of the right child

int right_child(int i) {

~ 367 ~
 return 2*i + 2;
}

void swap(int *x, int *y) {

int temp = *x;
*x = *y;
*y = temp;
}

// insert the item at the appropriate position

void insert(int a[], int data, int *n) {
if (*n >= MAX_SIZE) {
printf("%s\n", "The heap is full. Cannot insert");
return;
}
// first insert the time at the last position of the array
// and move it up
a[*n] = data;
*n = *n + 1;

// move up until the heap property satisfies

int i = *n - 1;
while (i != 0 && a[parent(i)] < a[i]) {
swap(&a[parent(i)], &a[i]);
i = parent(i);
}
}

// moves the item at position i of array a

// into its appropriate position
void max_heapify(int a[], int i, int n){
// find left child node
int left = left_child(i);

// find right child node

int right = right_child(i);

// find the largest among 3 nodes

int largest = i;

// check if the left node is larger than the current node

if (left <= n && a[left] > a[largest]) {
largest = left;
}

// check if the right node is larger than the current node

if (right <= n && a[right] > a[largest]) {
largest = right;
}

// swap the largest node with the current node

// and repeat this process until the current node is larger than
// the right and the left node

~ 368 ~
 if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
max_heapify(a, largest, n);
}

// converts an array into a heap

void build_max_heap(int a[], int n) {
int i;
for (i = n/2; i >= 0; i--) {
max_heapify(a, i, n);
}
}

// returns the maximum item of the heap

int get_max(int a[]) {
return a[0];
}

// deletes the max item and return

int extract_max(int a[], int *n) {
int max_item = a[0];

// replace the first item with the last item

a[0] = a[*n - 1];
*n = *n - 1;

// maintain the heap property by heapifying the

// first item
max_heapify(a, 0, *n);
return max_item;
}

// prints the heap

void print_heap(int a[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d\n", a[i]);
}
printf("\n");
}

int main() {
int n = 10;
int a[MAX_SIZE];
a[1] = 10; a[2] = 12; a[3] = 9; a[4] = 78; a[5] = 33; a[6] = 21; a[7] =
35; a[8] = 29; a[9] = 5; a[10] = 66;
build_max_heap(a, n);
insert(a, 55, &n);
insert(a, 56, &n);

~ 369 ~
 insert(a, 57, &n);
insert(a, 58, &n);
insert(a, 100, &n);
print_heap(a, n);
return 0;
}

Learning outcome 3.7 Use Hashing Data Structure Using C

Programming Techniques

3.7.1 Description of hashing data structure

 Uses special Hash function

 A hash function maps element to an address for storage
 This provides constant-time access
 Collision is handled by collision resolution techniques
 Collision resolution technique
o Chaining
o Open Addressing
a. Advantages

 The hash function helps in fetching element in constant time

 An efficient way to store elements
b. Disadvantages

 Collision resolution increases complexity

c. Applications

 Suitable for the application needs constant time fetching

3.7.2 Implementation

// Implementing hash table in C

#include <stdio.h>
#include <stdlib.h>

struct set

~ 370 ~
{
int key;
int data;
};
struct set *array;
int capacity = 10;
int size = 0;
int i;
int hashFunction(int key)
{
return (key % capacity);
}
int checkPrime(int n)
{
int i;
if (n == 1 || n == 0)
{
return 0;
}
for (i = 2; i < n / 2; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}
int getPrime(int n)
{
if (n % 2 == 0)
{
n++;
}
while (!checkPrime(n))
{
n += 2;
}
return n;
}
void init_array()
{
capacity = getPrime(capacity);
array = (struct set *)malloc(capacity * sizeof(struct set));
for ( i = 0; i < capacity; i++)
{

~ 371 ~
 array[i].key = 0;
array[i].data = 0;
}
}

void insert(int key, int data)

{
int index = hashFunction(key);
if (array[index].data == 0)
{
array[index].key = key;
array[index].data = data;
size++;
printf("\n Key (%d) has been inserted \n", key);
}
else if (array[index].key == key)
{
array[index].data = data;
}
else
{
printf("\n Collision occured \n");
}
}

void remove_element(int key)

{
int index = hashFunction(key);
if (array[index].data == 0)
{
printf("\n This key does not exist \n");
}
else
{
array[index].key = 0;
array[index].data = 0;
size--;
printf("\n Key (%d) has been removed \n", key);
}
}
void display()
{
int i;
for (i = 0; i < capacity; i++)
{
if (array[i].data == 0)

~ 372 ~
 {
printf("\n array[%d]: / ", i);
}
else
{
printf("\n key: %d array[%d]: %d \t", array[i].key, i, array[i].data);
}
}
}

int size_of_hashtable()
{
return size;
}

int main()
{
int choice, key, data, n;
int c = 0;
init_array();

do
{
printf("[Link] item in the Hash Table"
"\[Link] item from the Hash Table"
"\[Link] the size of Hash Table"
"\[Link] a Hash Table"
"\n\n Please enter your choice: ");

scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter key -:\t");
scanf("%d", &key);
printf("Enter data -:\t");
scanf("%d", &data);
insert(key, data);
break;
case 2:
printf("Enter the key to delete-:");
scanf("%d", &key);
remove_element(key);
break;
case 3:
n = size_of_hashtable();

~ 373 ~
 printf("Size of Hash Table is-:%d\n", n);
break;
case 4:
display();

break;

default:

printf("Invalid Input\n");
}

printf("\nDo you want to continue (press 1 for yes): ");

scanf("%d", &c);

} while (c == 1);
}
Output:

~ 374 ~
~ 375 ~
~ 376 ~
Learning outcome 3.8 Use Graph Data Structure Using C
Programming Techniques

3.8.1 Introduction to graph in data structure

 Basically it is a group of edges and vertices

 Graphs are those types of non-linear data structures which consist of a definite
quantity of vertices and edges. The vertices or the nodes are involved in storing data
and the edges show the vertices relationship. The difference between a graph to a
tree is that in a graph there are no specific rules for the connection of nodes. Real-
life problems like social networks, telephone networks, etc. can be represented
through the graphs.
a. Advantages

 finding connectivity
 Shortest path

~ 377 ~
  min cost to reach from 1 pt to other
 Min spanning tree
b. Disadvantages

 Storing graph (Adjacency list and Adjacency matrix) can lead to complexities
c. Graph representation

 G(V, E): where V(G) represents a set of vertices and E(G) represents a set of
edges

3.8.2 Graph Terminology

 A graph can be directed or undirected

 A graph can be connected or disjoint

 A graph may be directed, meaning that the line segments join points only in one
direction.

 A graph also might be undirected, meaning that line segments join point from either
direction.

~ 378 ~
 When we see edge with no arrows, you may presume the graph is undirected, or
bidirectional, when an edge connects two vertices or nodes, we say that they are
‘adjacent’.
 E is adjacent to F, A, B and D, but not C. Sure, you can still get to C from E, but not
directly.
 Unlike trees, which are special types of graphs, graphs may have cycles, meaning
that children can be the parents of their ‘ancestor’.

 A collection of individual points (or edges) in a graph may represent a path. A path
is just a way of getting from one node to another node.
 We can also assign ‘weights’ or values to edges.

~ 379 ~
In such case, we have a weighted graph, the weights can represent cost, distance….
3.8.3 Graph to a Tree
 the tree is generated by traversing the graph
 the same node in the graph may appear repeatedly in the tree
 the arrangement of the tree depends on the traversal strategy (search method)
 the initial state becomes the root node of the tree
 in the fully expanded tree, the goal states are the leaf nodes
 cycles in graphs may result in infinite branches
Example:

~ 380 ~
3.8.4 Graph Traversal
Graph traversal is a technique to visit each nodes of a graph G. It is also use to calculate the
order of vertices in traverse process. We visit all the nodes starting from one node which is
connected to each other without going into loop.
Basically in graph it may happen sometime visitors can visit one node more than once. So,
this may cause the going the visitors into infinite loop. So, to protect from this infinite loop
condition we keep record of each vertex. Like if visitors visited vertex then the value will be
zero if not, then one.
There are two graph traversal techniques
 Breadth-first search
 Depth-first search
a. Breadth First Search (BFS) Traversal in Data Structure

Breadth-first search graph traversal techniques use a queue data structure as an auxiliary
data structure to store nodes for further processing. The size of the queue will be the
maximum total number of vertices in the graph.
Steps to implement BFS traversal
Step 1 – First define a Queue of size n. Where n is the total number of vertices in the graph.
Step 2 – Select any vertex which is a starting point from where traversal will start.

~ 381 ~
Step 3 – Visit starting vertex and insert it into the Queue.
Step 4 – Visit all the non-visited adjacent vertices which is connected to it and insert all
non-visited vertices into the Queue.
Step 5 – When there is no new vertex to be visited from the element which is top in a queue,
Remove the top element which is the vertex from the queue.
Step 6 – Repeat steps 4 and 6 until the queue becomes empty.
Step 7 – When all elements removed from the queue, then produce the final spanning tree
by removing unused edges from the graph.
Example of BFS Graph Traversal
 Initialize the queue

 We start visiting from vertex 12 that can be considered as starting node, and
mark it as visited.

~ 382 ~
 Now we will see an unvisited adjacent node from 12. In this example, we have
three nodes and we can visit anyone. here we are traversing from left to right.
We choose 5 and mark it as visited and enqueue it.

 Next, visit the unvisited adjacent node from 12 to 23 . We mark it as visited and
enqueue it.

 Next, the unvisited adjacent node from 12 is 3. We mark it as visited and

enqueue it.

~ 383 ~
  Now, all the connected adjacent node from 12 is traversed and no unvisited
adjacent nodes left. So, we dequeue and find all connect vertex from 5.

 From 5 we have 25 as unvisited adjacent node. We mark it as visited and enqueue it.
Now if all nodes visited, we will dequeue all nodes from queue.
 So BFS Traversal output is: 12, 5, 23, 3, 25
Complexity Analysis of BFS
Time complexity: O(V + E), where V is the number of vertices and E is the number of
edges in the graph.
Space Complexity: O(V).
Since, an extra visited array is needed of size V.
Applications of BFS
 Finding the Shortest path in an unweighted graph

~ 384 ~
  Find a solution to a game with the least number of moves. In such a scenario each
state of the game can be represented by a node and state transitions as edges
 Finding Connected Components in an unweighted graph
 Level Order Traversal in Tree
 Find the shortest paths in graphs with weights 0/1
b. Depth First Search(DFS) Traversal in Data Structure

DFS stands for Depth First Search, is one of the graph traversal algorithms that uses Stack
data structure. In DFS Traversal go as deep as possible of the graph and then backtrack once
reached a vertex that has all its adjacent vertices already visited.
Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a
stack data structure to remember to get the next vertex to start a search, when a dead end
occurs in any iteration.
DFS traversal for tree and graph is similar but the only difference is that a graph can
have a cycle but the tree does not have any cycle. So in the graph we have additional
array which keeps the record of visited array to protect from infinite loop and not visited
again the visited node.
Steps to implement Depth First Traversal
Step 1 – Visit all adjacent unvisited vertex. Mark it as visited. Print it and Push it in a stack.
Step 2 − If no adjacent vertex is found, pop up a vertex from the stack.
Step 3 − Repeat Step 1 and Step 2 until the stack is empty.
Graph Traversal using DFS Technique
 Initialize the stack

~ 385 ~
 Mark 12 as visited and push into stack. Now Explore any unvisited adjacent
node from 12. In our example We have three nodes. We can pick any of them.
Here we are going to pick 5.

 Mark 5 as visited and put it onto the stack. Explore any unvisited adjacent node
from 5. Both 12 and 25 are adjacent to 5 but we are concerned for unvisited
nodes only.

 Visit 25 and mark it as visited and put onto the stack. Here, we
have 23 and 3 nodes, which are adjacent to 25 and both are unvisited.

~ 386 ~
 We choose 3, mark it as visited and put onto the stack. Here 3 does not have any
unvisited adjacent node. So, we pop 3 from the stack.

 We check the stack top for return to the previous node and check if it has any
unvisited nodes. Here, we find 25 to be on the top of the stack.

~ 387 ~
  Only unvisited adjacent node is from D is 23 now. So we visit 23, mark it as
visited and put it onto the stack.

 Output of DFS Traversal will be: 3, 23, 25, 5, 12

Complexity Analysis
Time complexity: O(V + E), where V is the number of vertices and E is the number of
edges in the graph.
Space Complexity: O(V).
Since, an extra visited array is needed of size V.
Application of DFS
 Find a path from the source vertex to other vertices
 Find the connected components in a graph
 Topological Sorting
 Find bridges and articulation points in a graph
 Find LCA (Lowest Common Ancestor) of two nodes in a graph
 Find cycles in a directed and undirected graph
Applications
 Suitable for a circuit network
 Suitable for applications like Facebook, LinkedIn, etc
 Medical science

~ 388 ~
Exercises
1) How can we describe an array in the best possible way?
A. The Array shows a hierarchical structure.
B. Arrays are immutable.
C. Container that stores the elements of similar types
D. The Array is not a data structure
2) Which of the following is the correct way of declaring an array?
A. int javatpoint[10];
B. int javatpoint;
C. javatpoint{20};
D. array javatpoint[10];
3) How can we initialize an array in C language?
A. int arr[2]=(10, 20)
B. int arr(2)={10, 20}
C. int arr[2] = {10, 20}
D. int arr(2) = (10, 20)
4) Which of the following is the advantage of the array data structure?
A. Elements of mixed data types can be stored.
B. Easier to access the elements in an array
C. Index of the first element starts from 1.
D. Elements of an array cannot be sorted
5) Which of the following highly uses the concept of an array?
A. Binary Search tree
B. Caching
C. Spatial locality
D. Scheduling of Processes
6) Which of the following is the disadvantage of the array?
A. Stack and Queue data structures can be implemented through an array.
B. Index of the first element in an array can be negative
C. Wastage of memory if the elements inserted in an array are lesser than the allocated size

~ 389 ~
 D. Elements can be accessed sequentially.
7) What is the output of the below code?

#include <stdio.h>
int main()
{
int arr[5]={10,20,30,40,50};
printf("%d", arr[5]);
return 0;
}
A. Garbage value
B. 10
C. 50
D. None of the above
8) Which one of the following is the size of int arr[9] assuming that int is of 4 bytes?
A. 9
B. 36
C. 35
D. None of the above
9) Which one of the following is the process of inserting an element in the stack?
A. Insert
B. Add
C. Push
D. None of the above
10) When the user tries to delete the element from the empty stack then the condition is
said to be a ____
A. Underflow
B. Garbage collection
C. Overflow
D. None of the above
11) If the size of the stack is 10 and we try to add the 11th element in the stack then the
condition is known as___

~ 390 ~
 A. Underflow
B. Garbage collection
C. Overflow
D. None of the above
12) Which one of the following is not the application of the stack data structure
A. String reversal
B. Recursion
C. Backtracking
D. Asynchronous data transfer

13) Which data structure is mainly used for implementing the recursive algorithm?
A. Queue
B. Stack
C. Binary tree
D. Linked list
14) Which data structure is required to convert the infix to prefix notation?
A. Stack
B. Linked list
C. Binary tree
D. Queue
15) Which of the following is not the correct statement for a stack data structure?
A. Arrays can be used to implement the stack
B. Stack follows FIFO
C. Elements are stored in a sequential manner
D. Top of the stack contains the last inserted element
16) If the elements '1', '2', '3' and '4' are added in a stack, so what would be the order for
the removal?
A. 1234
B. 2134

~ 391 ~
 C. 4321
D. None of the above
17) The minimum number of stacks required to implement a stack is __
A. 1
B. 3
C. 2
D. 5
18) Which one of the following node is considered the top of the stack if the stack is
implemented using the linked list?
A. First node
B. Second node
C. Last node
D. None of the above
19) Consider the following stack implemented using stack.
#define SIZE 11
struct STACK
{
int arr[SIZE];
int top=-1;
}
What would be the maximum value of the top that does not cause the overflow of the stack?
A. 8
B. 9
C. 11
D. 10
20) If the elements '1', '2', '3' and '4' are inserted in a queue, what would be order for the
removal?
A. 1234
B. 4321
C. 3241
D. None of the above

~ 392 ~
21) A list of elements in which enqueue operation takes place from one end, and dequeue
operation takes place from one end is__
A. Binary tree
B. Stack
C. Queue
D. Linked list
22) Which of the following principle does Queue use?
A. LIFO principle
B. FIFO principle
C. Linear tree
D. Ordered array
23) Which one of the following is not the type of the Queue?
A. Linear Queue
B. Circular Queue
C. Double ended Queue
D. Single ended Queue
24) Which of the following that determines the need for the Circular Queue?
A. Avoid wastage of memory
B. Access the Queue using priority
C. Follows the FIFO principle
D. None of the above
25) Consider the following code.
int fun()
{
if(isEmpty())
{
return -10;
}
else
{
int n;

~ 393 ~
 n= q[front];
front++;
return n;
}
}
Which operation does the above code perform?
A. Enqueue
B. Dequeue
C. Return the front element
D. Both B and C
26) In the linked list implementation of queue, where will the new element be inserted?
A. At the middle position of the linked list
B. At the head position of the linked list
C. At the tail position of the linked list
D. None of the above
27) How many Queues are required to implement a Stack?

A. 3
B. 2
C. 1
D. 4
28) Which one of the following is not the application of the Queue data structure?
A. Resource shared between various systems
B. Data is transferred asynchronously
C. Load balancing
D. Balancing of symbols
29) Which of the following option is true if implementation of Queue is from the linked list?
A. In enqueue operation, new nodes are inserted from the beginning and in dequeue
operation, nodes are removed from the end.
B. In enqueue operation, new nodes are inserted from the end and in dequeue operation,
nodes are deleted from the beginning.

~ 394 ~
 C. In enqueue operation, new nodes are inserted from the end and in dequeue operation,
nodes are deleted from the end.
D. Both A and B.
30) The necessary condition to be checked before deletion from the Queue is__
A. Overflow
B. Underflow
C. Rear value
D. Front value
31) Which data structure is the best for implementing a priority queue?
A. Stack
B. Linked list
C. Array
D. Heap
32) Which of the following principle is used if two elements in the priority queue have the
same priority?
A. LIFO
B. FIFO
C. Linear tree
D. None of the above
33) Which of the following statement is not true regarding the priority queue?
A. Processes with different priority can be easily handled
B. Easy to implement
C. Deletion is easier
D. None of the above
34) A linear data structure in which insertion and deletion operations can be performed
from both the ends is___
A. Queue
B. Dequeue
C. Priority queue
D. Circular queue

~ 395 ~
35) Which of the following statement is not true about the doubly linked list?
A. We can traverse in both the directions.
B. It requires extra space
C. Implementation of doubly linked list is easier than the singly linked list
D. It stores the addresses of the next and the previous node
36) What is the maximum number of children that a node can have in a binary tree?
A. 3
B. 1
C. 4
D. 2
37) Which one of the following techniques is not used in the Binary tree?
A. Randomized traversal
B. Preorder traversal
C. Postorder traversal
D. Inorder traversal
38) Which of the following options is not true about the Binary Search tree?
A. The value of the left child should be less than the root node
B. The value of the right child should be greater than the root node.
C. The left and right sub trees should also be a binary search tree
D. None of the above
39) How can we define a AVL tree?
A. A tree which is binary search tree and height balanced tree.
B. A tree which is a binary search tree but unbalanced tree.
C. A tree with utmost two children
D. A tree with utmost three children
40) Why do we prefer Red Black tree over AVL tree?
A. Red Black trees are not strictly balanced
B. Red black tree requires lesser rotations than AVL tree.
C. AVL tree needs more space to store the balance factor.
D. Both B and C
41) Which of the following satisfies the property of the Red Black tree?

~ 396 ~
 A. A tree which is a binary search tree but not strictly balanced tree.
B. A node must be either Red or Black in color and root node must be black.
C. A tree with maximum three children
D. Both A and B
42) What would be the color of newly created node while inserting a new element in a Red
black tree?
A. Black, if the new node is not a root node
B. Red, if the new node is not a root node
C. Black, if the new node is a root node
D. Both B and C
43) Identify the AVL tree among the following options?

~ 397 ~
 A. A
B. C
C. Both A and C
D. B
44) A graph with all vertices having equal degree is known as a __________
A. Multi Graph
B. Regular Graph
C. Simple Graph
D. Complete Graph
45) Consider the following Tree

Perform:
A. Inorder Traversal
B. Preorder Traversal
C. Postorder Traversal
Sample Example on Binary Tree
Create the binary search tree using the following data elements.
43, 10, 79, 90, 12, 54, 11, 9, 50
1. Insert 43 into the tree as the root of the tree.
2. Read the next element, if it is lesser than the root node element, insert it as the root of the
left sub-tree.
3. Otherwise, insert it as the root of the right of the right sub-tree.

~ 398 ~
The process of creating BST by using the given elements, is shown in the image below.

~ 399 ~
Basis for Tree Graph
comparison

Definition Tree is a non-linear data structure in which A Graph is also a non-linear data
elements are arranged in multiple levels. structure.

Structure It is a collection of edges and nodes. For It is a collection of vertices and edges.
example, node is represented by N and edge For example, vertices are represented
is represented as E, so it can be written as: by V, and edge is represented as 'E',
T = {N,E} so it can be written as:
T = {V, E}

Root node In tree data structure, there is a unique node In graph data structure, there is no
known as a parent node. It represents the unique node.
topmost node in the tree data structure.

Loop It does not create any loop or cycle. In graph, loop or cycle can be formed.
formation

Model type It is a hierarchical model because nodes are It is a network model. For example,
arranged in multiple level, and that creates a Facebook is a social network that uses
hierarchy. For example, any organization the graph data structure.
will have a hierarchical model.

Edges If there are n nodes then there would be n-1 The number of edges depends on the
number of edges. graph.

Type of edge Tree data structure will always have In graph data structure, all the edges
directed edges. can either be directed edges,
undirected edges, or both.

Applications It is used for inserting, deleting or searching It is mainly used for finding the

~ 400 ~
 any element in tree. shortest path in the network.

References:
1. Griffiths, David (2012). Head First c. 1005 GravensteinHighwayNorth, Sebastopol, CA
95472 : Brian Sawyer
2. Stephen, Kochan.G (2005). A complete introduction to the C programming language.3rd
ed. Indianapolis, Indiana 46240 : Cindy Teeters
3. Mark Burnett, "Blocking Brute Force Attacks" Archived 2016-12-03 at the Wayback
Machine, UVA Computer Science, 2007
4. Web reference
- [Link]
- [Link]
- [Link]
- [Link]
- [Link]
- [Link]
- [Link]
- [Link]
- [Link]

-htps://[Link]/basics_of_computer_science/basics_of_computer_scienc
e_algorithm_flowchart.htm

~ 401 ~