Unit 1

Introduction

Asha H, Assistant Professor, Dept of Computer Science,

Surana College
PROBLEM SOLVING

❑ Problem solving is the process of overcoming issues, mistakes, errors, failures and risks to
move forward.
❑ It is the programmer who has to write down the solution to the problem in terms of simple
operations which the computer can understand and execute.
❑ In order to solve a problem by the computer one has to pass through certain stages or steps.
Steps Involved in Problem Solving:-

❑ Understanding the Problem

❑ Designing the algorithm
❑ Analysis of Algorithm
❑ Coding / Implementation
❑ Testing and Debugging
Algorithm

The word Algorithm means “ A set of finite

rules or instructions to be followed in
calculations or other problem-solving
operations ”
Or
“ A procedure for solving a mathematical
problem in a finite number of steps that
frequently involves recursive operations”.
[Link]
to-algorithms/
Therefore, Algorithm refers to a sequence of
finite steps to solve a particular problem.
 Algorithms play a crucial role in various fields and have many applications. Some of
the key areas where algorithms are used include:

Computer Science: Algorithms form the basis of computer programming and are
used to solve problems ranging from simple sorting and searching to complex tasks
Use of the such as artificial intelligence and machine learning.

Algorithms: Mathematics: Algorithms are used to solve mathematical problems, such as finding
the optimal solution to a system of linear equations or finding the shortest path in a
graph.

Operations Research: Algorithms are used to optimize and make decisions in fields
such as transportation, logistics, and resource allocation.

Artificial Intelligence: Algorithms are the foundation of artificial intelligence and

machine learning and are used to develop intelligent systems that can perform tasks
such as image recognition, natural language processing, and decision-making.

Data Science: Algorithms are used to analyze, process, and extract insights from
large amounts of data in fields such as marketing, finance, and healthcare.
What is the need for algorithms?

Algorithms are necessary for solving complex problems efficiently and effectively.

They help to automate processes and make them more reliable, faster, and easier to perform.

Algorithms also enable computers to perform tasks that would be difficult or impossible for
humans to do manually.

They are used in various fields such as mathematics, computer science, engineering, finance, and
many others to optimize processes, analyze data, make predictions, and provide solutions to
problems.
What are the Characteristics of an Algorithm?
 For some instructions to be an algorithm, it must
have the following characteristics:
✓ Clear and Unambiguous: The algorithm should be unambiguous. Each of its steps should be clear in all
aspects and must lead to only one meaning.
✓ Well-Defined Inputs: If an algorithm says to take inputs, it should be well-defined inputs. It may or may not
take input.
✓ Well-Defined Outputs: The algorithm must clearly define what output will be yielded and it should be well-
defined as well. It should produce at least 1 output.
✓ Finite-ness: The algorithm must be finite, i.e. it should terminate after a finite time.
✓ Feasible: The algorithm must be simple, generic, and practical, such that it can be executed with the available
resources. It must not contain some future technology or anything.
✓ Language Independent: The Algorithm designed must be language-independent, i.e. it must be just plain
instructions that can be implemented in any language, and yet the output will be the same, as expected.
✓ Input: An algorithm has zero or more inputs. Each that contains a fundamental operator must accept zero or
more inputs.
✓ Output: An algorithm produces at least one output. Every instruction that contains a fundamental operator
must accept zero or more inputs.
 Definiteness: All instructions in an algorithm
must be unambiguous, precise, and easy to
interpret. By referring to any of the instructions
For some in an algorithm one can clearly understand
what is to be done. Every fundamental operator
instructions to be in instruction must be defined without any
an algorithm, it ambiguity.

must have the

Finiteness: An algorithm must terminate after a
following finite number of steps in all test cases. Every
characteristics: instruction which contains a fundamental
operator must be terminated within a finite
amount of time. Infinite loops or recursive
functions without base conditions do not
possess finiteness.

Effectiveness: An algorithm must be developed

by using very basic, simple, and feasible
operations so that one can trace it out by using
just paper and pencil.
 It should terminate after a finite time.

Properties of It should produce at least one output.

Algorithm:
It should take zero or more input.

