Chapter 3 Greedy Approach
Dijkstra Algorithm
1. Initialize distances:
o Set the distance to the source node as 0.
o Set the distance to all other nodes as infinity.
2. Mark all nodes as unvisited.
3. Pick the unvisited node with the smallest known distance.
4. For the current node, check all of its unvisited neighbors.
o Calculate the tentative distance to each neighbor.
o If the calculated distance is smaller than the current stored distance, update it.
5. Mark the current node as visited.
6. Repeat steps 3–5 until all nodes have been visited or the shortest path to the target node is
found.
Chapter 4 Dynamic programming
0/1 Knapsack Algorithm (Dynamic Programming)
1. Make a table with rows for items and columns for weight limits (from 0 to max weight).
2. Each cell in the table shows the best value you can get with a certain number of items
and a certain weight.
3. Start filling the table from the top-left corner.
4. For each item:
o Go through every possible weight from 0 to max weight.
o If the item fits (its weight is less than or equal to the current weight limit):
You have two choices:
Take the item: add its value to the best value from the remaining
weight.
Don’t take it: keep the previous best value.
Pick the better option (the one with more value).
o If the item doesn't fit, just copy the value from above (skip the item).
5. After filling the table, the bottom-right cell has the maximum value you can carry.
Travelling Sales Person problem using Dynamic Programming
Algorithm:
1. Start from the first city (e.g., city 0).
2. Keep track of which cities you’ve already visited using a bitmask (like a checklist).
3. Create a table to store the minimum cost to reach a city after visiting a certain set of
cities.
4. Begin with just the starting city visited and cost 0.
5. For each set of visited cities:
o For each city in that set:
Try visiting every city not yet visited.
Update the minimum cost to reach the new city through this path.
6. After visiting all cities, return to the starting city and add that final cost.
7. The smallest total cost from this process is the answer.
Chapter 5 BackTracking
4-queen or n –Queen problem using Backtracking Algorithm (Simple
Sentences).
1. Try placing a queen in each column of the row.
2. For each placement:
o Check if it is safe (no queen in same column or diagonal).
o If it’s safe, place the queen and move to the next row.
3. If placing a queen leads to a solution, keep it.
4. If it leads to a dead end, remove (backtrack) the last queen and try the next column.
5. Repeat this process until all queens are placed safely or all options are tried.
Graph coloring using Backtracking Algorithm
1. Start with the first node.
2. Try assigning each color (from 1 to m) to the node.
3. Before assigning, check if the color is safe:
o No neighbor of the node has the same color.
4. If it’s safe, assign the color and move to the next node.
5. If you can’t assign any color, backtrack to the previous node and try a different color.
6. Repeat this until:
o All nodes are colored (✅success), or
o No solution is possible (❌ fail).
Hamiltonian Cycle using Backtracking Algorithm
1. Start at the first node (e.g., node 0).
2. Add it to the path.
3. Try adding one node at a time to the path:
o Make sure the node is connected to the previous one.
o Make sure it hasn’t been visited before.
4. If all nodes are in the path and the last node connects to the first, you found a
Hamiltonian cycle!
5. If you reach a point where no valid next node exists, backtrack and try a different
choice.
Chapter 6 Branch and Bound
0/1 knapsack problem using branch and bound
Algorithm:
1. Sort items by value/weight ratio (most valuable per weight first).
2. Use a queue/tree to explore item combinations:
o Each node represents a partial solution (some items chosen or skipped).
3. At each node:
o Track: current level, total value, total weight, and upper bound of max value.
4. If a node's total weight > capacity, discard it.
5. If a node’s upper bound ≤ best value found so far, skip it (pruning).
6. Keep updating the best value as better solutions are found.
7. When all possibilities are checked or pruned, return the best value.
Travelling Salesperson Problem using branch and bound
Algorithm Steps:
1. Start at the first city (e.g., city 0).
2. Create a cost matrix of distances between cities.
3. Reduce the cost matrix:
o For each row, subtract the smallest value from every element.
o For each column, subtract the smallest value from every element.
o The sum of all these subtractions is the initial lower bound (cost estimate).
4. Create a root node representing the starting city:
o Current path contains only the starting city.
o Cost = initial lower bound.
o Reduced cost matrix after step 3.
5. Use a priority queue (min-heap) to store live nodes, prioritized by their lower bound
cost.
6. While the queue is not empty:
o Remove the node with the smallest lower bound.
o If this node’s path visits all cities:
Add cost to return to the start city.
Update the best solution if this cost is smaller.
o Else:
For every city not yet visited:
Create a new node:
Extend the path by visiting that city.
Update the cost matrix:
Set the row of the current city and column of the
new city to infinity (forbidden).
Set the edge from new city back to the start city to
infinity (to avoid premature return).
Reduce the updated cost matrix and calculate new lower
bound.
If this lower bound is less than the best solution cost so far,
add this node to the queue.
7. Continue until all promising nodes are explored or pruned.
8. Return the best path and cost found.