Unit 1 · Foundation of DSA
Algorithm and Its Properties
Learn what an algorithm is, its essential properties, examples, advantages, and how to write correct algorithms for DSA problems.
Introduction
An algorithm is a finite set of clear, ordered steps used to solve a problem. It's like a recipe: it takes specific ingredients (input), follows a series of instructions, and produces a finished dish (output).
In the world of Data Structures and Algorithms (DSA), data structures are the containers for our data, while algorithms are the brains of the operation. They provide the logic for manipulating that data to achieve a goal, whether it's sorting a list, finding the shortest path on a map, or searching for a name in a database.
A good algorithm is not just about getting the right answer. It must also be efficient, clear, and guaranteed to finish. This chapter explores the essential properties that every valid algorithm must possess.
Input | v Step-by-step Algorithm | v Correct Output
Why Algorithms Matter
Problem Solving
Algorithms convert a problem into clear steps.
Efficiency
A better algorithm can solve the same problem much faster.
Correctness
Good algorithms produce the expected output for valid input.
Interviews
Most coding interviews test algorithmic thinking.
Table of Contents
What is an Algorithm?
An algorithm is a sequence of instructions that takes some input, processes it, and produces an output.
A recipe, an ATM withdrawal process, and finding the largest number in a list are all examples of algorithms.
Simple definition: Algorithm means step-by-step logic to solve a specific problem.
Properties of a Good Algorithm
For a set of instructions to be considered a valid algorithm, it must satisfy the following five properties. These criteria ensure that the algorithm is well-defined, reliable, and executable.
1. Input
An algorithm must have zero or more well-defined inputs. These are the values on which the algorithm will operate. For example, a sorting algorithm takes a list of numbers as input.
2. Output
An algorithm must produce at least one well-defined output. This is the result of the computation. For the sorting algorithm, the output would be the same list of numbers, but in sorted order.
3. Finiteness
An algorithm must terminate after a finite number of steps for all possible inputs. It cannot run forever. An algorithm with an infinite loop violates this property.
4. Definiteness
Each step of an algorithm must be precisely and unambiguously defined. There should be no room for interpretation. For example, "add 2 or 3" is ambiguous, whereas "add 2" is definite.
5. Effectiveness
Every instruction must be basic enough that it can, in principle, be carried out by a person using only pen and paper. The operations must be feasible. A step like "find the largest integer" is not effective because it's a problem in itself, not a basic operation.
Algorithm Example: Find Largest Number
Let's write a simple algorithm to find the largest number in a given list of numbers. We can express this in plain English before converting it to code.
Problem: Given a list of numbers, find the largest one.
Algorithm:
- Start with the first element as largest.
- Compare largest with each remaining element.
- If a bigger element is found, update largest.
- After traversal, print largest.
How to Write an Algorithm
Writing an algorithm is a structured process. Following these steps can help you create a clear and correct solution.
- Understand the Problem: Clearly define what the input is and what the output should be. Identify any constraints.
- Devise a Plan: Think about how you would solve the problem manually. Break it down into smaller, manageable steps. Consider different approaches (e.g., brute-force, divide and conquer).
- Write the Steps: Write down the algorithm in clear, unambiguous steps using plain language or pseudocode.
- Test the Algorithm: Dry run your algorithm with simple examples and edge cases (e.g., empty input, single-element input) to ensure it is correct and handles all scenarios.
Common Types of Algorithms
Algorithms can be grouped by the strategy they use to solve problems.
- Brute Force: Try all possible options.
- Divide and Conquer: Break the problem into smaller parts.
- Greedy: Choose the best option at each step.
- Dynamic Programming: Store and reuse answers to subproblems.
- Backtracking: Try a path and undo it if it fails.
Algorithm Properties at a Glance
| Property | Meaning |
|---|---|
| Input | Data accepted by the algorithm |
| Output | Result produced by the algorithm |
| Definiteness | Steps are clear |
| Finiteness | Algorithm stops after limited steps |
| Effectiveness | Each step can be performed |
| A sixth property, Correctness (producing the right output for every valid input), is also crucial. | |
C Program Example
This C program implements a basic algorithm to find the largest number in an array.
#include <stdio.h>
int main() {
int arr[] = {14, 9, 27, 3, 18};
int largest = arr[0];
for (int i = 1; i < 5; i++) {
if (arr[i] > largest) {
largest = arr[i];
}
}
printf("Largest = %d", largest);
return 0;
}
Output:
Largest = 27
Key Points
- An algorithm is step-by-step logic for solving a problem.
- A valid algorithm must be finite, definite, effective, and correct.
- Algorithms take input and produce output.
- Efficiency is measured using time and space complexity.
Interview Tip
In interviews, explain the algorithm in plain English before writing code. It proves that you understand the logic.
Common Beginner Mistakes
- Writing code without first deciding the steps.
- Ignoring edge cases such as empty input or single-element input.
- Creating logic that works for one example but fails for general cases.
Quick Revision
- Algorithm = ordered finite steps.
- Good algorithms are clear, correct, and efficient.
- Every algorithm should have output.
- Time and space complexity help compare algorithms.
Summary
An algorithm is the heart of problem-solving in computer science. It provides a clear, step-by-step blueprint for transforming input into the desired output. For an algorithm to be considered valid, it must be finite, definite, and effective.
Understanding these fundamental properties is the first step toward designing algorithms that are not only correct but also efficient and reliable, forming the core skill set for any software developer.