It should be deterministic means giving the

same output for the same input case.

Every step in the algorithm must be effective

i.e. every step should do some work.
Designing Algorithms

Brute Force Algorithm

Recursive Algorithm
Divide and Conquer Technique
Greedy Approach
Dynamic Programming
Backtracking Algorithm
Designing Alorithm - Types of Algorithms:

There are several types of algorithms available. Some important algorithms are:

Brute Force Algorithm

1. Brute Force Algorithm:

It is the simplest approach to a problem. A brute force algorithm is the first approach that comes to finding when we
see a problem.

Recursive Algorithm

2. Recursive Algorithm:

recursion

A recursive algorithm is based on recursion. In this case, a problem is broken into several sub-parts and called the
same function again and again.

Backtracking Algorithm

3. Backtracking Algorithm:

The backtracking algorithm builds the solution by searching among all possible solutions. Using this algorithm, we
keep on building the solution following criteria. Whenever a solution fails, we trace back to the failure point build
on the next solution and continue this process till we find the solution, or all possible solutions are looked after.
Searching Algorithm:
Searching algorithms are the ones that are used for searching elements or groups of elements from a
particular data structure. They can be of different types based on their approach or the data structure in
which the element should be found.
5. Sorting Algorithm:
Sorting is arranging a group of data in a particular manner according to the requirement. The algorithms
which help in performing this function are called sorting algorithms. Generally sorting algorithms are
used to sort groups of data in an increasing or decreasing manner.
6. Hashing Algorithm:
Hashing algorithms work similarly to the searching algorithm. But they contain an index with a key ID. In
hashing, a key is assigned to specific data.
7. Divide and Conquer Algorithm:
This algorithm breaks a problem into sub-problems, solves a single sub-problem, and merges the
solutions to get the final solution. It consists of the following three steps:
❑ Divide
❑ Solve
❑ Combine
Greedy Algorithm:
In this type of algorithm, the solution is built part by part. The solution for the
next part is built based on the immediate benefit of the next part. The one solution
that gives the most benefit will be chosen as the solution for the next part.
9. Dynamic Programming Algorithm:
This algorithm uses the concept of using the already found solution to avoid
repetitive calculation of the same part of the problem. It divides the problem into
smaller overlapping subproblems and solves them.
10. Randomized Algorithm:
In the randomized algorithm, we use a random number so it gives immediate
benefit. The random number helps in deciding the expected outcome.
To learn more about the types of algorithms refer to the article about “Types of
Algorithms“.
Advantages of Algorithms:

❖ It is easy to understand.
❖ An algorithm is a step-wise representation of a solution to a given problem.
❖ In an Algorithm the problem is broken down into smaller pieces or steps hence,
it is easier for the programmer to convert it into an actual program.
❖ Disadvantages of Algorithms:
❖ Writing an algorithm takes a long time so it is time-consuming.
❖ Understanding complex logic through algorithms can be very difficult.
❖ Branching and Looping statements are difficult to show in Algorithms(imp).
Disadvantages of Algorithms:

❖ Writing an algorithm takes a long time so it is time-consuming.

❖ Understanding complex logic through algorithms can be very difficult.
❖ Branching and Looping statements are difficult to show in Algorithms(imp).
Symbol Used in Flowchart:
Symbol Name Description

Terminal Terminal represent start and end

Used for input (reading) and output

Input / Output
(printing) operation.

Used for data manipulation and data

Processing
operations.

Arrow Used to represent flow of operations.

Connector Used to connect different flow of lines

Decision Used to make decision

Example: Algorithm and Flowchart to check odd
or even

Step 1: Start
Step 2: Declare a variable x
Step 3: Take a input from user and store in x
Step 4: IF x % 2 == 0 THEN
PRINT Even
ELSE
PRINT Odd
Step 5: End

Flowchart Algorithm
Steps in Problem Solving - Coding, Compiling and
Execution
Flowchart to find Area of circle
Flowchart to find Sum of Two numbers
Flowchart to find Simple Interest
Flowchart to Find Largest among two
numbers
Flowchart:-
Advantages:- Disadvantages:-
Easy to make. It is a time-consuming process.
Mistakes can be easily identified. No scope for alteration or
Communication becomes effective and modification.
easy to understand. No man to computer communication.
Logics can be easily interpreted.
Difference b/w Algorithm and Flowchart:-

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

