UNIT 3 DESIGN ANALYSIS AND ALGORITHM

11)Describe in detail about depth first traversals with appropriate example and pseudocode.
(13)
https://chatgpt.com/share/67d2b488-416c-8004-849d-9ea8d98d167f

Depth First Traversal (DFS)

Depth First Traversal (or Depth First Search, DFS) is a graph traversal algorithm that explores as far as
possible along each branch before backtracking. It is commonly used in tree and graph data
structures.

DFS can be implemented using:

1. Recursive Approach (via function calls using call stack)

2. Iterative Approach (using an explicit stack)

Working of DFS

1. Start from a source node (or any arbitrary node in the case of an undirected graph).

2. Visit the node and mark it as visited.

3. Traverse to an adjacent unvisited node.

4. Repeat step 2 and 3 until no unvisited adjacent nodes remain.

5. Backtrack to the previous node and explore other unvisited adjacent nodes.

6. Repeat until all nodes are visited.

11.b. 1 Write the steps involved in breath first search algorithm and explain with example.
(13)

Breadth-First Search (BFS) Algorithm: Steps and Example

Definition:
Breadth-First Search (BFS) is a graph traversal algorithm that explores all neighbors of a node before
moving to the next level of nodes. It uses a queue (FIFO structure) to keep track of nodes to be
explored.

Steps of BFS Algorithm:

1. Initialize Data Structures

o Create a queue and enqueue the starting node.

o Mark the starting node as visited.

2. Dequeue and Explore

o Dequeue a node from the front of the queue.

 o Process the node (print/store result).

o Enqueue all its unvisited adjacent nodes and mark them as visited.

3. Repeat

o Continue the process until the queue is empty.

Example of BFS Traversal:

Consider the following graph:

mathematica

CopyEdit

/\

B C

/\ \

D E F

Step-by-Step Execution of BFS (Starting from A):

1. Initialize:

o Queue: [A]

o Visited: {A}

2. Dequeue A, Enqueue its neighbors (B, C):

o Queue: [B, C]

o Visited: {A, B, C}

o Output: A

3. Dequeue B, Enqueue its neighbors (D, E):

o Queue: [C, D, E]

o Visited: {A, B, C, D, E}

o Output: A B

4. Dequeue C, Enqueue its neighbor (F):

o Queue: [D, E, F]

o Visited: {A, B, C, D, E, F}

o Output: A B C

5. Dequeue D (No new neighbors):

 o Queue: [E, F]

o Output: A B C D

6. Dequeue E (No new neighbors):

o Queue: [F]

o Output: A B C D E

7. Dequeue F (No new neighbors):

o Queue: []

o Output: A B C D E F

Final BFS Traversal Output:

A→B→C→D→E→F

Time and Space Complexity:

 Time Complexity: O(V+E) where V is the number of vertices and E is the number of edges.

 Space Complexity: O(V)(for storing visited nodes and queue).

Applications of BFS:

 Shortest path in an unweighted graph (e.g., Dijkstra’s algorithm variation).

 Solving puzzles like mazes, Rubik’s cube.

 Finding connected components in a graph.

 Web crawling, network broadcasting, and AI pathfinding.


12)PRIMS ALGORITHM

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/

https://chatgpt.com/share/67d37fe6-9248-8004-8051-bd97d61eb19c

Prim’s algorithm is a Greedy algorithm like Kruskal’s algorithm. This algorithm always starts with a
single node and moves through several adjacent nodes, in order to explore all of the connected
edges along the way.

 The algorithm starts with an empty spanning tree.

 The idea is to maintain two sets of vertices. The first set contains the vertices already
included in the MST, and the other set contains the vertices not yet included.

 At every step, it considers all the edges that connect the two sets and picks the minimum
weight edge from these edges. After picking the edge, it moves the other endpoint of the
edge to the set containing MST.

Minimum Spanning Tree (MST)

A Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph is a subset of
edges that:

1. Connects all vertices without forming any cycles.

2. Minimizes the total edge weight.

3. Contains exactly V - 1 edges (where V is the number of vertices).

Kruskal’s Minimum Spanning Tree (MST) Algorithm

Last Updated : 05 Mar, 2025

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected, and
undirected graph is a spanning tree (no cycles and connects all vertices) that has minimum weight.
The weight of a spanning tree is the sum of all edges in the tree.

In Kruskal’s algorithm, we sort all edges of the given graph in increasing order. Then it keeps on
adding new edges and nodes in the MST if the newly added edge does not form a cycle. It picks the
minimum weighted edge at first and the maximum weighted edge at last. Thus we can say that it
makes a locally optimal choice in each step in order to find the optimal solution. Hence this is
a Greedy Algorithm.

How to find MST using Kruskal’s algorithm?

Below are the steps for finding MST using Kruskal’s algorithm:

 Sort all the edges in a non-decreasing order of their weight.

 Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If the
