MODULE IV

Computational Approaches to Problem-Solving

Computational approaches to problem-solving use the power of computers to solve complex
problems efficiently. This module covers key strategies such as:
• Brute Force: Trying all possible solutions to find the correct one.
• Divide-and-Conquer: Breaking a problem into smaller parts, solving each, and
combining the results.
• Dynamic Programming: Solving problems by reusing solutions to smaller
subproblems.
• Greedy Algorithms: Making the best choice at each step to find a solution.
• Randomized Approaches: Using randomness to explore solutions in an
unpredictable way.

BRUTE-FORCE APPROACH TO PROBLEM SOLVING

Concept of Brute-Force Approach

The brute-force approach is a fundamental problem-solving technique in which all possible solutions
are systematically tried until the correct one is found. It does not use shortcuts, or optimizations. Instead,
it relies on:

• Complete search of the solution space

• Simplicity and guaranteed correctness (if a solution exists)

• Often high time complexity because all possibilities must be checked

• Used when no better algorithm is available.

Brute-force is usually easy to understand and implement but becomes inefficient when the number of
possibilities grows large.

Characteristics of Brute-Force Solutions

1. Exhaustive Search: Every possible solution is examined without any optimization.
2. Simplicity: Easy to understand and implement.
3. Inefficiency: Often slow due to the large number of possibilities.
4. Guaranteed Solution: If a solution exists, the brute-force method will eventually find it.

Example 1: Padlock Combination Guessing

Imagine a padlock that has rotating dials.

Suppose the lock has 3 dials, with digits 0 to 9 on each.

So the possible combinations are from: 000, 001, 002, … up to 999

The brute-force method is to test each combination in order:

Algorithm:
1. Start with 000.
2. Increment sequentially: 001, 002, ..., 999.
3. Stop when the lock opens.
Why brute force works here

• There is no better clue to the correct combination.

• The number of combinations is limited.

• You will find the correct combination eventually.

Practical understanding

If the correct combination is 572, we will find it after trying all combinations up to 572.
If it is 999, we must try almost all possibilities.

This shows brute force is reliable but may require many attempts.

Example 2: Password Guessing

A brute-force password attack works by:

1. Generating all possible combinations of characters allowed in the password (letters, numbers,
symbols).

2. Trying each password one by one.

3. Comparing it with the actual password stored in the system.

4. Stopping only when the correct password is successfully matched.

This method does not use any intelligence or patterns.

It simply relies on exhaustive search.

2. Example for Clear Understanding

Suppose the password has:

• Length: 4 characters

• Allowed characters: only lowercase letters (a–z)

So possible passwords include:

aaaa, aaab, aaac, …, zzzz

The brute-force attacker tries all these possibilities in sequence.

If the correct password is “dbac”, then the attacker must try every combination from aaaa up to dbac.

The difficulty of brute-force password guessing increases rapidly as:

• The password becomes longer

• The number of allowed characters increases

For example:

If the password is 6 letters (a–z):

Total possibilities = 266 = 308 million

If the password is 6 characters (letters + numbers):

Total possibilities = 366 = 2.1 billion

If the password is 8 characters with symbols:

Possibilities can exceed trillions

So brute-force becomes impractical for strong passwords.

This increases the time needed to try all possibilities, making brute-force attacks unrealistic.
Divide and Conquer Algorithm

Divide and Conquer Algorithm is a problem-solving technique used to solve problems by dividing the
main problem into sub-problems, solving them individually and then merging them to find solution to
the original problem.

Working of Divide and Conquer Algorithm

The Divide and Conquer algorithmic approach consists of three main steps: Divide,
Conquer, and Merge.

1. Divide

• Goal: Break down the original problem into smaller, more manageable subproblems.
• Each subproblem represents a part of the overall problem.
• The division continues recursively until the subproblems are simple enough to solve
directly.

2. Conquer

• Goal: Solve each subproblem individually.

• If a subproblem is small enough (reaching a base case), it is solved directly without
further recursion.
• Each subproblem is processed independently to find its solution.
3. Merge

• Goal: Combine the solutions of the subproblems to form the solution to the original
problem.
• Once the subproblems are solved, their solutions are recursively merged to resolve the
overall problem efficiently.

Characteristics of Divide and Conquer Algorithm

1. Dividing the Problem