It is easy to debug. It is hard to debug.

It is the pseudo-code for the program. It is just a graphical representation of that

logic.
In the algorithm, plain text is used.
In the Flowchart, symbols/shapes are used.
It does not follow any rules.
It follows rules to be constructed.
Difference b/w Algorithm and Flowchart:-
Algorithm Flowchart
An algorithm can be defined as a step-by-step A flowchart is a visual or graphical
procedure for accomplishing a task. representation of an algorithm.
It is easy to debug. It is hard to debug.
In the algorithm, plain text is used. In the Flowchart, symbols/shapes are used.
For complex programs, algorithms prove to be For complex programs, Flowcharts prove to be
inadequate. adequate.
It is complex to understand. It is easy to understand.
Algorithm as a Technology

1. Internet
2. The Human Genome Project
3. E-Commerce
4. Page Rank
5. Weather Forecasting
6. Linear Programming
7. Shortest Path Algorithm
8. Other Important Applications of Algorithms
Pseudo code:-
Pseudo code is a simple way of describing a set of instructions that does not
have to use specific syntax.
Common pseudo code notation:-
1) Input
2) Output
3) While
4) For
5) Repeat until
6) If then else
Using Pseudo code:-
REPEAT
OUTPUT “What is the best subject you take?”
INPUT user inputs the best subject they take
STORE the user’s input in the answer variable
IF answer = ‘Computer Science’ THEN
OUTPUT ‘of course it is!’
ELSE
OUTPUT ‘try again!’
UNTIL answer = ‘Computer Science’
Flowchart for Pseudocode:-
Asymptotic notations:-
It is used to mathematically calculate the running time of any operation inside
an algorithm. OR
The asymptotic notations used for calculating the running time complexity of
an algorithm.
There are mainly three asymptotic notations:-
• Big-O Notation (O-notation)
• Omega Notation (Ω-notation)
• Theta Notation (Θ-notation)
Big-O Notation (O-notation):-
Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.
• It is the most widely used notation for Asymptotic analysis.
• It specifies the upper bound of a function.
• It returns the highest possible output value(big-O) for a given input.
Big-Oh(Worst Case) It is defined as the condition that allows an algorithm to
complete statement execution in the longest amount of time possible.
If f(n) describes the running time of an algorithm,
f(n) is O(g(n)) if there exist a positive constant C
and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0.

Mathematical Representation of Big-O

Notation:-
O(g(n)) = { f(n): there exist positive constants c
and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
Omega Notation (Ω-notation):-
Omega notation represents the lower bound of the running time of an algorithm.
Thus, it provides the best-case complexity of an algorithm.
It is defined as the condition that allows an algorithm to complete statement
execution in the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The function
f is said to be Ω(g), if there is a constant c > 0 and a natural number n0 such that
c*g(n) ≤ f(n) for all n ≥ n0.
 Mathematical Representation of Omega notation :-

Ω(g(n)) = { f(n): there exist positive

constants c and n0 such that 0 ≤
cg(n) ≤ f(n) for all n ≥ n0 }
Theta Notation (Θ-Notation):
Theta notation encloses the function from above and below.
Since it represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an algorithm.
Theta (Average Case) You add the running times for each possible input
combination and take the average in the average case.
Let g and f be the function from the set of natural numbers to itself. The function
f is said to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0
such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0.
 Mathematical Representation of Theta notation:

Θ (g(n)) = {f(n): there exist positive

constants c1, c2 and n0 such that 0 ≤ c1 *
g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
 Analyzing Algorithms

Analysis refers to the task to determine

the computing time and storage space
required for an algorithm. Algorithm can be analyzed in two ways:

Time Factor: Time is measured by counting the number of

It is called as “Performance Analysis” or key operations such as comparisons in the sorting algorithm.
“efficiency” of an algorithm. Space Factor: Space is measured by counting the maximum
memory space required by the algorithm.

Definition:
Performance analysis of an algorithm is
the process of calculating space required
by that algorithm and time required by
that algorithm.
Priori and Posteriori Analysis
To analyze the algorithm, 2 phases are required.

1)Priori Analysis – “Priori” means before. This analysis is done before its
implementation.
Total time taken by the algorithm = The number of times the statement will be executed
(frequency count) x time taken for one execution
The notations used in Priori analysis are Big-oh (O), Omega (Ω), Theta(θ), small-oh(o).

2) Posteriori Analysis – “Posterior” means after. This analysis is done after