cycle is not formed, include this edge. Else, discard it.

 Repeat step 2 until there are (V-1) edges in the spanning tree

3)BIN PROBLEMS

14)Explain in detail about NP hard problems (13)

https://chatgpt.com/sha re/67d37976-30cc-8004-bc8d-8c18350b4cbf
In computer science, problems are divided into classes known as Complexity Classes. In complexity
theory, a Complexity Class is a set of problems with related complexity. With the help of complexity
theory, we try to cover the following.

 Problems that cannot be solved by computers.

 Problems that can be efficiently solved (solved in Polynomial time) by computers.

 Problems for which no efficient solution (only exponential time algorithms) exist.

The common resources required by a solution are are time and space, meaning how much time the
algorithm takes to solve a problem and the corresponding memory usage.

 The time complexity of an algorithm is used to describe the number of steps required to
solve a problem, but it can also be used to describe how long it takes to verify the answer.

 The space complexity of an algorithm describes how much memory is required for the
algorithm to operate.

 An algorithm having time complexity of the form O(nk) for input n and constant k is called
polynomial time solution. These solutions scale well. On the other hand, time complexity of
the form O(kn) is exponential time.

. P (Polynomial Time)

 These are problems that can be solved efficiently.

  There exists an algorithm that can find the solution in polynomial time (like
O(n2)O(n^2)O(n2) or O(n3)O(n^3)O(n3)).

 Example: Sorting numbers (like using merge sort, which runs in O(nlog⁡n)O(n \log
n)O(nlogn)).

2. NP (Nondeterministic Polynomial Time)

 These are problems where, if you guess a solution, you can verify it quickly (in polynomial
time).

 But finding the solution might be very slow (we don't know a fast way to solve them yet).

 Example: Sudoku – If someone gives you a filled Sudoku grid, you can check if it's correct
quickly. But solving it from scratch can be very hard.

3. NP-Complete (NPC)

 These are the hardest problems in NP.

 If you can solve any NP-Complete problem quickly, then you can solve all NP problems
quickly.

 Example: Traveling Salesman Problem (TSP) (finding the shortest route visiting multiple
cities).

 If someone finds a fast way to solve an NP-Complete problem, it would mean P = NP (which
is still unknown).

4. NP-Hard (NPH)

 These are problems that are at least as hard as NP-Complete problems, but they might not
even be in NP.

 This means we can’t even verify a solution quickly.

 Example: Chess – Determining if the first player has a guaranteed winning strategy from a
given board position is NP-Hard.

Simple Analogy:

Think of solving a puzzle:

 P: You can solve it easily (like sorting a list).

 NP: You can check a given solution quickly, but finding it might be hard (like solving Sudoku).

 NP-Complete: The hardest puzzles in NP. If you solve one efficiently, you solve them all!

 NP-Hard: Even harder than NP problems—maybe you can't even check the solution easily.
Understanding NP-Hard Problems in Detail (With Examples)

1. Understanding the Basics

Before we get into NP-Hard problems, let’s break things down step by step.

Computational problems are categorized into different classes based on how hard they are to solve.
The most common classes are:

 P (Polynomial Time): Problems that can be solved efficiently in polynomial time.

 NP (Nondeterministic Polynomial Time): Problems where, if given a solution, we can verify it

quickly (in polynomial time).

 NP-Complete: The hardest problems in NP; if one of them can be solved efficiently, then all
problems in NP can be solved efficiently.

 NP-Hard: Problems that are at least as hard as NP-Complete problems, but they might not be
in NP themselves (they may not even have a solution that can be verified quickly).

2. NP-Hard Problems: A Simple Explanation

A problem is NP-Hard if it is at least as hard as any problem in NP.

🔹 Important Note: An NP-Hard problem does not have to be in NP, meaning:

 The problem may not have a solution that can be verified quickly.

 It can be harder than NP problems.

 Many optimization problems are NP-Hard.

3. Examples of NP-Hard Problems

Now, let’s look at some real-world problems that are classified as NP-Hard.

Example 1: Travelling Salesman Problem (TSP)

 Problem Statement: Imagine a salesman who has to visit multiple cities and return to the
starting city while minimizing the total travel cost (distance, time, etc.).

 Why is it Hard? The number of possible routes increases exponentially as we add more
cities. There is no known efficient algorithm to find the shortest route for a large number of
cities.

 Why is it NP-Hard? Finding the shortest tour is at least as hard as the hardest NP problems,
and no polynomial-time solution is known.

Example 2: Knapsack Problem

  Problem Statement: You have a set of items, each with a weight and value, and a knapsack
that can carry a limited weight. You need to select a subset of items to maximize the total
value while keeping the total weight within the limit.

 Why is it Hard? There are an exponential number of ways to pick the items, and checking all
possibilities takes too much time.

 Why is it NP-Hard? There’s no known fast way to find the best selection of items.

Example 3: Job Scheduling Problem

 Problem Statement: Suppose you have multiple jobs and multiple machines. Each job takes
a certain time to complete on a given machine. The goal is to schedule jobs in a way that
minimizes the total time taken.

 Why is it Hard? Different combinations of job assignments lead to different total times, and
checking all possibilities takes too long.

 Why is it NP-Hard? No known polynomial-time algorithm can solve this optimally for all
cases.

4. NP-Hard vs. NP-Complete

It’s easy to confuse NP-Hard with NP-Complete problems, so let’s compare them with a simple table.

Feature NP-Complete NP-Hard

Yes, solutions can be verified in No, solutions may not be verifiable in

Belongs to NP?
polynomial time. polynomial time.

Travelling Salesman Problem, Halting

Example Problems Sudoku, Boolean Satisfiability (SAT)
Problem

Hard to Solve? Yes Yes (even harder in some cases)

If solved efficiently, does

Yes Not necessarily
P = NP?

👉 Key Difference: All NP-Complete problems are NP-Hard, but not all NP-Hard problems are NP-
Complete.

5. Why Are NP-Hard Problems Important?

NP-Hard problems appear in real-world applications such as:

 Logistics & Transportation: Finding the best delivery routes (TSP).

 Finance: Portfolio optimization (similar to the knapsack problem).

 Manufacturing: Job scheduling in factories.

 Artificial Intelligence: Planning and decision-making.

 Biology & Medicine: Protein folding simulations.

Since these problems are hard to solve optimally, researchers focus on approximation algorithms
and heuristics to get close-to-optimal solutions.

6. How Do We Solve NP-Hard Problems?

Since NP-Hard problems are very difficult to solve exactly in a reasonable time, we use different
approaches:

1. Exact Algorithms (Exponential Time)

o Used for small inputs.

o Example: Brute Force Search (checking all possibilities).

2. Approximation Algorithms

o Provides a solution that is close to the best possible.

o Example: Greedy algorithms for the Knapsack Problem.

3. Heuristic Methods

o Fast but does not guarantee the best solution.

o Example: Genetic Algorithms for optimization problems.

4. Dynamic Programming

o Tries to break problems into smaller overlapping subproblems.

o Example: 0/1 Knapsack Problem solved using dynamic programming.

7. Conclusion

NP-Hard problems are some of the toughest problems in computer science. They have no known
efficient solution, but they appear in many real-world applications. While we cannot always solve
them exactly, we use approximation and heuristic methods to get practical solutions.

Would you like me to explain a specific NP-Hard problem in even more detail?

15)Floyd Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used to find the shortest paths
between all pairs of vertices in a weighted graph. It is particularly useful for dense graphs and can
handle negative weight edges, though it does not work with negative weight cycles.