o The problem is recursively broken down into smaller subproblems until they
become simple enough to solve directly.
2. Independence of Subproblems
o Each subproblem is independent, meaning the solution of one subproblem
does not rely on another.
o This allows for parallel or concurrent execution of subproblems, improving
efficiency.
3. Conquering Each Subproblem
o After dividing the problem, each subproblem is solved individually, often
applying the divide and conquer strategy recursively.
4. Combining Solutions
o The solutions to the subproblems are merged to form the final solution.
o This merging step is designed to be efficient and seamless.

Examples of Divide and Conquer Algorithm:

Example1. Finding the Maximum Element in an Array Using Divide and Conquer

The Divide and Conquer algorithm can efficiently find the maximum element in an array by
following these steps:

• Divide:

• Split the array into two halves.

• Recursively divide each half until subarrays of size 1 are reached.

• Conquer:

• Once the subarrays have only one element, return that element as the maximum of
that subarray.

• Merge:

• Compare the maximums of the two halves and return the larger value as the maximum
for the combined array.
  If the section of the array has only one number, that number is the maximum.
 If it has more than one number, split it into two equal parts.
 Find the biggest number in the left part (by doing the same steps again).
 Find the biggest number in the right part (also by repeating the steps).
 Compare the two biggest numbers from each part.
 The larger of the two is the maximum for the whole array.

1. Start with the whole array:

38, 27, 43, 10
It has more than one number, so we split it into two parts:
• Left part: 38, 27
• Right part: 43, 10

2. Consider the left part (38, 27)

This still has two numbers, so we split again:
• First half: 38
• Second half: 27
Now each part has only one number.
So the maximums are:
• Max of left = 38
• Max of right = 27
Compare them: the larger one is 38.
So the maximum of the left side is 38.

3. Consider the right part (43, 10)

Split it again:
• First half: 43
• Second half: 10
These each have one number.
So the max values are:
• Max of left = 43
• Max of right = 10
 Compare them: the larger one is 43.
So the maximum of the right side is 43.

4. Now compare the results of the two sides

• Maximum on the left side = 38
• Maximum on the right side = 43
The larger of the two is 43.
 Example2: Merge Sort using Divide and Conquer

Merge Sort is a classic example of problem decomposition. It uses a divide-and-conquer

approach to sort an array.

1. Divide: The array is divided into two halves recursively until each subarray has one
element.
2. Sort: Each sub-array is sorted individually.
3. Merge: The sorted sub-arrays are merged to produce a single sorted array.

Consider an Example array [38, 27, 43, 3, 9, 82, 10]

ALGORITHM
1. Initial Array
[38, 27, 43, 3, 9, 82, 10]

2. First Split
According to the diagram:
Left part:
[38, 27, 43, 3]
Right part:
[9, 82, 10]

3. Sorting the Left Part: [38, 27, 43, 3]

Split again:
• [38, 27]
• [43, 3]
Split into single elements:
• [38] and [27]
• [43] and [3]
Merge back:
• Merge [38] and [27] → [27, 38]
• Merge [43] and [3] → [3, 43]
Merge the two sorted halves:
• Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
So the sorted left half is:
Left sorted = [3, 27, 38, 43]

4. Sorting the Right Part: [9, 82, 10]

Split:
• [9,82]
• [ 10]
Break [9, 82] into single elements:
• [9]
• [82]
Merge:
• Merge [9] and [82] → [9, 82]
Merge with the remaining element:
• Merge [10] and [9, 82] → [9, 10, 82]
So the sorted right half is:
Right sorted = [9, 10, 82]

5. Final Merge
Now merge the two sorted parts:
• Left sorted: [3, 27, 38, 43]
• Right sorted: [9, 10, 82]
Final merging sequence:
3
9
10
27
38
43
82
Final sorted array:
[3, 9, 10, 27, 38, 43, 82]
Advantages of the Divide and Conquer Approach
1. Reduces Problem Complexity
o By breaking a large problem into smaller subproblems, it becomes easier to
understand, solve, and manage.
o Each subproblem is less complex than the original problem.
2. Improved Performance for Many Problems
o Many algorithms (e.g., Merge Sort, Quick Sort, Binary Search) achieve better
time complexity using divide and conquer.
o This approach often transforms inefficient algorithms into much faster ones.
3. Independent sub problems
o Subproblems are often independent and can be solved simultaneously on multiple
processors.
o This makes divide and conquer suitable for parallel and distributed computing.
4. Reusability of Solutions
o Solutions to subproblems can be applied to similar problems.

