What is an Algorithm?
Definition
• An algorithm is a step-by-step set of instructions or a well-defined procedure designed
to solve a problem or perform a specific task. It provides a sequence of operations that,
when executed, produces a solution or output from a given input.
• In the context of computer science, an algorithm is implemented using a programming
language (e.g., C, Python, Java) to instruct a computer to perform computations or
process data.
Origin of the Term
• The word "algorithm" comes from the name of the Persian mathematician Al-Khwarizmi
(9th century), who contributed to algebra and introduced systematic problem-solving
methods.
Example:
Algorithm to make tea: Boil water → Add tea leaves → Add milk/sugar → Strain and serve.
Simple Analogy
• Think of an algorithm as a recipe for cooking:
o Input: Ingredients (e.g., flour, water, yeast).
o Steps: Mix ingredients, knead dough, let it rise, bake.
o Output: Bread.
o Similarly, an algorithm takes input data, processes it through defined steps, and
produces an output (e.g., sorted list, search result).
2. Characteristics of an Algorithm
An effective algorithm must have the following properties:
• 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 in an algorithm one can clearly
understand what is to be done. Every fundamental operator in instruction must be
defined without any ambiguity.
• Finiteness: An algorithm must terminate after a finite number of steps in all test cases.
Every 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.
1. Input:
o An algorithm should take zero or more inputs (e.g., numbers to sort).
o Example: In the bubble sort program, the input is an array of integers.
2. Output:
o It must produce at least one output (e.g., a sorted array).
o Example: The output of the sorting algorithm is the arranged list.
3. Finiteness:
o The algorithm must terminate after a finite number of steps.
o Example: The bubble sort stops when no more swaps are needed, ensuring it
doesn’t run infinitely.
4. Definiteness:
o Each step must be precisely defined and unambiguous.
o Example: “Compare two adjacent elements and swap if the first is greater” is a
clear instruction.
5. Effectiveness:
o Every step must be basic enough to be carried out (in principle) by a person using
paper and pencil, and it must lead to a solution.
o Example: Adding two numbers is a simple, effective step in a calculation
algorithm.
6. Efficiency:
o The algorithm should use minimal time and resources (e.g., memory, CPU cycles).
o Example: Bubble sort is less efficient (O(n²)) compared to Quick Sort (O(n log n))
for large datasets.
3. Types of Algorithms
Algorithms can be classified based on their purpose or design. Here are some common types
relevant to BCA students:
Types of Algorithms
1. Sorting Algorithms
• Arrange data in ascending/descending order.
o Bubble Sort: Compares adjacent elements (simple but slow).
o Quick Sort: Divide-and-conquer approach (fast for large datasets).
o Merge Sort: Splits, sorts, and merges (stable and efficient).
2. Searching Algorithms
• Find an element in a dataset.
o Linear Search: Checks each element sequentially.
o Binary Search: Works on sorted arrays by repeatedly dividing the search
interval.
3. Recursive Algorithms
• Solve problems by calling themselves with smaller inputs.
o Example: Factorial calculation, Fibonacci series.
4. Greedy Algorithms
• Make locally optimal choices at each step to find a global optimum.
o Example: Dijkstra’s algorithm (shortest path), Huffman coding.
5. Dynamic Programming (DP)
• Break problems into overlapping subproblems and reuse solutions.
o Example: Knapsack problem, Fibonacci with memoization.
6. Backtracking
• Explore all possible solutions and backtrack if a dead end is reached.
o Example: N-Queens problem, Sudoku solver.
4. How Algorithms Work (Step-by-Step Process)
1. Problem Identification:
o Define the problem (e.g., “Sort a list of numbers”).
2. Design the Algorithm:
o Break it into logical steps (e.g., compare and swap adjacent elements).
3. Implementation:
o Write the algorithm in a programming language (e.g., C code for bubble sort).
4. Testing:
o Verify the algorithm works with sample inputs (e.g., [64, 34, 25, 12, 22]).
5. Optimization:
o Improve efficiency if needed (e.g., switch to a faster sorting algorithm).
Example: Bubble Sort Algorithm
• Problem: Sort an array in ascending order.
• Steps:
1. Compare adjacent elements.
2. If the first element is greater than the second, swap them.
3. Repeat until no more swaps are needed.
Code:
FOR i = 0 to n-1
FOR j = 0 to n-i-1
IF arr[j] > arr[j+1]
SWAP arr[j] and arr[j+1]
• C Implementation (from your earlier request):
void bubbleSort(int arr[], int size) {
int i, j, temp;
for (i = 0; i < size - 1; i++) {
for (j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
• Output for [64, 34, 25, 12, 22]: [12, 22, 25, 34, 64].
5 Properties of Algorithm:
• It should terminate after a finite time.
• It should produce at least one output.
• 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.
Time and Space Complexity
• Time Complexity: Measures the time taken based on input size (e.g., O(n²) for bubble
sort, meaning time grows quadratically with input size).
• Space Complexity: Measures memory usage (e.g., bubble sort uses O(1) extra space as it
sorts in-place).
6. Applications in different Domains
• Business: Algorithms optimize inventory management or CRM data analysis.
• Law Enforcement: Search algorithms match fingerprints or DNA in databases.
• Political Process: Voting algorithms ensure accurate vote counting.
• E-commerce: Recommendation algorithms suggest products.
• Manufacturing: Scheduling algorithms optimize production lines.
• Education: Algorithms grade exams or manage student timetables .
• Entertainment: Game algorithms control AI opponents.
• Agriculture: Algorithms predict crop yields based on weather data.
• Bioinformatics: Sequence alignment algorithms compare DNA (e.g., the Python exercise
from earlier).
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.