Algorithm Overview

The Floyd-Warshall algorithm works by iteratively improving an adjacency matrix that stores the
shortest path distances between every pair of vertices. The key idea is to check if including an
intermediate vertex kkk between two vertices iii and jjj results in a shorter path.
Working Principle

 Let dist[i][j] represent the shortest distance from vertex i to vertex j.

 Initially, if there is an edge from i to j, set dist[i][j] to the weight of that edge. Otherwise, set
it to infinity (∞).

 The diagonal elements dist[i][i] are set to 0 since the distance from a node to itself is always
zero.

The algorithm updates the matrix using the recurrence relation:

dist[i][j]=min⁡( dist[i][j],dist[i][k]+dist[k][j])

This means:

 If the direct path from iii to jjj is longer than the path going through an intermediate vertex
kkk, update it.

Algorithm Steps

1. Initialize the distance matrix:

o If there is a direct edge (i,j)(i, j)(i,j), set dist[i][j]=dist[i][j] =dist[i][j]= weight of the
edge.

o Otherwise, set dist[i][j]=∞dist[i][j] = \inftydist[i][j]=∞.

o Set dist[i][i]=0dist[i][i] = 0dist[i][i]=0 for all iii.

2. Iterate over all possible intermediate vertices kkk:

o For each pair of vertices (i,j)(i, j)(i,j), update the distance using: dist[i][j]=min⁡(dist[i]
[j],dist[i][k]+dist[k][j])dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])dist[i]
[j]=min(dist[i][j],dist[i][k]+dist[k][j])

o This step ensures that the shortest path between iii and jjj includes intermediate
vertices up to kkk.

3. Detect negative-weight cycles:

o If dist[i][i]<0d for any iii, then there is a negative-weight cycle in the graph.

Time Complexity

Since there are three nested loops iterating over all vertices, the time complexity is:

O(V3)O(V^3)O(V3)

where V is the number of vertices. This makes it inefficient for very large graphs but suitable for
dense graphs.