Disadvantages of the Divide and Conquer Approach

1. May require a lot of Memory
Splitting the problem many times means storing extra function calls, which uses more
space
2. Not Suitable for All Problems
o Some problems cannot be easily divided into smaller independent subproblems.
o In such cases, divide and conquer becomes inefficient or impossible.
3. Combining Solutions Can Be Complex
o In certain problems, merging the results of subproblems into a final solution is
challenging.
o This increases algorithm complexity and implementation effort.
4. Risk of Redundant Computation
o If overlapping subproblems exist (without memoization), the same subproblems
may be solved repeatedly, leading to inefficiency.
o This is why some problems require dynamic programming instead.

PREVIOUS YEAR
You are working as a financial analyst for a bank. The bank has received a list of loan interest
rates from multiple branches, and you need to identify the two lowest rates to recommend the
most cost-effective options to customers. The rates are provided as an array of positive integers,
and your task is to develop an efficient algorithm using the Divide and Conquer approach to find
the sum of the two smallest rates. Explain with a suitable example.

The Divide and Conquer approach works in three steps:

1. Divide
Split the array into two halves until each sub-array contains either one or two elements.
2. Conquer
Find the two smallest elements in each half.
3. Combine
Compare the results from the left and right halves to determine the overall smallest and second
smallest elements.
This approach avoids scanning the entire array sequentially, distributing the comparison work
across subproblems.
Lets us consider the loan rates
[12, 5, 18, 7, 3, 10]
We need the sum of the two smallest rates.

1. Divide the array

Split into two halves:
Left: [12, 5, 18]
Right: [7, 3, 10]

2. Conquer each half

Left Half: [12, 5, 18]
Split:
• [12]
• [5, 18]
Split again where needed:
• [5], [18] → merge → smallest = 5, second smallest = 18
Now combine with [12]:
Compare:
• Among 12, 5, 18 →
smallest = 5, second smallest = 12
Result for left half:
(5, 12)

Right Half: [7, 3, 10]

Split:
• [7]
• [3, 10]
Split further:
• [3], [10] → merge → smallest = 3, second smallest = 10
Combine with [7]:
Among 7, 3, 10 →
smallest = 3, second smallest = 7
Result for right half:
(3, 7)

3. Combine results of both halves

Left half: (5, 12)
Right half: (3, 7)
Now find the two smallest values from:
• 5, 12, 3, 7
Smallest = 3
Second smallest = 5

Final Output
Two smallest loan rates:
3 and 5
Sum:
3+5=8

Qn) Illustrate the process of sorting the array [15, 8, 3, 12, 6, 10, 4, 1] using the merge sort algorithm.
Draw a diagram showing how the array is split and merged at each stage. (Do it Yourself)
Dynamic Programming Approach

Dynamic programming is a way to solve problems by breaking them into smaller

parts, solving each small part only once, and then reusing those answers
instead of solving them again.

GENERAL ALORITHM

1. Breakdown Complex problems to sub problems

2. Find the optimal solutions to the sub problems
3. Store the results of sub problems
4. Reuse the results of sub problems to avoid repeated calculations
5. Finally find the result of complex problem

Dynamic Programming (DP) is a problem-solving technique used to solve

problems that can be broken down into overlapping subproblems and follow an
optimal substructure (the optimal solution of a problem can be built from
optimal solutions of its subproblems).

Dynamic programming stores the results of subproblems so they do not need to

be recomputed.

This makes it much faster than simple recursion when the same subproblems
repeat.

Key ideas of Dynamic Programming

1. Overlapping Subproblems
Same subproblems appear again and again.
2. Optimal Substructure
The best solution can be formed by combining smaller optimal solutions.
3. Memoization or Tabulation
DP stores intermediate results:
o Memoization → top-down
o Tabulation → bottom-up
 ⭐ MEMOIZATION (Top-Down)

Memoization means: Solve when needed, and remember the answer.

• Uses recursion
• Every time we solve a small problem, we store the result.
• Uses extra memory to store results
• Execution direction: Top → Down
• Avoids repeated calculation of the same subproblem. If we face the same small problem
again, we don’t solve it again — we just look up the stored answer
• Efficient for problems where only some subproblems are needed

⭐ TABULATION (Bottom-Up)

Tabulation means: Start from the easiest problem and build up the answer step
by step.

• Use a table (usually an array) to store the values.

