Chapter 3
Algorithm and Problem Solving
Computational Problem: it is a task that can be solved using step-by-step procedure and this
procedure is known as algorithm.
Algorithm: An algorithm is a set of clear, step-by-step instructions that a computer follows to solve a
problem or complete a task.
Components of a Computational Problem:
1. Input
• This is the information or data that we give to the computer.
• It could be a number, a list, text, or anything else the problem starts with.
Example:
In a problem where you want to sort names, the input is the list of names.
2. Output
• This is the result the computer gives after solving the problem.
• It depends on what the question is asking.
Example:
For sorting names, the output would be the list arranged in order (A to Z).
3. Conditions/Requirements/Process
• This is what the problem is asking you to do.
• It defines the rules or what should be achieved.
Example:
“Arrange the names in alphabetical order” – that’s the condition or goal of the problem.
Classification of Computation Problem:
Decision Problems:
These problems have a yes or no answer, like checking if a number is prime or if a password is correct.
Example: Is the number 17 a prime number? → Yes.
Search Problems:
The goal is to find something that meets certain conditions, such as searching for a name in a contact
list.
Example: Find a student in a list who scored more than 90%.
Optimization Problems:
These problems look for the best solution, like finding the shortest route or the lowest cost.
Example: Find the shortest route between two cities on a map.
Counting Problems:
They ask how many possible solutions exist, such as how many different ways to arrange books.
Example: How many different ways can you arrange 3 books?
Types of Problems
1. Well-defined Problems
These problems have clear input, output, and rules for solving them. The steps to reach the solution
are specific and unambiguous.
Example:
• Problem: Add two numbers.
• Input: 4 and 5
• Output: 9
The process is clear and easy to follow.
2. Ill-defined Problems
These problems are not clearly stated, and there may be multiple ways to define or solve them. The
goal or method might be vague or incomplete.
Example:
• Problem: Design a “good” website.
• What does "good" mean? Fast? Beautiful? Easy to use? The criteria are not clearly defined.
Algorithms for Problem Solving
An algorithm for problem solving is a step-by-step method used to find a solution to a problem. In
computer science, we use algorithms to solve different types of computational problems efficiently.
Generate and Test Algorithm
This algorithm works by generating potential solutions to a problem and then testing each one to
determine if it meets the required conditions. The process continues until a satisfactory solution is
found or all possible solutions have been exhausted.
The generate and test algorithm is useful in the scenario where:
• The problem space is small, making it feasible to generate and test all possible solutions.
There is no clear strategy for finding a solution, and a search is necessary.
Problem Solvability and Complexity
1. Problem Solvability
This tells us whether a problem can be solved by an algorithm or not.
• A problem is solvable if there is a clear algorithm that gives the correct result for all valid
inputs.
• A problem is unsolvable if no algorithm can solve it in all cases.
Example:
• Solvable: Sorting a list of numbers.
• Unsolvable: Determining if any computer program will run forever.
2. Problem Complexity
This describes how hard or how much time/memory a problem takes to solve using an algorithm.
There are two main types:
• Time Complexity: How long the algorithm takes as the input grows.
• Space Complexity: How much memory it uses as the input grows.
Solvable and Unsolvable Problems
Solvable Problems
These are problems for which we can write an algorithm that always gives the correct answer after a
finite number of steps.
Examples:
• Sorting a list of numbers (e.g., putting names in alphabetical order).
• Finding the largest number in a group.
• Checking if a number is even or odd.
In short, if a computer can solve the problem and finish, it’s solvable.
Unsolvable Problems
These are problems for which no algorithm exists that can solve the problem for all possible inputs.
No matter how much time or resources you have, you cannot guarantee an answer.
Examples:
• The Halting Problem: Determining if any computer program will stop running or run forever.
• Certain logic puzzles that don’t have a clear solution or decision process.
In short, these problems are impossible to solve by any computer program.
Tractable vs. Intractable Problems
Tractable Problems
These are problems that can be solved efficiently by an algorithm, meaning the solution can be found
in a reasonable amount of time as the input size grows. Usually, tractable problems have algorithms
that run in polynomial time. Tractable problems are considered "efficiently solvable."
Example:
• Sorting a list of numbers (Merge Sort runs in n log n time).
• Finding the shortest path in a graph with Dijkstra’s algorithm.
Intractable Problems
These problems cannot be solved efficiently; their algorithms take an exponential amount of time
(like 2^n) as input size grows. For large inputs, solving them becomes practically impossible, even if a
solution exists.
Example:
• The Traveling Salesman Problem (finding the shortest route visiting many cities).
• Many NP-complete problems.
Complexity Classes (P, NP, NP-hard, NP-complete)
1. P (Polynomial Time)
Definition:
P is the class of problems that can be solved by an algorithm quickly (in polynomial time), meaning
the time taken grows reasonably as the input size increases.
If a problem is in P, it means there is a known method to solve it efficiently for even large inputs.
Example:
Sorting a list of numbers using Merge Sort. If you have 1000 numbers, Merge Sort can sort them
quickly, and even if you have 1 million numbers, it can still do it in a reasonable time.
2. NP (Nondeterministic Polynomial Time)
Definition:
NP is the class of problems where, if someone gives you a possible solution, you can check or verify
that the solution is correct quickly (in polynomial time), but finding the solution might be hard.
You may not know how to solve the problem fast, but if given a candidate answer, you can easily
check it.
Example:
Solving a Sudoku puzzle can be difficult, but if someone hands you a completed board, you can
quickly check if all rows, columns, and blocks are valid.
3. NP-hard
Definition:
NP-hard problems are at least as hard as the hardest problems in NP. They may or may not be in NP
themselves, and solving an NP-hard problem quickly means you could solve all NP problems quickly.
These are very challenging problems, often used to show the difficulty of computational tasks.
Example:
The Traveling Salesman Problem (TSP) asks: “What is the shortest route that visits a list of cities and
returns to the start?” There’s no known efficient algorithm for large numbers of cities.
4. NP-complete
Definition:
NP-complete problems are both in NP (solutions can be verified quickly) and NP-hard (as hard as the
hardest NP problems).
They are considered the “core” of difficult problems — solving any one efficiently would solve all NP
problems efficiently.
Example: A classic example of an NP-Complete problem is the Knapsack Problem.
The Knapsack Problem: In the Knapsack Problem, you have a knapsack with a maximum weight
capacity and a set of items, each with a weight and a value. The goal is to determine the most
valuable combination of items to put in the knapsack without exceeding its weight capacity.
Algorithm Analysis
Algorithm analysis is the process of evaluating the efficiency and performance of an algorithm. It
helps us understand how an algorithm behaves as the size of the input data grows.
Time Complexity
Time complexity is a way to measure the amount of time an algorithm takes to run, based on the size
of its input (usually denoted as n). Instead of measuring real time (which can vary), it uses a
mathematical function to express how the running time scales as the input grows.
Why It's Useful:
Time complexity helps you:
• Predict how fast an algorithm runs.
• Choose the best algorithm for large data sets.
• Avoid performance issues in code.
Common Time Complexities (from best to worst):
Time Complexity Name Example Algorithm
O(1) Constant time Accessing an array element
O(log n) Logarithmic Binary search
O(n) Linear Linear search
O(n log n) Linearithmic Merge sort, Quick sort (avg)
O(n²) Quadratic Bubble sort, Insertion sort
O(2ⁿ) Exponential Recursive Fibonacci
O(n!) Factorial Solving Traveling Salesman
Big O Notation
Big O notation is a mathematical way to describe the upper bound (worst-case scenario) of an
algorithm's time or space complexity as the input size (n) grows.
It tells you how fast the runtime increases relative to the input size, not the exact time, but how it
scales.
O(1) – Constant Time
• Definition: The algorithm takes the same amount of time, no matter how big the input is.
• Example: Accessing an element in an array by index.
O(n) – Linear Time
• Definition: The time grows directly with the input size.
• Example: Printing all elements in a list.
O(n²) – Quadratic Time
• Definition: The time grows with the square of the input size.
• Example: Printing all pairs of elements (nested loop).
O(log n) – Logarithmic Time
• Definition: The time grows slowly as the input increases. The input is divided repeatedly.
• Example: Binary search in a sorted list.
Space Complexity
Space complexity refers to the amount of memory or space an algorithm needs to run to completion.
Example:
Imagine your computer has a backpack (memory).
When your program runs, it puts things into the backpack — like:
• Variables
• Arrays or lists
• Function calls (especially with recursion)
Space complexity tells you how full your backpack gets while your program is running.
Algorithm Design Techniques
Algorithm design techniques are general strategies or approaches used to develop efficient
algorithms to solve computational problems.
Divide and Conquer
Divide and Conquer is a fundamental algorithm design technique where a problem is broken into
smaller subproblems, each of which is solved independently and their results are combined to solve
the original problem.
Steps of Divide and Conquer
1. Divide:
Split the original problem into smaller subproblems of the same type.
2. Conquer:
Solve each subproblem recursively. If the subproblem is small enough, solve it directly (base
case).
3. Combine:
Merge the solutions of the subproblems into the final solution.
Examples: Sorting large datasets (Merge Sort, Quick Sort)
Searching (Binary Search)
What is a Greedy Algorithm?
A Greedy Algorithm is a method where we make the best choice at each step, hoping that this will
lead to the best overall solution.
• We don’t go back and change our choices.
• We always pick what looks best right now.
Real-life Example
Imagine you're collecting coins to make a certain amount of money (e.g., Rs.27), and you have coins
of Rs.10, Rs.5, Rs.2, and Rs.1.
A greedy way to do this:
1. Take as many Rs.10 coins as you can → Rs.10 + Rs.10 = Rs.20
2. Now take Rs.5 → Rs.25
3. Then Rs.2 → Rs.27 (done!)
You always choose the largest coin you can at each step.
That’s a greedy strategy!
Some More Examples:
2. Selecting TV Shows to Watch
You want to watch as many TV shows as possible in one evening, and none should overlap.
You have a list of shows with start and end times.
What would you do?
• Always pick the show that ends earliest, so you have more time left to watch others.
This is the activity selection problem, solved using a greedy approach.
3. Taking the Shortest Path to School
You ride your cycle to school. There are many roads, but you always choose the one that seems
shortest right now at every turn.
What are you doing?
• Making a greedy choice to get to school faster.
This is like Dijkstra’s Algorithm, used in maps and GPS!
Dynamic Programming in Algorithm Analysis
Dynamic Programming (DP) is a technique used to solve problems that can be divided into smaller,
overlapping subproblems, where the solution to the big problem depends on the solution to smaller
ones.
Instead of solving the same subproblems again and again, DP solves each subproblem only once and
stores the result — either using:
• Memoization (top-down approach)
• Tabulation (bottom-up approach)
Example: Fibonacci Series
So the series looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Each number is the sum of the two previous numbers.
The Fibonacci series is a sequence where each number is the sum of the two before it (e.g., 0, 1, 1, 2,
3, 5, 8...).
Using dynamic programming, we store previous results so we don’t repeat calculations, making it
much faster than simple recursion.
Backtracking
Backtracking is a method used to solve problems by trying all possible solutions and discarding
("backtracking") ones that don’t work.
It builds a solution step-by-step, and whenever it finds that a partial solution can’t lead to a valid full
solution, it goes back to the previous step and tries a different path.
Example: Puzzle Games, Graph Algorithms
Sorting Algorithms
Sorting algorithms are used to arrange data in a particular order — most commonly ascending or
descending.
Examples:
• Sorting numbers: [5, 2, 9] → [2, 5, 9]
• Sorting names: ["Zoe", "Alice"] → ["Alice", "Zoe"]
Why is Sorting Important?
• Makes searching faster (binary search needs sorted data)
• Helps in data organization
Bubble Sort
Bubble Sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they
are in the wrong order.
Example:
Sort: [5, 2, 4, 1]
Pass 1:
• Compare 5 and 2 → swap → [2, 5, 4, 1]
• Compare 5 and 4 → swap → [2, 4, 5, 1]
• Compare 5 and 1 → swap → [2, 4, 1, 5]
Pass 2:
• Compare 2 and 4 → no swap
• Compare 4 and 1 → swap → [2, 1, 4, 5]
• Compare 4 and 5 → no swap
Pass 3:
• Compare 2 and 1 → swap → [1, 2, 4, 5]
• No more swaps needed → done!
Time Complexity:
Case Time
Best (sorted) O(n)
Average O(n²)
Worst O(n²)
Space: O(1) (in-place)
Stable: Yes (does not change the order of equal elements)
Selection Sort
Selection Sort is a simple comparison-based sorting algorithm. It repeatedly selects the smallest (or
largest) element from the unsorted part of the list and moves it to the beginning of the sorted part .
Process
1. Start from the beginning of the array.
2. Find the minimum element in the unsorted part of the array.
3. Swap it with the first element of the unsorted part.
4. Move the boundary of the sorted part one step forward.
5. Repeat the process until the array is completely sorted.
Example
Sort the array: [64, 25, 12, 22, 11]
Step-by-step:
Pass Unsorted Part Minimum Swap With Resulting Array
1 [64, 25, 12, 22, 11] 11 64 [11, 25, 12, 22, 64]
2 [25, 12, 22, 64] 12 25 [11, 12, 25, 22, 64]
3 [25, 22, 64] 22 25 [11, 12, 22, 25, 64]
4 [25, 64] 25 25 [11, 12, 22, 25, 64]
Sorted Array: [11, 12, 22, 25, 64]
Time Complexity
Case Time Complexity Explanation
Best Case O(n²) Still compares all elements
Average Case O(n²) Nested loops for comparison and selection
Worst Case O(n²) Even if sorted, comparisons still happen
Space O(1) In-place sorting, no extra space used
Search Algorithm?
A search algorithm is a method for finding a particular item or set of items in a collection of data, or a solution
in a problem space. It systematically explores possible options and either finds the desired result or determines
that no solution exists.
Linear Search
Linear search (also called sequential search) is a simple search algorithm that checks each element of a list or
array one by one until the desired element is found or the end of the list is reached.
Process / How It Works
1. Start from the first element of the list.
2. Compare the target value with the current element.
3. If they match, return the index (or the element).
4. If not, move to the next element.
5. Repeat until:
o A match is found, or
o The end of the list is reached.
6. If no match is found, return a message like “Not Found” or -1.
Time Complexity
Case Time Complexity Explanation
Best Case O(1) Target is the first element.
Worst Case O(n) Target is at the end or not present.
Average O(n) On average, checks n/2 elements.
• n = number of elements in the list
When to Use Linear Search?
• The dataset is small or unsorted.
• Performance isn’t critical.
• You don’t want the overhead of sorting or more complex algorithms.
Example
Find the number 8 in the list:
[3, 5, 2, 8, 6]
Step-by-Step Procedure:
1. Start at the first number in the list.
o The first number is 3.
o Is 3 equal to 8? → No.
2. Move to the second number.
o The second number is 5.
o Is 5 equal to 8? → No.
3. Move to the third number.
o The third number is 2.
o Is 2 equal to 8? → No.
4. Move to the fourth number.
o The fourth number is 8.
o Is 8 equal to 8? → Yes!
5. Stop searching.
o You found the number 8.
o It is in position 4 in the list (if we count positions starting from 1).
Binary Search
Binary Search is a fast and efficient algorithm used to find an item in a sorted list or array by repeatedly dividing
the search range in half. It uses divide and conquer approach to solve any problem.
Key Requirement: The list must be sorted (in increasing or decreasing order).
Procedure
This is how binary search works, step by step:
1. Start with a sorted list.
2. Find the middle element of the list.
3. Compare the target value with the middle element:
o If it matches, the search is complete.
o If the target is less than the middle element:
▪ Repeat the search in the left half of the list.
o If the target is greater than the middle element:
▪ Repeat the search in the right half of the list.
4. Keep narrowing the range by half each time until:
o The target is found, or
o There are no more elements to search (in which case, the target is not in the list).
Example: Find 35
Sorted list: [5, 10, 15, 20, 25, 30, 35]
Step-by-step Binary Search:
1. Start with full list:
[5, 10, 15, 20, 25, 30, 35]
o First index = 0, Last index = 6
o Middle index = (0 + 6) ÷ 2 = 3 → Middle element = 20
Compare 35 with 20:
o 35 > 20 → Search in the right half.
2. New search range:
[25, 30, 35]
o First index = 4, Last index = 6
o Middle index = (4 + 6) ÷ 2 = 5 → Middle element = 30
Compare 35 with 30:
o 35 > 30 → Search in the right half again.
3. New search range:
[35]
o First index = 6, Last index = 6
o Middle index = (6 + 6) ÷ 2 = 6 → Middle element = 35
Compare 35 with 35:
o ✅ They are equal! Found it!
Complexity
Case Time Complexity Explanation
Best Case O(1) Target is the middle item.
Worst Case O(log n) Search range is halved each time.
Average O(log n) Very efficient for large data sets.
• n = number of elements in the list
Graph Algorithms
A graph is a data structure consisting of a set of vertices (nodes) and edges (connections) that
represent relationships between entities. Graph algorithms are a collection of well-defined steps or
procedures designed to solve computational problems on graphs, such as searching, finding shortest
paths, or detecting cycles.
1. Breadth-First Search (BFS)
Introduction
BFS is a way to visit nodes of a graph step by step, level by level. It starts from one node (root), then
visits all its direct neighbors first. It uses a queue and helps in finding the shortest path in unweighted
graphs.
Process
1. Start with a source vertex, mark it as visited.
2. Enqueue the source vertex.
3. While the queue is not empty:
o Dequeue a vertex.
o Visit all its unvisited neighbors and enqueue them.
Example
Graph:
A—B—C
| |
D—E
Adjacency list:
• A: [B, D]
• B: [A, C, E]
• C: [B]
• D: [A, E]
• E: [B, D]
Start BFS from A:
• Queue = [A], Visited = {A}
• Dequeue A → Visit B, D → Queue = [B, D], Visited = {A, B, D}
• Dequeue B → Visit C, E → Queue = [D, C, E], Visited = {A, B, D, C, E}
• Dequeue D → (A, E already visited) → Queue = [C, E]
• Dequeue C → (B already visited) → Queue = [E]
• Dequeue E → (B, D already visited) → Queue = []
Traversal Order: A → B → D → C → E
Time Complexity
• O(V + E) where
o V = number of vertices
o E = number of edges
• Each vertex and edge is processed once.
2. Depth-First Search (DFS)
Introduction
DFS is a way to visit nodes by going as deep as possible along one path before coming back. It starts
from one node (often root), goes deep into its neighbors, and backtracks when stuck. It uses recursion
or a stack and is good for exploring paths or finding cycles.
Process
1. Start with a source vertex, mark it as visited.
2. Visit one unvisited neighbor and go deeper recursively.
3. If no unvisited neighbors remain, backtrack.
4. Repeat until all vertices are visited.
Example
Using the same graph:
A—B—C
| |
D—E
Start DFS from A:
• Visit A → Visited = {A}
• Go to B → Visited = {A, B}
• From B → Go to C → Visited = {A, B, C}
• From C → No new neighbors → Backtrack to B
• From B → Go to E → Visited = {A, B, C, E}
• From E → Go to D → Visited = {A, B, C, E, D}
• From D → All neighbors visited → Backtrack fully
Traversal Order: A → B → C → E → D
Time Complexity
• O(V + E)
• Each vertex and edge are visited once.
Key Differences Between BFS and DFS
Feature BFS (Breadth-First Search) DFS (Depth-First Search)
Data Structure Queue (FIFO) Stack (LIFO) / Recursion
Exploration
Level by level Deep branch first
Style
Finds shortest path (unweighted
Path Finding Does not guarantee shortest path
graphs)
Memory Usage More (queue can grow) Less (stack/recursion)
Shortest path, social networks, web Cycle detection, topological sort,
Applications
crawling puzzles/mazes