UNIT -2

Greedy Method in DAA

Greedy Method is an algorithm technique where we choose the best option at each step to solve a
problem.

Simple idea:

Take the best choice now and move ahead.

Key Points (Easy to Remember)

• Makes local best choice

• Hopes to get overall best solution

• Decision is final (no backtracking)

Steps of Greedy Method

1. Start with empty solution

2. Pick the best available choice

3. Add it to solution

4. Repeat until problem is solved

Where Greedy is Used

• Fractional Knapsack

• Prim’s Algorithm

• Kruskal’s Algoritm

Advantages

• Fast

• Uses less memory

Dynamic Programming in DAA

Dynamic Programming (DP) is a method used to solve problems by breaking them into smaller
subproblems, solving each only once, and storing the results for future use.

Simple idea:
Solve once, store it, reuse it.

Why Dynamic Programming?

• Avoids repeated calculations

• Saves time

• Gives optimal solution

Common DP Problems (Easy Names)

• 0/1 Knapsack

• Shortest Path (Floyd–Warshall)

Advantages
• Always gives correct (optimal) answer

• Reduces time complexity

Disadvantages

• Uses extra memory

• Harder than greedy

Greedy vs Dynamic Programming (Easy)

Greedy Dynamic Programming

Takes best step now Thinks of all steps

Faster Slower

May fail Always correct

Difference between Greedy Method and Dynamic Programming

The greedy method means choosing what looks best right now. It does not think much about the future.
Once a choice is made, it is not changed. This method is fast and simple, but sometimes it gives the wrong
result.
Real life example (Greedy):
You are very hungry and see snacks on the way home. You eat the first snack you find because you want
instant relief, without thinking that a better meal is waiting at home. This is greedy thinking — best choice at
the moment.
Dynamic programming means thinking step by step and considering all options. It breaks the problem into
smaller parts, solves each part carefully, and remembers the results. This method takes more time but always
gives the best solution.

Real life example (Dynamic Programming):

You plan a monthly budget. You write down all expenses (rent, food, travel), compare different choices,
and decide how to spend money so you save the most. You think about the future and use past data — this is
dynamic programming.

In Simple Words

Greedy is quick decision thinking.

Dynamic programming is planned decision thinking.

Fractional Knapsack Problem ( imp)

1. Definition

The Fractional Knapsack Problem is a problem in which we are given items with profit and weight, and a
knapsack with limited capacity.
We can take full items or fractions of items to maximize the total profit.

This problem is solved using the Greedy Method.

2. Key Idea (Very Easy)

• Calculate profit/weight ratio for each item

• Select items with highest ratio first

• If item cannot be fully added, take a fraction of it

3. Algorithm (Easy Steps)

Input:
Items with profit p[i], weight w[i]
Knapsack capacity W

Steps:

1. For each item, calculate p[i] / w[i]

2. Sort items in descending order of p/w
3. Set total profit = 0

4. For each item:

o If w[i] ≤ W, take full item

 ▪ Add profit, reduce capacity

o Else take fraction of item

▪ Add proportional profit

▪ Stop

5. Example (Very Easy)

Knapsack Capacity = 50

Item Profit Weight Profit/Weight

A 60 10 6

B 100 20 5

C 120 30 4

6. Step-by-Step Solution

1. Sort by profit/weight ratio:

A→B→C

2. Take item A:

o Weight = 10, Profit = 60

o Remaining capacity = 40

3. Take item B:
o Weight = 20, Profit = 100
o Remaining capacity = 20

4. Take 2/3 of item C:

o Profit = (20/30) × 120 = 80

7. Final Answer

Maximum Profit = 60 + 100 + 80 = 240

Job Sequencing with Deadlines

1. Definition (Simple)
Job sequencing with deadlines is a problem where we choose jobs in such a way that total profit is
maximum.
Each job has a deadline and a profit, and each job takes 1 unit time.
 Aim: Do the most profitable jobs before their deadlines

2. Simple Idea
• Do high profit jobs first

• Put each job before its deadline

• If no time is free → skip the job

3. Steps to Solve

1. Arrange jobs in decreasing order of profit

2. Find the largest deadline (this gives number of slots)

3. Create empty slots

4. Take jobs one by one:
o Put the job in the latest free slot before its deadline

5. Add profits of selected jobs

4. Example (Very Simple)

Job Deadline Profit

J1 2 100

J2 1 19

J3 2 27

J4 1 25

5. Final Answer

• Jobs done: J3, J1

• Total Profit = 27 + 100 = 127

1. Spanning Tree
A spanning tree is a way to connect all vertices of a graph:

• using no cycles
• using minimum number of edges