• Uses iteration (loops)
• No recursion → no stack overflow
• Execution direction: Bottom → Up
• Computes all subproblems from smallest problem → biggest problem
• Usually faster due to no recursive overhead

Memoization: Remember answers while going down through recursion.

Tabulation: Build answers while going up through a table.

Generate the Fibonacci series up to n terms using recursive method

(Memoization)

Consider n = 5 ; We know fib(0) = 0 and fib(1) = 1

Start from the big problem (fib(5)), compute answers with recursion, save every fib(k) you
compute, and reuse saved answers so you never compute the same fib value twice.
Assume we start computing fib(5):
1. Compute fib(5) → needs fib(4) and fib(3).
2. Compute fib(4) → needs fib(3) and fib(2).
3. Compute fib(3) → needs fib(2) and fib(1).
4. Compute fib(2) → needs fib(1) and fib(0).

o fib(1) = 1, fib(0) = 0, so fib(2) = 1.

Save fib(2) = 1. (Stored in an array , let’s say memo=[0,1,1,?,?,?])

5. Back to fib(3):
now fib(2) is in memo, so reuse memo[2] and fib(1) to get fib(3) = 2.
Save fib(3) = 2.

6. Back to fib(4):
fib(3) is in memo, fib(2) is in memo → fib(4) = 3.
Save fib(4) = 3.

7. Back to fib(5):
fib(4) and fib(3) are now in memo → fib(5) = 5.
Save fib(5) = 5.

So each fib(k) is computed once and all later requests use the saved value.

Without memoization:
• F(3) needs to be calculated many times
• F(4) needs to be calculated many times
•
With memoization:
• Once F(3) = 2 is stored, every future call simply uses the stored value, making the
algorithm much faster.

Fib(5)

Fib(4) Fib(3)

Fib(2) Fib(1)
Fib(3) Fib(2)

Fib(1) Fib(0)
Fib(2) Fib(1) Fib(1) Fib(0)

Fib(1) Fib(0)
 How the memo (table) fills for n = 5 (step by step)

Start: memo = [?, ?, ?, ?, ?, ?] (? = unknown)

• Base values returned directly when needed: fib(0)=0, fib(1)=1
• After computing fib(2) → memo = [0, 1, 1, ?, ?, ?]
• After fib(3) → memo = [0, 1, 1, 2, ?, ?]
• After fib(4) → memo = [0, 1, 1, 2, 3, ?]
• After fib(5) → memo = [0, 1, 1, 2, 3, 5]
Final answer fib(5) = 5.

Generate the Fibonacci series up to n terms using Tabulation

Tabulation means:
Start from the smallest problem, fill a table step by step, and
working up to the final answer.

No recursion is used.

Everything is done using a table (usually an array).

How Tabulation Works (Example: Fibonacci)

We want to compute F(6).

We create a table of size 7 (from 0 to 6):

Start:
i: 0 1 2 3 4 5 6
fib: [ ? ? ? ? ? ? ?]

Step 1 — Fill base values

fib[0] = 0
fib[1] = 1
Table: [0 1 ? ? ? ? ?]

Step 2 — Fill the rest of the table one by one

• fib[2] = fib[1] + fib[0] = 1 + 0 = 1
[0 1 1 ? ? ? ?]

• fib[3] = fib[2] + fib[1] = 1 + 1 = 2

[0 1 1 2 ? ? ?]

• fib[4] = fib[3] + fib[2] = 2 + 1 = 3

[0 1 1 2 3 ? ?]

• fib[5] = fib[4] + fib[3] = 3 + 2 = 5

[0 1 1 2 3 5 ?]
 • fib[6] = fib[5] + fib[4] = 5 + 3 = 8
[0 1 1 2 3 5 8]

Final answer:
fib(6) = 8

Diagram (Bottom-Up filling)

Start → [0] [1] [ ] [ ] [ ] [ ] [ ]
↓
Fill fib(2) → [0] [1] [1] [ ] [ ] [ ] [ ]
↓
Fill fib(3) → [0] [1] [1] [2] [ ] [ ] [ ]
↓
Fill fib(4) → [0] [1] [1] [2] [3] [ ] [ ]
↓
Fill fib(5) → [0] [1] [1] [2] [3] [5] [ ]
↓
Fill fib(6) → [0] [1] [1] [2] [3] [5] [8]

Comparison Between Recursion and Dynamic Programming