implementing the algorithm in any programming language.
Posteriori Analysis
Testing a program consists of 2 major phases.

a) Debugging: After execution of program if there are faulty results, then they are corrected
using this approach.
b) Profiling: It is the actual time taken by the algorithm to process the data.

1. Read data
2. Time (t1)
3. Process (data)
4. Time (t2)
5. Write (time = t2 – t1)
Priori and Posteriori Analysis
Difference between Priori Analysis and Posteriori Analysis

Priori Analysis Posteriori Analysis

computing time and storage an algorithm will Profiling will measure the exact time and space
require. required to compute the results.

Independent of programming language and Depends on machine, compiler and programming

machine. language used
It will give approximate answer. It gives exact answer
Uses asymptotic notations to represent the time It does not depend on the asymptotic notations to
taken. represent the time taken.
Analysis is done on the algorithm and not the code. Analysis is done on the actual code
1. Read data
2. Time (t1)
3. Process (data)
4. Time (t2)
5. Write (time=t2 – t1)
Complexity of Algorithms
Complexity of an algorithm is a measure of the amount of time and /or
space required by an algorithm for an input of a given size.

The 2 types of algorithm complexity are:

❖Time complexity – Time required to complete the task of that algorithm.
❖Space complexity – Space required to complete the task of that algorithm.
Space Complexity

The total amount of computer memory required by an algorithm to complete its

execution is called as space complexity of that algorithm.
During program execution the computer memory is used for
❖Instruction space:- It is the amount of memory used to store compiled
version of instruction.
❖Environmental stack:- It is the amount of memory used to store information
of partially executed functions at the time of function call.
❖Data space:- It is the amount of memory used to store all the variables and
constants.
Space complexity
Calculation of space complexity:
Memory required for storing different data types

Data type Memory required

Integer (2,3,4,5 …) 4 bytes

Float (3.141, 6.756…) 4 bytes

Character (a, b, c…) 1 byte

Double 8 bytes
The space needed by an algorithm consists of the following components:-

a) The fixed static part:- A fixed part that is a space required to store certain data
and variables, that are independent of the size of the problem. For example,
simple variables and constants used, program size, etc
b) The variable dynamic part:- A variable part is a space required by variables,
whose size depends on the size of the problem.

The overall space requirements for an algorithm is the sum of both the fixed
static part storage and variable dynamic part storage.
If P be a program, then space required for program P will be denoted by S(P).
S(p) = Cp + Sp
Time complexity:-

The total amount of time required by an algorithm to complete its execution

is called Time complexity.
There are 3 cases:
1. Best case: When minimum time is required to complete its execution.
2. Average case: The amount of time is neither more nor less for its execution.
3. Worst case: Maximum amount of time is required to complete its execution.
Time-Space Tradeoff:-

In computer science, space time tradeoff is a way of solving a problem or

calculation in less time by using more storage space.
OR
By solving a problem in a very little space by spending more time.
Complexity of an Algorithms
The complexity of an algorithm computes the amount of time and spaces required by an algorithm for an input
of size (n).
The complexity of an algorithm can be divided into two types.
➢ Time complexity
➢ Space complexity.
Time Complexity of an Algorithm
The time complexity is defined as the process of determining a formula for total time required towards the
execution of that algorithm. This calculation is totally independent of implementation and programming
language.
Space Complexity of an Algorithm
Space complexity is defining as the process of defining a formula for prediction of how much memory space is
required for the successful execution of the algorithm. The memory space is generally considered as the primary
memory
Space Complexity of an Algorithm
Space complexity is defining as the process of defining a formula for prediction of how much memory
space is required for the successful execution of the algorithm. The memory space is generally
considered as the primary memory.

