Introduction to Algorithms

Exploring the foundational

concepts and diverse
paradigms that drive
computational problem-
solving.

Dr. Moutushi Singh

Professor & Head
Department of Computer Science & Engg. & Information Technology
Institute of Engineering & Management,
University of Engineering & Management, Kolkata

preencoded.png
1 What is an Algorithm? 2 Algorithm Analysis
Defining the core concept and its importance in Evaluating efficiency and complexity using
computing. mathematical tools.

3 Algorithmic Paradigms 4 Real-World Applications

Deep dive into Divide and Conquer, Greedy, Dynamic Connecting theory to practical computational
Programming, and Branch & Bound. problems.

preencoded.png
What is an Algorithm?
At its core, an algorithm is a finite set of well-defined, unambiguous instructions for solving a
problem or performing a computation. It's a step-by-step procedure that takes an input,
processes it, and produces a desired output.
Algorithms are the backbone of all software and computational systems, from simple
calculations to complex artificial intelligence models. Their clarity and precision are paramount
for reliable execution.

Characteristics of a Good Algorithm

1.Input: It should accept zero or more inputs.
2.Output: It should produce at least one output.
3.Finiteness: It must terminate after a finite number of steps.
4.Definiteness: Each step must be precisely defined and unambiguous.
5.Effectiveness: Every step must be basic enough to be carried out, in principle, by a human
using pen and paper.

preencoded.png
 Why Do We Study Algorithms?
•To solve problems efficiently and correctly.
•To compare various approaches to the same problem.
•To choose the most optimal solution based on time and space.
•Algorithms are the foundation of all software development.
Algorithm Analysis
The performance of an algorithm is measured using:
1.Time Complexity: Amount of time an algorithm takes relative to input size.
2.Space Complexity: Amount of memory an algorithm uses.
We use Asymptotic Notations to describe performance:

Notation Meaning
O(f(n)) Upper bound (Worst-case)
Ω(f(n)) Lower bound (Best-case)
Θ(f(n)) Tight bound (Average-case)

preencoded.png
 Real-Life Analogy
An algorithm is like a cooking recipe:
•Ingredients = Inputs
•Cooking steps = Process
•Prepared dish = Output

Example
Step 1: Start
Step 2: Read two numbers A and B
Step 3: Compute SUM = A + B
Step 4: Display SUM
Step 5: Stop

preencoded.png
 Algorithm Analysis

Analyzing algorithms involves determining the computational resources (time and space) required to execute them. This
evaluation is crucial for comparing algorithms and choosing the most efficient one for a given problem.

O(n) O(1) 2x
Space Complexity Scalability
Time Complexity
Measures how the runtime of an Quantifies the amount of memory an Refers to an algorithm's ability to handle

algorithm grows with the input size (n), algorithm needs to run, excluding input increasing amounts of data or workload

often expressed using Big O notation. storage. efficiently.

preencoded.png
Divide and Conquer
This paradigm involves breaking down a problem into two or more smaller sub-problems of the same or related type, solving them
recursively, and combining their solutions to get the solution for the original problem.

Conquer
Solve the sub-problems recursively.

Divide
Break the problem into smaller sub-
problems.
Combine
Merge the solutions of sub-problems to
get the final solution.

Examples: Merge Sort, Quick Sort, Binary Search. preencoded.png

Greedy Algorithms
A greedy algorithm makes the locally optimal choice at each stage with the hope of
finding a global optimum. It builds up a solution piece by piece, always choosing the
next piece that offers the most obvious and immediate benefit.

While simple and intuitive, greedy algorithms don't always yield the globally optimal
solution. They work best for problems exhibiting the "greedy choice property" and
"optimal substructure."

preencoded.png
Dynamic Programming
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It
solves each subproblem only once and stores their solutions to avoid redundant computations.

Overlapping Subproblems Optimal Substructure

Problem can be broken into subproblems that are reused An optimal solution to the problem contains optimal
many times. solutions to its subproblems.

Examples: Fibonacci sequence, Longest Common Subsequence, Knapsack Problem (0/1).

preencoded.png
Branch and Bound
Branch and Bound (B&B) is a general algorithm design paradigm, primarily for discrete and combinatorial optimization problems. It systematically explores all possible solutions but prunes branches that
cannot lead to an optimal solution, using bounding functions.

Branching

Dividing the problem into smaller subproblems (nodes in a search tree).

Bounding

Calculating upper and lower bounds for the optimal solution in each subproblem.

Pruning

Discarding subproblems whose bounds indicate they cannot contain the optimal solution.

preencoded.png
 Summary Comparison
Overlapping Sub-
Technique Optimality Complexity Example Problem
problems
Merge Sort, Binary
Divide and Conquer Usually Yes No O(n log n), etc
Search
Greedy Not always No O(n log n), etc Dijkstra, Kruskal
Knapsack, LCS, Matrix
Dynamic Programming Yes Yes O(n²), O(n³)
Multiplication
Branch and Bound Yes Sometimes Exponential TSP, 0/1 Knapsack

preencoded.png
Key Takeaways & Next Steps
1 Algorithmic Diversity 2 Importance of Analysis 3 Practical Application
Understanding various Efficiency metrics (time/space Algorithms are not just
paradigms helps in choosing the complexity) are critical for theoretical concepts; they power
best approach for different building scalable and performant every aspect of modern
problem types. software. computing.

Next Steps: Explore specific algorithms within each paradigm, practice implementing them, and analyze their performance on
various datasets.

preencoded.png