Dynamic Programming
Aspect Recursion
(DP)
Solving complex
Solving a problem
problems by breaking
by calling the same
them into smaller
Definition function on smaller
subproblems and saving
parts of the
their results to avoid
problem.
repeating work.
Can be Top-down
Top-down: start
(memoization) or
from the main
Bottom-up (tabulation);
Approach problem and go
deeper into smaller
avoids recmputation by
problems.
storing results.
Essential for Same base cases, but
Base Case stopping recursion stored directly in a table
(e.g., fib(0), fib(1)). or memo.
Can be slow due to Much faster because
repeated each subproblem is
Performance
calculations of the solved only once and
same subproblems. reused.
Time Higher Lower
Complexity Often exponential Usually polynomial or
 Dynamic Programming
Aspect Recursion
(DP)
linear
Uses extra table/memo
Uses recursion
Memory array, but avoids large
stack, which can
Usage recursion stacks
grow deep.
(especially in tabulation).
Less efficient when Highly efficient when
Efficiency subproblems repeat subproblems overlap and
many times. results can be reused.
Suitable for
problems with Best for problems with
natural recursive overlapping subproblems
Use Cases
structure and no and optimal
repeated substructure.
subproblems.
When performance
When simplicity is
When to matters and the problem
preferred and input
Use has repeated
size is small.
subproblems.
Fibonacci (DP), Knapsack
Fibonacci (naive problem, Longest
recursion), Tree Common Subsequence,
Examples
traversal, Factorial, Matrix Chain
Tower of Hanoi. Multiplication, Shortest
paths.

PREVIOUS YEAR

Compare Dynamic Programming and Recursion in terms of

their approach, efficiency, and use cases.

What is memoization, and how does it differ from

tabulation in dynamic programming?

Explain memoization and tabulation techniques in dynamic

programming for calculating the n-th Fibonacci number
Greedy Algorithm for Problem Solving

A Greedy Algorithm is a problem-solving approach that builds up a solution piece

by piece, always choosing the option that looks best at every step. It focuses on
making a sequence of locally optimal choices, with the hope that these decisions
will lead to a globally optimal solution.

A greedy algorithm is a problem-solving approach where you make the best local
choice at each step, hoping it leads to the best overall solution.

A greedy algorithm builds a solution step by step, and at each step it chooses the
option that looks best right now — the local optimum — hoping that repeated
local choices produce a global optimum.

• Locally Optimal Choices: At each step, the algorithm optimizes for the immediate
constraint (time, cost, practicality) without revisiting earlier decisions.
• Global Solution: The sequence of locally optimal decisions leads to an efficient and
practical final solution.

Qn) Given an array of positive integers, each indicating the completion time for a
task, find the maximum number of tasks that can be completed in the limited
amount of time that you have.

We are given an array of positive integers where:

• Each element represents the time required to complete a task
• We have a limited total available time
• Our goal is to complete as many tasks as possible

Greedy Strategy
To maximize the number of tasks completed:
✔ Always choose the tasks that take the least time first.

This ensures the completion of the maximum number of tasks within your total
time.

Consider:
Completion times for tasks:
[2, 3, 1, 4, 6]
Total available time:
8

Step-by-Step Solution Using Greedy

Step 1: Sort the task times (ascending)
Sorting gives:
[1, 2, 3, 4, 6]

Step 2: Iterate through tasks and accumulate time

Task Time New Total Time Task Count Allowed?
1 1 1 ✔
2 3 2 ✔
3 6 3 ✔
4 10 — exceeds 8
We stop here because adding 4 would exceed the available time.

Final Answer
✔ Maximum tasks completed = 3
The tasks with times 1, 2, and 3 can be completed within the total available
time 8.

Example: Traveling from Thiruvananthapuram to Ernakulam Using the

Greedy Approach

Let’s consider the task of traveling from Thiruvananthapuram to Ernakulam with multiple
available modes of transport: bike, car, bus, train, airplane, or even walking. The goal is to
select the mode of transport based on a set of constraints or objectives:

1. Minimizing Travel Time

2. Minimizing Cost
3. Satisfying Practical Constraints

Step 1: Apply the Greedy Approach

At each step, the greedy algorithm makes the locally optimal choice by filtering options
based on the immediate constraint.

Stage 1: Minimize Travel Time

To reach the destination quickly, we first prioritize speed.

• Available Options:
o Bike: 6 hours
 o Car: 4.5 hours
