Write a program to find the factorial of a given number using recursion and analyze the time complexity.
Theory:
The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. It is commonly used in permutations, combinations, and other mathematical computations.
The factorial of n is defined as:
-
n! = n × (n - 1) × (n - 2) × … × 1
-
For example:
-
5! = 5 × 4 × 3 × 2 × 1 = 120
-
4! = 4 × 3 × 2 × 1 = 24
There is a special case where:
- 0! = 1
CODE:
Code Explanation:
Base Case: If n is less than or equal to 1, return 1 (factorial(0) = 1 and factorial(1) = 1).
Recursive Case: Multiply n by the factorial of n - 1, which calls the function again with a smaller number.
The recursion continues until it reaches the base case and then backtracks, multiplying the numbers to get the final result.
The time complexity of the recursive factorial function is O(n), where n is the input number.
For each call to factorial(n), the function makes a recursive call to factorial(n - 1). This process continues until n reaches 0 or 1, requiring n recursive calls.
Thus, the number of recursive calls grows linearly with the value of n, leading to the time complexity being O(n).
Output:
Conclusion:
Factorial programs are fundamental in learning recursion, and they are widely used in solving problems related to permutations, combinations, and algorithms that require repetitive tasks.
Recursion breaks the problem down into smaller subproblems.
The program uses a stack to keep track of recursive function calls.
The base condition is essential to avoid infinite recursion.
Assignment 2
Write a programs to implement the Prim’s algorithm
Theory:
Prim’s Algorithm is a greedy algorithm that is used to find the Minimum Spanning Tree (MST) of a connected, undirected graph. The Minimum Spanning Tree is a subset of the graph’s edges that connect all vertices with the minimum total edge weight and without any cycles.
-
Greedy Approach: Prim’s Algorithm builds the MST step-by-step, always choosing the least expensive edge that connects a vertex in the growing MST to a vertex outside the MST.
-
Spanning Tree: A subgraph that includes all the vertices of the original graph and is connected and acyclic.
-
Minimum Spanning Tree: A spanning tree where the sum of the weights of the edges is minimized.
CODE:
Explanation:
Start with any arbitrary vertex: The algorithm starts by selecting any vertex as the starting point and adds it to the MST.
Find the Minimum Edge: From the current vertex, find the edge with the smallest weight that connects the vertex in the MST to a vertex not yet included in the MST.
Add Vertex and Edge: Add this edge and the new vertex to the MST.
Repeat Until All Vertices are Included: Continue the process until all vertices are included in the MST.
minKey**(****)**: This function returns the vertex with the minimum key value not yet included in the MST.
primMST**(****)**:
-
Initializes the key values to infinity and sets the starting vertex’s key to 0.
-
Repeatedly picks the minimum key vertex and adds it to the MST.
-
Updates the key and parent values of the adjacent vertices if a smaller edge is found.
Input: The graph is input as an adjacency matrix.
Output: The program prints the edges in the MST and their weights.
Output:
Conclusion:
Prim’s Algorithm starts from any vertex and grows the MST by selecting the smallest edge that connects a new vertex.
It ensures that no cycles are formed and connects all vertices with the minimum possible weight.
It is efficient for dense graphs.
Assignment 3
Write a programs to implement the Krushkals algorithm
Theory:
Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) for a connected, undirected graph. The Minimum Spanning Tree is a subset of the graph’s edges that connect all vertices with the minimum total edge weight and without any cycles.
-
Greedy Approach: Kruskal’s algorithm sorts all the edges in ascending order based on their weights and then adds edges to the MST in this order while ensuring no cycles are formed.
-
Spanning Tree: A subgraph that includes all the vertices of the graph, is connected, and does not contain any cycles.
-
Minimum Spanning Tree (MST): A spanning tree with the minimum possible sum of edge weights.
CODE:
Explanation:
Sort all the edges: The algorithm begins by sorting all the edges of the graph by their weights in non-decreasing order.
Pick the smallest edge: Start picking the smallest edge from the sorted list. If adding the edge forms a cycle, skip it.
Add the edge if it does not form a cycle: Use a technique like Union-Find to keep track of which vertices are in which components (or sets). Only add an edge if it connects two components (i.e., it does not form a cycle).
Repeat until the MST is formed: Continue adding edges until you have V-1 edges (where V is the number of vertices in the graph).
Time Complexity:
-
Sorting the edges takes O(E log E), where E is the number of edges.
-
Union-Find operations are nearly constant time, so the overall time complexity is O(E log E) or O(E log V).
Code Explanation**:**
Edge Class: Represents an edge between two vertices (src, dest) with a certain weight.
Union-Find: The findParent() function uses path compression to efficiently find the root parent of a vertex. The union() function unions two sets of vertices based on rank to balance the tree structure.
kruskalMST():
-
Sorts all edges by weight.
-
Processes edges one by one, adding them to the MST if they don’t form a cycle.
-
Uses the Union-Find data structure to keep track of which vertices are in which sets.
Input: The graph is input as a list of edges (with weights).
Output: The program prints the edges that form the MST and their weights.
Output:
Conclusion:
Kruskal’s Algorithm is particularly useful for sparse graphs, as it works by selecting the smallest edge and ensuring no cycles are formed.
The Union-Find data structure efficiently checks if adding an edge forms a cycle
Sorting the edges takes *O( n log n)**, where E is the number of edges