For any algorithm Memory required for the following things:

• Instruction space: Amount of memory used to store instruction
• Data Space: Amount of memory used to store variables and constants
• Environment Stack: Amount of memory used to store function call info
Formula to calculate Space complexity:
S(P)=Cp + Sp
Where,
• Cp is the space required for code segment(Cp)
• Sp is the space required to Dynamic part(Sp)
Time Complexity of an Algorithm
The time complexity is defined as the process of determining a formula for total time required
towards the execution of that algorithm. This calculation is totally independent of implementation
and programming language.
Time complexity of an algorithm will be denoted by notations called “Big O Notation”.ie O(n).
Order of notation based on the relation between run time against the number of input data
sizes and the number of operations performed on them.
There are different types of time complexities used:
1. Constant time – O (1)
2. Linear time – O (n)
3. Logarithmic time – O (log n)
4. Quadratic time – O (n^2)
5. Cubic time – O (n^3)
1. Constant time – O (1)
➢ An algorithm is said to have constant time with order O (1) when it is not dependent on the input size n.
Irrespective of the input size n, the runtime will always be the same.
Example: accessing the array element base on index, push, pop operations.
T(n)=O(1)
Time complexity=compiletime + runtime

[Link] time – O(n)

An algorithm is said to have a linear time complexity O(n) when the running time increases linearly with the
length of the input.
When the function involves checking all the values in input data, with this order O(n).
Example: Linear search if the size of the array increases number of comparesions also increase intern time
complexity increases.
T(n)=O(n)
[Link] time – O (log n)
An algorithm is said to have a logarithmic time complexity when it reduces the size of the
input data in each step. This indicates that the number of operations is not the same as the
input size.
Binary search functions: This involves the search of a given value in an array by splitting
the array into two and starting searching in one split.
T(n)=O(log n)
[Link] time – O (n^2)
An algorithm is said to have a non-linear time complexity where the running time increases
non-linearly (n^2) with the length of the input. Generally, nested loops come under this
order where one loop takes O(n) and if the function involves a loop within a loop, then it
goes for O(n)*O(n) = O(n^2) order
Similarly, if there are ‘m’ loops defined in the function, then the order is given by O (n ^ m),
which are called polynomial time complexity functions..
T(n)= O(n^2)
 Growth-rate Functions
❖ O(1) – constant time, the time is independent of n, e.g. array look-up
❖ O(log n) – logarithmic time, usually the log is base 2, e.g. binary search
❖ (O) – linear time, e.g. linear search
❖ O(n*log n) – e.g. efficient sorting algorithms Heap sort, Merge Sort
❖ O(n 2 ) – quadratic time, e.g. selection sort
❖ O(n k ) – polynomial (where k is some constant) :Matrix Multiplication,
❖ Bubble Sort, Selection Sort, Insertion Sort, Bucket Sort.
❖ O(2n ) – exponential time, very slow! :Towers of Hanoi
❖ O(n!) - Factorial algorithm –– Determinant Expansion by Minors, Brute
❖ force

Order of growth of some common functions