o Bus: 5 hours
o Train: 3.5 hours
o Airplane: 1 hour
o Walking: 40 hours

Greedy Decision:
Select modes that satisfy the time constraint of reaching as quickly as possible. The airplane
(1 hour) is the fastest, followed by the train (3.5 hours).

Filter Outcome:
Airplane, Train.

Stage 2: Minimize Cost (Economical Constraint)

Among the remaining options, we now focus on minimizing cost.

• Cost of Airplane: ₹3,500

• Cost of Train: ₹500

Greedy Decision:
Select the train as it is cheaper and satisfies the economical constraint.

Filter Outcome:
Train.

Stage 3: Practical Constraints

Lastly, consider practical constraints like availability of tickets, comfort, or personal

preferences. If the train has tickets available and meets other needs, it will be chosen.

Final Decision

The algorithm selects the train as the final mode of transport based on:

2. Minimizing time (after filtering slower options).

3. Minimizing cost.
4. Satisfying practical constraints

Example: Coin Changing Problem

The Coin Changing Problem aims to find the minimum number of coins required to make a
specified amount using valid Indian Rupee coins.
The greedy algorithm repeatedly selects the largest denomination that fits into the remaining
amount.

Valid Indian Coin Denominations:

₹1, ₹2, ₹5, ₹10

To make ₹18 using the greedy algorithm:

1. Start with ₹10: Take one ₹10 coin (₹18 - ₹10 = ₹8 left).
2. Next, ₹5: Take one ₹5 coin (₹8 - ₹5 = ₹3 left).
3. Next, ₹2: Take one ₹2 coin (₹3 - ₹2 = ₹1 left).
4. Finally, ₹1: Take one ₹1 coin (₹1 - ₹1 = ₹0 left).

Total coins used: 4

(1×₹10, 1×₹5, 1×₹2, 1×₹1).
Motivations for the Greedy Approach

The Greedy Approach is an effective problem-solving strategy due to several key

motivations:

1. Simplicity and Ease of Implementation

o Straightforward Logic: Makes optimal local choices, simplifying
understanding and implementation.
o Minimal Requirements: Requires less complex data structures

2. Efficiency in Time and Space

o Fast Execution: Suitable for large inputs.
o Low Memory Usage: Uses minimal memory by avoiding extensive
intermediate storage.
3. Optimal Solutions for Specific Problems
o Greedy-Choice Property: Local optimal choices lead to a global optimum.
o Optimal Substructure: Global optimal solutions can be built from optimal
subproblem solutions.
4. Real-World Applicability
o Practical Applications: Used in scheduling, network routing, and resource
allocation.
o Quick, Near-Optimal Solutions: Offers efficient solutions when exact results
aren't necessary.

Characteristics of Greedy Algorithms

1. Local Optimization
o Makes the best possible choice at each step using only current state
information.
2. Irrevocable Decisions
o Choices are final; no backtracking or revision of earlier decisions.
3. Problem-Specific Heuristics
o Relies on heuristics tailored to the problem's properties for decision-making.
4. Optimality

o Guarantees optimal solutions for problems like coin change, Huffman coding,
and Kruskal's algorithm, but not universally applicable.
5. Efficiency
o High efficiency in time and space due to reliance on local information and
limited exploration of solutions.
Comparison between Dynamic programming and Greedy Approach

Advantages and Disadvantages

• Advantages

• Easy to implement: Greedy algorithms are relatively easy to understand and

implement.

• Time complexity: Greedy algorithms usually have a smaller time complexity.

• Optimization: Greedy algorithms can be used for optimization or to find solutions

that are close to optimal for hard problems.

• Disadvantages

• Not guaranteed to find the best solution: Greedy algorithms may not find the best
solution because they don't consider all the data.

• Local optima: Greedy algorithms may get stuck in local optima and fail to find the
global optimum.

• Lack of backtracking: Once a decision is made, it cannot be undone.

• Dependence on problem structure: Greedy algorithms may not work well for
problems that don't fit the greedy paradigm.

• Lack of rigorous proof: Greedy algorithms often lack a rigorous proof of correctness
Randomized Approach to Problem Solving
A randomized approach is a method of solving a problem where the algorithm
makes random choices during its process.
These random choices help:
• make the algorithm simpler,
• avoid worst-case situations,
• and sometimes make it faster.

A randomized approach means the algorithm uses “luck” or random numbers to decide what to do next.

Comparison: Randomized vs. Deterministic Methods