If a graph has V vertices, a spanning tree has V − 1 edges.

Simple Example (Diagram)

Original graph:

|\

|\
B--C

One spanning tree:

B_ C

✔ All vertices connected

✔ No cycle
✔ Edges = V – 1

2. Minimum Cost Spanning Tree

A minimum cost spanning tree (MCST) is a spanning tree in which the total cost of edges is minimum.

Meaning:
Out of all spanning trees, choose the one with least total weight.

Methods to Find Minimum Cost Spanning Tree

1. Prim’s Method

2. Kruskal’s Method

1. Prim’s Method (Easy Explanation)

Prim’s method is used to find the minimum cost spanning tree by starting from any one vertex and
growing the tree step by step.

How it works (steps):

1. Start with any vertex.

2. Select the minimum cost edge connected to the tree.

3. Add that edge and the new vertex to the tree.

4. Make sure no cycle is formed.

5. Repeat until all vertices are connected.
 Important point:
Prim’s method always looks at edges connected to the current tree.

Easy example idea:

Connecting houses one by one using the shortest wire from the already connected house.

2. Kruskal’s Method (Easy Explanation)

Kruskal’s method finds the minimum cost spanning tree by selecting edges in increasing order of cost.

How it works (steps):

1. Sort all edges by increasing cost.

2. Pick the smallest edge.

3. If it does not form a cycle, include it in the tree.

4. Repeat until the tree has (V − 1) edges.

Important point:
Kruskal’s method considers all edges, not starting from a single vertex.
Single Source Shortest Path
(Dijkstra’s Algorithm)
Dijkstra’s algorithm is a greedy method used to solve the single source shortest path problem when all
edge weights are non-negative.

. Basic Idea

• Start from the source node

• Always choose the node with the smallest distance

• Update distances of neighboring nodes

Steps of Dijkstra’s Algorithm

1. Set distance of source = 0

2. Set distance of all other vertices = ∞

3. Mark all vertices as unvisited

4. Select the unvisited vertex with minimum distance

5. Update distances of its adjacent vertices

6. Mark the vertex as visited

7. Repeat until all vertices are visited

Simple Example
Graph:

A ----- B

| |

1 2

| |
C ----- D

Source = A

Final Shortest Distances from A

• A→A=0
 • A→C=1

• A→B=4

• A→D=4

Optimal Binary Search Tree (OBST)( just learn itt fo exammm )

Dynamic Programming Method

1. Definition (Very Simple)

An Optimal Binary Search Tree is a binary search tree that has the minimum search cost when the
frequency of searching keys is known.

Keys searched more times are kept near the root.

2. Why Dynamic Programming?

• Many BSTs are possible

• We must find the best one

• Same subproblems repeat
So we use Dynamic Programming

3. Given Information

• Keys: k1, k2, ..., kn

• p[i]: probability of successful search

• q[i]: probability of unsuccessful search

4. Basic Idea (Easy)

• Try each key as root

• Calculate cost

• Choose the tree with minimum cost

5. Steps of Dynamic Method (Easy to Remember)

1. Make a table for cost

2. Start with small trees

 3. Increase tree size step by step

4. Choose root with least cost

5. Store result in table

6. Cost Formula (Simple)

Cost = level × probability

7. Advantages

• Gives minimum search cost

• No repeated work

Memory Trick

OBST = DP + Minimum Cost + Frequent Key Near Root

Travelling Salesman Problem (TSP)

1. Definition (Easy)

The Travelling Salesman Problem is a problem where a salesman must:

• visit every city exactly once

• return to the starting city

• with minimum total travel cost

2. Simple Real-Life Example

A delivery boy wants to deliver parcels to all houses and come back home using the shortest possible route.

3. Example

Suppose there are 4 cities: A, B, C, D

From/To A B C D

A 0 10 15 20

B 10 0 35 25

C 15 35 0 30
From/To A B C D

D 20 25 30 0

4. Possible Tours (Starting from A)

1. A → B → C → D → A
Cost = 10 + 35 + 30 + 20 = 95

2. A → B → D → C → A
Cost = 10 + 25 + 30 + 15 = 80

3. A → C → B → D → A
Cost = 15 + 35 + 25 + 20 = 95

4. A → C → D → B → A
Cost = 15 + 30 + 25 + 10 = 80

5. Final Answer

• Minimum cost = 80

• Optimal tour:
A→ B → D → C →A
(or A → C → D → B → A)

6. Important Exam Points

• Visit each city once

• Return to starting city

• Find minimum cost tour

• TSP is NP-hard

Memory Trick

TSP = All cities once + Return + Minimum cost