O(1) < O(log n) < O(n) < O(n * log n) < O(n2 ) < O(n3 ) < O(2n )<O(n!)
Growth-rate Functions in Graphical Representation
Standard mathematical notations and functions
Monotonocity:
An array is monotonic if it is either monotone increasing or monotone decreasing.
An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is
monotone decreasing if for all i <= j, A[i] >= A[j]. Return true if and only if the
given array A is monotonic.
Floor and Ceiling function:
A ceil function returns the smallest integer greater than or equal to the given
number, whereas the floor function returns the largest number smaller than or
equal to the given number.
Ceil Function:
Ceil means ceiling of our home. So, we can pick out some
similarities from here. That is ceil function returns an integer that is
just greater than a certain rational value.
Ceil function is used in situations where exact integer values are
required which is just greater than or equal to the given value.
For example, ceil value of 3.138 is 4.
It should be noted that this does not return the round-off value
which is 3. It just returns an integer that is just greater than a
certain rational value.
Example 1: Find ceil value of 5.534.
Solution: Ceil value of 5.534 is an just greater than 5.534 i.e. 6.
So, the ceil value of 5.534 is 6.
Example 2: What is ceil(0.34).
Solution: Ceil value of 0.34 is integer just greater than 0.34 i.e. 1.
So, ceil(0.34) is 1.
Floor function:
Floor means the floor of our home. So, we can pick out some
similarities from here. That is floor function returns an integer that is
just lesser than a certain rational value.
Floor function is used in situations where exact integer values are
required which is just lesser than or equal to the given value.
For example, ceil value of 3.883 is 3.
It should be noted that this does not return the round-off value which
is 4. It just returns an integer that is just lesser than a certain rational
value.
Example 1: What is value of floor(86.43)?
Solution: floor value of 86.43 is integer value just lesser than 86.43
that is 86.
So, the value of floor(86.43) is 86.
Example 2: What is floor of 67.212?
Solution: floor of 67.212 is integer just lesser than 67.212 that is 67.
So, floor of 67.212 is 67.
 Remainder Function
The remainder is evaluated using % (the modulo operator) and stored
in remainder .

remainder = dividend % divisor;

Finally, the quotient and remainder are displayed using printf() .
printf("Quotient = %d\n", quotient);
printf("Remainder = %d", remainder)
Examples

Input: A = 2, B = 6
Output: Quotient = 0, Remainder = 2

Input: A = 17, B = 5
Output: Quotient = 3, Remainder = 2
Integer and Absolute value function
Integer:
Integers are whole numbers. They can be positive, negative, or zero.
Numbers like -321, 497, 19345, and -976812 are all perfectly valid integers, but 4.5 is
not because 4.5 is not a whole number.
Floating point numbers are numbers with a decimal.
Absolute:
The use of the function abs in C programming is to return the absolute value of an
integer. By absolute value, it means the function returns the positive value of an
integer.
The parameter or argument of function abs in C is an integral value. To use the abs()
function in C, you need a header file called <stdlib.
C library - abs() function. This function only returns the positive integer.
For example, if we have an integer value of -2, we want to get the absolute number of
-2. We then used the abs() function to return the positive number 2.
Factorial Function

The factorial sign is an exclamation point and it means to

start with the number and multiply by each previous integer
until reaching 1.
For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.
Permutations

A permutation also called an “arrangement number” or

“order,” is a rearrangement of the elements of an ordered list
S into a one-to-one correspondence with S itself.
A string of length n has n! permutation.
Below are the permutations of string ABC.
ABC ACB BAC BCA CBA CAB
Here is a solution that is used as a basis in
backtracking.
Exponents

That means, exponent refers to how many times a number multiplied by

itself. For example, 6 is multiplied by itself 4 times, i.e. 6 × 6 × 6 × 6.
This can be written as 64.
Here, 4 is the exponent and 6 is the base.
It can be represented as a^x where a is a constant value. Usually, the
constant value is e.
Logarithms

Logarithm, the exponent or power to which a base must be

raised to yield a given number.
Expressed mathematically, x is the logarithm of n to the
base b if bX = n, in which case one writes x = logb n.
For example, 23 = 8; therefore, 3 is the logarithm of 8 to
base 2, or 3 = log2 8.
 Exchanging the values of two variables:
Swapping two number in C programming language means exchanging the values of two
variables. Suppose you have two variable var1 & var2. Value of var1 is 20 & value of var2 is
40. So, after swapping the value of var1 will become 40 & value of var 2 will become 20. In
this blog will understand how to swap two variables in C.
❑ Swapping Two Numbers Using Third Variable (Temporary Variable)
❑ Swapping Two Numbers Using Without Using Third Variable (Without Temporary
Variable)
[Link]
[Link]
Exchanging the value of two variables
Let us consider two variables a = 10 and B = 20
Before swapping: a=10 and B=20
After swapping: a=20 and B=10

10 20