Feature Deterministic Approach Randomized Approach

Always follows the same steps Uses random choices during the
Definition and gives the same result for process; results may differ each
the same input. time.
Unpredictable; may take
Behavior Predictable and fixed.
different paths each run.
Usually the same output, but
Always the same for the same
Output the process or time taken can
input.
vary.
Worst-case and average-case Often avoids worst cases and
Performance
may be predictable. performs well “on average”.
Good when deterministic
Good when we need reliable
Usefulness methods are slow or get stuck
and repeatable results.
in bad cases.
Randomized QuickSort,
Binary Search, Merge Sort,
Examples Randomized Search,
Dijkstra’s Algorithm.
Randomized Primality Test.

• Randomized:
o Incorporates chance.
o Efficient for large, complex, or variable datasets.
o Example: Estimating customer satisfaction via random sampling.
 • Deterministic:
o Yields exact, repeatable results.
o Suitable for precision-critical problems.
o Example: Exact cost calculation in shopping.

Qn) A company selling jeans gives a coupon for each pair of jeans. There are n different
coupons. Collecting n different coupons would give you free jeans. How many jeans do you
expect to buy before getting a free one? explain this using randomised approach.

Problem statement
• A company has n different coupons.
• Every time you buy a pair of jeans, you get one coupon chosen at random from the n
coupons.
• Collecting all n different coupons gives you a free pair of jeans.
• Each purchase is independent of the previous ones.

1. Model it as a random process:

• Every purchase gives a coupon chosen completely at random.
• Each purchase is independent of the previous ones.

2. Break it into stages:

o Stage 1: Getting your first new coupon (no coupons yet).
o Stage 2: Getting your second new coupon (you already have 1).
o Stage 3: Getting your third new coupon (you already have 2).
o … and so on until you collect the nth coupon.

Let
• X = number of jeans needed to get the i-th new coupon after already having 𝑖 −
1coupons.

• Total jeans needed:

𝑋 = 𝑋1 + 𝑋2 + 𝑋3 + ⋯ + 𝑋𝑛
3. Estimate purchases for each stage:
First coupon: you always get a new one → need 1 purchase.
E[X1]=1

Second coupon: some coupons are repeats, so it may take a few tries to get a new
one.
E[X2]=(n−1)/n1= (n−1) / n

Third coupon: probability of getting a new one decreases, so you need even more
tries.
E[X3]=(n−2) / n

Last coupon
E[Xn]=1 / n= n
• Add them up:
1. The total expected number of jeans = sum of the expected purchases for all stages.
2. As a result, you usually need more than n purchases.
 E[X]=E[X1]+E[X2]+E[X3]+⋯+E[Xn]=n(1+1/2+1/3+⋯+1/n)

• Suppose there are 5 different coupons.

• Expected number of jeans to buy: roughly 11 or 12.
•
o First coupon → 1 jean
o Second coupon → maybe 1–2 more
o Third coupon → maybe 1–3 more
o …
o By the end, the total adds up to about 11–12 jeans.

E[X]=5(1+1/2+1/3+1/4+1/5)≈5×2.2833≈11.4

So, expect to buy about 11 or 12 jeans to collect all 5 coupons.

Qn) n people go to a party and drop off their hats to a hat-check person. When the party is over,
a different hat-check person is on duty and returns the n hats randomly back to each person.
What is the expected number of people who get back their hats? Explain this using randomized
approach

Problem Statement
• There are n people at a party.
• Each person gives a hat to the hat-check person.
• When they leave, a different hat-check person returns the hats randomly.

Step 1: Model it as a random process

1. Each hat is given back completely randomly.
2. Each person has a 1/n chance of getting their own hat.

Step 2: Define indicator variables

Let’s use a simple way to think:
• Let 𝑋𝑖 = 1if a person i gets their own hat, otherwise 𝑋𝑖 = 0.
• Total people who get their hats back:
𝑋 = 𝑋1 + 𝑋2 + 𝑋3 + ⋯ + 𝑋𝑛

Step 3: Expected value for each person

• Probability person i gets their own hat: 𝑃(𝑋𝑖 = 1) = 1/𝑛
• Expected value:
𝐸[𝑋𝑖 ] = 1 ⋅ (1/𝑛) + 0 ⋅ (1 − 1/𝑛) = 1/𝑛
Step 4: Add up expectations
Using linearity of expectation:
𝐸[𝑋] = 𝐸[𝑋1 + 𝑋2 + ⋯ + 𝑋𝑛 ] = 𝐸[𝑋1 ] + 𝐸[𝑋2 ] + ⋯ + 𝐸[𝑋𝑛 ] = 𝑛 ⋅ (1/𝑛) = 1

