Q6. Explain Dijkstra algorithm with suitable example. ?

Dijkstra's algorithm is a popular algorithm for finding the shortest path between nodes in a graph, which
may represent, for example, road networks. The algorithm maintains a set of vertices whose shortest
distance from the source is known, and it repeatedly selects the vertex with the smallest known
distance, updates its neighbors' distances, and adds it to the set of visited vertices.

Steps of Dijkstra's Algorithm:

1. Initialize distances from the source to all vertices as infinity and the distance to the source itself
as 0.
2. Create an empty set to store visited vertices.

3. While the destination has not been visited:

a. Pick the unvisited vertex with the minimum distance as the current vertex.

b. For the current vertex, update the distance of its neighbors by considering the distance through the
current vertex. If the new distance is smaller, update it.

c. Mark the current vertex as visited.

Example:

Consider the following graph:

Let's find the shortest path from vertex A to other vertices using Dijkstra's algorithm.
 1. Initialize distances: A (0), B (inf), C (inf), D (inf).
2. Choose the unvisited vertex with the smallest distance (A), and update its neighbors' distances.

Update B: dist[A] + weight(A-B) = 0 + 10 = 10

Update C: dist[A] + weight(A-C) = 0 + 5 = 5

3. Mark A as visited.
4. Choose the next unvisited vertex with the smallest distance (C), and update its neighbors'
distances.

Update D: dist[C] + weight(C-D) = 5 + 5 = 10

Update B: No change (10 is not smaller than the current value).

5. Mark C as visited.
6. Choose the next unvisited vertex with the smallest distance (B), and update its neighbors'
distances.

Update D: No change (10 is not smaller than the current value).

7. Mark B as visited.
8. Choose the last unvisited vertex (D), and update its neighbors' distances.

No updates.

9. Mark D as visited.
The final distances are: A (0), B (10), C (5), D (10).

The shortest path from A to D is A -> C -> D, with a total distance of 15

Q7. What is a minimum spanning tree? .

A minimum spanning tree (MST) is a tree that spans all the vertices of a connected, undirected graph
while minimizing the sum of the weights (or costs) associated with the edges. In simpler terms, it is a
subset of the edges of the graph that connects all the vertices together without forming any cycles and
has the minimum possible total edge weight.

Here are some key points about minimum spanning trees:

2. **Acyclic Structure:** The tree must be acyclic, meaning there are no cycles (closed loops) in the
tree.

3. **Minimization of Edge Weights:** The sum of the edge weights in the minimum spanning tree is
minimized. This is the primary objective of finding a minimum spanning tree.

4. **Applications:** Minimum spanning trees have various applications, such as in network design,
circuit design, transportation planning, and any scenario where the goal is to establish connections
between points with minimal cost.

5. **Algorithms:** There are several algorithms to find a minimum spanning tree, with two notable
ones being Kruskal's algorithm and Prim's algorithm. These algorithms iteratively add edges to the
growing spanning tree while ensuring that no cycles are formed.

The choice of which algorithm to use may depend on factors like the characteristics of the graph, the
presence of weighted or unweighted edges, and the computational resources available.

In summary, a minimum spanning tree is a fundamental concept in graph theory and has practical
implications in various fields where the goal is to establish efficient connections while minimizing costs.

Q8. Explain Hash table with example?

A hash table is a data structure that allows you to store and retrieve data in an efficient manner. It uses
a hash function to map keys to indices in an array, where the corresponding values are stored. The
primary advantage of a hash table is fast data retrieval, with an average time complexity of O(1) for
search, insert, and delete operations, assuming a good hash function.

Here's a simple explanation of how a hash table works with an example:

### Basic Components of a Hash Table:

2. **Hash Function:** A hash function takes a key as input and produces an index (hash code) where the
corresponding value should be stored in the array.

3. **Collision Handling:** Collisions occur when two keys hash to the same index. Different collision
resolution techniques, such as chaining or open addressing, are used to handle collisions.

### Example:

Let's consider a scenario where we want to store a set of student records with their names and
corresponding grades using a hash table.

1. **Array Initialization:**

- Create an array with a fixed size (e.g., 10).

2. **Hash Function:**

- Define a hash function that takes the student's name and produces an index.

3. **Insertion:**
 - Insert a student record into the hash table.

4. **Retrieval:**

- Retrieve a student's grade based on their name.

In this example, the hash function maps each student's name to an index in the array. Collisions are
handled using chaining, where each array index contains a list of records. This allows multiple records
with different names to coexist at the same index.

It's important to note that a good hash function is crucial for minimizing collisions and ensuring a
balanced distribution of keys across the array indices. Additionally, the array size should be chosen
carefully to balance memory usage and prevent excessive collisions.