a b
We can use the assignment operator “=” to assign the value to a variable as shown below:
a=b
b=a
The assignment (a=b) has changed the value of a to 20 and the assignment (b= a) has changed the value
of b to 20. Since the value of a is 20 after assignment (a=b) and its value is sorted in b.
20 10

a b
We cannot solve the problem by assigning the value of ‘a’ to ‘b’ and ‘b’ to ‘a’. It is because once the value
of ‘a’ is assigned to ‘b’, then original value of ‘a’ is overwritten and will be lost.
Let us use temporary variable ‘t’ to solve this problem.

10 10 10

a b t
First assign the value of ‘a’ to ‘t’ (a=t)

10 20 10

a b t
Assign the value of ‘b’ to ‘a’ (a=b)

20 20 10

a b t
Assign the value of ‘t’ to ‘b’ (a=t)

20 10 10
a b t
Finally, the value of a and b are swapped using temporary variable ‘t’
Swap Two Numbers Using a Temporary Variable
Swapping two numbers means exchanging their values.
Example
Input: a = 5, b = 10
Output: a = 10, b = 5
Explanation: The values of a and b are exchanged.

Input: a = -1, b = 20
Output: a = 20, b = -1
Explanation: The values of a and b are exchanged.
The idea behind swapping two numbers using 3rd variable is simple. Store the value of
1st variable in temporary variable. Store the value of 2nd variable in the first variable. At last,
store the value of temp variable in 2nd variable. In this program, we are using a temporary
variable to hold the value of the first variable.

❑ Assign var1 value to a temp variable: temp = var1

❑ Assign var2 value to var1: var1 = var2
❑ Assign temp value to var2: var2 = temp

Code:
temp = var1;
var1 = var2;
var2 = temp;
In this method, we use a temporary variable to hold one of the
values, then we assign the value of the second variable to the first,
and finally, we assign the temporary value to the second variable.
✓ Store the value of a in a temporary variable temp.
✓ Assign the value of b to a.
✓ Assign the value stored in the temp to b.
Example
// C Program to Swap Two Numbers using a Temporary Variable
#include <stdio.h>

int main() {
int a = 5, b = 10, temp;

printf("Before swapping: a = %d, b = %d\n", a, b); Output:

Before swapping: a = 5, b = 10
// Store the value of a in temp After swapping: a = 10, b = 5
temp = a;
// Assign the value of b to a
a = b;
// Assign the value stored in temp to b
b = temp;
printf("After swapping: a = %d, b = %d\n", a, b);
return 0;
}
Swapping Two Numbers Without Using Third Variable

In this variation of swapping two variables, we are not using any temporary variable to
store the value. In the first variable we are storing the sum of both variable. Then, in next
step we are we are extracting the value of 1st variable by subtracting the value of
2nd variable form the sum & storing it in 2nd variable. At last, we are extracting the
original value of the 2nd variable & storing it in the 1st variable.
Code:
var1 = var1 + var2;
var2 = var1 - var2;
var1 = var1 - var2;
Swap Two Numbers Without Using a Temporary Variable

In this method, we use arithmetic operations to swap the values

without using a temporary variable.
✓ Add the values of a and b and store the result in a.
✓ Subtract the value of b from a and store the result in b.
✓ Subtract the new value of b from a and store the result in a.
 Example
// C Program to Swap Two Numbers without Using a Temporary
// Variable
#include <stdio.h>

int main() {
int a = 5, b = 10; Output:
printf("Before swapping: a = %d, b = %d\n", a, b);
Before swapping: a = 5, b = 10
// Add the values of a and b After swapping: a = 10, b = 5
a = a + b;
// Subtract the value of b from a
b = a - b;
// Subtract the new value of b from a
a = a - b;

printf("After swapping: a = %d, b = %d\n", a, b);

return 0;
}
Counting:
Counting techniques are very frequently used in computer algorithms. Generally a count
must be made on the number of items in a set which possess some particular property, or
which satisfy some particular condition or conditions.