• Even though the hats are returned randomly, on average 1 person will get their own hat
back.
• It doesn’t matter how many people there are — the expected number is always 1.

Suppose:
• There are 4 people and 4 hats.
• Everyone gets a hat randomly.
• Check how many got their own hat → sometimes 0, sometimes 2, sometimes more.
• But on average, 1 person will get their own hat.

Person 1 → Hat 1
Person 2 → Hat 2
Person 3 → Hat 3
Person 4 → Hat 4

Person 1 → Hat 3
Person 2 → Hat 2 (correct!)
Person 3 → Hat 1
Person 4 → Hat 4 (correct!)

In this example, 2 people got their own hat, but the number can vary each time. On average
one person gets their hat.

Motivations for Randomized Approach

• Easy to implement – Simulations are simpler than exact formulas(deterministic

formulas).
• Handles complex problems – Works when analytical solutions are hard or impossible.
• Estimates probabilities – Approximates outcomes without full calculations.
• Flexible / Versatile – Can adapt to different scenarios or changing conditions.
• Improves performance – Faster for large or complicated systems than exact methods.
• Reduces complexity – Avoids complicated mathematical derivations.

OTHER EXAMPLES

[Link] Carlo Simulation (Estimating Circle Area)

Problem: Estimate the area of a circle inscribed in a square.
Approach:
1. Draw a square of side length 2r and a circle of radius r inside it.
2. Randomly place a large number of points (x, y) inside the square.
3. For each point, check if it lies inside the circle using the formula:
4. x^2 + y^2 <= r^2
5. Count how many points fall inside the circle (count_inside).
6. Estimate area of the circle:
7. Area ≈ (count_inside / total_points) * area_of_square
Randomized part: Choosing points randomly inside the square.

[Link] Problem
Problem: Find the probability that at least two people in a group share the same
birthday.

Randomized Algorithm:
1. For a group of n people, assign a random birthday to each person (1–365).
2. Check if any two birthdays match.
3. Repeat this simulation many times.
4. Record how often at least two birthdays match.
5. Estimate the probability based on these simulations.
Probability ≈ count_matches / total_trials

Randomized part: Assigning birthdays randomly for each simulation.

[Link] Walk on a Grid

Problem: Expected return time to the starting point for a person taking random steps.
Randomized Algorithm:
1. Place a person at the starting point (0,0) on a grid.
2. At each step, randomly choose a direction: up, down, left, or right.
3. Continue moving until the person returns to the starting point.
4. Record the number of steps taken.
5. Repeat this process many times and compute the average return time.

Randomized part: Choosing directions randomly at each step.

[Link] Coin Flips

Problem: Estimate the probability distribution of heads in a series of coin flips.
Randomized Algorithm:
1. Decide the number of flips n.
2. For each flip, randomly generate a result: heads (H) or tails (T) with equal probability.
3. Count the number of heads in each trial.
4. Repeat the experiment many times.
5. Build the distribution of heads by recording the results.

Randomized part: Each coin flip outcome is random.

Monte Carlo Simulation (Estimating Circle Area)

• Why Randomized: Points are placed randomly in the square.
• Randomness is key: The estimation depends on random sampling.
• Type: Randomized algorithm for probabilistic estimation.

2. Birthday Problem
• Why Randomized: Birthdays are simulated randomly in a group.
• Randomness is key: Probability is estimated by repeated random trials.
 • Type: Randomized simulation to estimate combinatorial probability.

3. Random Walk on a Grid

• Why Randomized: Each step is chosen randomly (e.g., left, right, up, down).
• Randomness is key: Behavior of the walk is probabilistic.
• Type: Randomized simulation to study stochastic processes.

4. Random Coin Flips

• Why Randomized: Each coin flip outcome is random.
• Randomness is key: Probability distribution is estimated from repeated trials.
• Type: Randomized experiment for empirical probability.

Problem Randomized Step Purpose

Circle Area Randomly place points in square Estimate area
Birthday Problem Randomly assign birthdays Estimate probability
Random Walk Randomly pick a direction Estimate return time
Coin Flips Randomly simulate flips Build probability distribution