Prim’s Algorithm:
Prim’s algorithm is a greedy method for constructing a Minimum Spanning Tree (MST) in a
connected weighted graph. It begins from an arbitrary vertex and repeatedly selects the minimum
weight edge that connects a visited vertex to an unvisited vertex. By continuously choosing the
smallest possible edge at each step, the algorithm ensures that the partial tree remains optimal. For
example, in a graph with edges A–B(2), A–C(4), B–C(1), B–D(7), and C–D(3), starting at A results
in selecting A–B(2), then B–C(1), and finally C–D(3), giving an MST of cost 6.
BFS (Breadth-First Search):
Breadth-First Search is a graph traversal technique that explores nodes level by level. Starting from
a source vertex, BFS visits all its immediate neighbors before moving to the next layer. It uses a
queue to maintain the order of exploration. BFS is especially useful for finding shortest paths in
unweighted graphs because the first time a node is reached is via the shortest route. Its time
complexity is O(V + E), making it suitable for large networks.
3D Methods:
3D transformation methods in computer graphics include translation, scaling, and rotation.
Translation involves shifting objects in 3D space by adding offsets to coordinates. Scaling enlarges
or shrinks objects with respect to scaling factors along axes. Rotation manipulates objects around
the x, y, or z-axis using rotation matrices. These transformations are essential parts of the 3D
graphics pipeline, allowing developers to position, size, and orient objects before projection.
Projections (perspective and parallel) are then used to convert 3D objects into 2D screen
representations.
Knapsack & Traveling Salesman:
The knapsack problem focuses on selecting items with maximum value without exceeding weight
capacity. In 0/1 knapsack, each item is either taken or not, solved via dynamic programming. In
fractional knapsack, greedy selection based on highest value per weight produces an optimal
solution. The Traveling Salesman Problem (TSP) involves finding the shortest route that visits all
cities once and returns to the start. As an NP-hard problem, exact solutions are expensive, thus
heuristics like nearest neighbor and MST-based approximations are often used.
Dijkstra’s Algorithm:
Dijkstra’s algorithm computes the shortest path from a source to all other vertices in a graph with
non■negative weights. It initializes distances to infinity except the source, then repeatedly extracts
the vertex with the smallest known distance from a priority queue. For each adjacent vertex, it
relaxes edges by checking if a shorter path exists. Complexity with a min-heap is O(E log V). It is
widely used in routing and navigation systems.
Sorting Algorithms:
Quick sort is a divide-and-conquer algorithm that partitions elements around a pivot. While its
average time is O(n log n), worst-case performance is O(n²). Merge sort divides the array into
halves, sorts them, and merges them, guaranteeing O(n log n) consistently but requiring O(n) extra
space. Insertion sort builds the sorted list incrementally, performing efficiently on small or nearly
sorted inputs. Its best case is O(n), but worst and average cases are O(n²).