Example:
Check the grade of the students based on marks. First of all we will take input a mark of subject from the
candidate and according to following condition we will calculate the grade.
[Link] marks <50 then Grade is F
[Link] marks >=50 <60 then Grade is D
[Link] marks >=60 <70 then Grade is C
[Link] marks >=70 <80 then Grade is B
[Link] marks >=80 <90 then Grade is A
[Link] marks >=90 then Grade is A+
Summation
The symbol ∑ indicates summation and is used as a shorthand notation for
the sum of terms that follow a pattern.
For example, the sum of the first 4 squared integers, 12+22+32+42, follows
a simple pattern: each term is of the form i2, and we add up values from i=1
to i=4.
Sum = i1+i2+i3+i4+…….in
Computer can add two numbers at a time and return the sum of two numbers. So for this purpose we assign the
variable sum as 0.
Sum = sum+i1
Sum = sum+i2
Sum = sum+i3
Sum = sum+i4
sum = sum+i n
Fibonacci sequence
The Fibonacci numbers may be defined by the recurrence relation.
The Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5,
8, 13, 21, 34, 55, 89, 144.
Examples:

Input : n = 1 with seed values and

Output : 1 F0=0 F0​=0 and
F1=1 F1​=1
Input : n = 9
Output : 34
Input : n = 10
Output : 55
 Recursion Approach to Find and Print Nth Fibonacci
Numbers:

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the

recurrence relation: Fn=Fn−1+Fn−2 with seed values F0=0 and F1​=1.
The Nth Fibonacci Number can be found using the recurrence relation shown
above:
✓ if n = 0, then return 0.
✓ If n = 1, then it should return 1.
✓ For n > 1, it should return Fn-1 + Fn-2
// Fibonacci Series using Space Optimized Method
#include <stdio.h>
int fib(int n)
{
int a = 0, b = 1, c, i;
if (n == 0) Output

return a; 34

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

c = a + b;
a = b;
b = c;
}
return b;
}
 Character to Number Conversion
Converting Characters to Integers is essential in programming, whether it is users’ input or extracting values
from strings.
Every programming language has different techniques to handle the conversion of these lines.
Char to Int in C:
Through the basic arithmetic of the ASCII value subtracting ‘0’ from the character to get its value as an integer.

#include <stdio.h>
int main() {
char ch = '5';
int intValue = ch - '0';
printf("The integer value is: %d\n", intValue);
return 0;
}
Output:
The integer value is: 5
Reversing the digits of an integer

We can just write the number in the reverse order of digits. In other
words, reversing a number means writing the given number in the reversed order
of digits.
For example, if the number is “12345”, the reverse number will be “54321”.
The reverse of a number means reversing the order of digits of a number.
For example, if number num = 12548, the reverse of number num is 84521.
Flow of Program To Reverse a Number
C Program to Reverse an Integer
// C program to implement
// the above approach
#include <stdio.h>
// Iterative function to reverse digits of num
int reverseDigits(int num)
{
int rev_num = 0;
while (num > 0)
{
rev_num = rev_num * 10 + num % 10;
num = num / 10;
}
return rev_num;
}
// Driver code
int main()
{
int num = 4562;
printf("Reverse of is %d", reverseDigits(num));
getchar();
return 0;
}

Output:
Reverse of no. is 2654
 Explanation
The above program takes an integer num as input. We use a while loop to iterate until the value of num
becomes 0. Inside the loop, the last digit of num is extracted using the modulo operator (num % 10). This digit
is then added to rev_num after multiplying it by 10, which means the existing digits of rev_num are shifted one
place to the left.
The value of num is updated by dividing it by 10, (num = num / 10). This removes the last digit of num in each
iteration, and terminates the loop when num becomes 0. rev_num is returned, which contains the reversed
digits of the original number.
num = 4562
rev_num = 0
rev_num = rev_num *10 + num%10 = 2
num = num/10 = 456
rev_num = rev_num *10 + num%10 = 20 + 6 = 26
num = num/10 = 45
rev_num = rev_num *10 + num%10 = 260 + 5 = 265
num = num/10 = 4
rev_num = rev_num *10 + num%10 = 2650 + 4 = 2654
num = num/10 = 0
Thank You…

End of Unit 1