Algorithms Design and Analysis

Study Notes

Adjacency Matrix vs Sparse Graphs: Two different approaches for designing and analyzing algorithms, each suitable for specific graph types.
Adjacency Matrix:
- Time complexity: O(V²)
- Space complexity: O(V²)
- Suitable for dense graphs
- Builds MST by continuously adding vertices to the growing MST
- Cycle handling: Does not allow cycles since it adds vertices directly to the MST
Sparse Graphs:
- Time complexity: O(Log V)
- Space complexity: O(E + V)
- Suitable for sparse graphs
- Builds MST by continuously adding edges to the MST
- Cycle handling: Checks for cycles before adding an edge to the MST

Overview: Finds the shortest path from a single source vertex to all other vertices in a weighted, directed or undirected graph with non-negative edge weights.
Key Properties:
- Single source shortest path problem
- Finds the shortest path from a given vertex to all remaining vertices
- Each edge has a non-negative cost
- Length of the path is the sum of edge costs
Working Process:
- Iteratively expands the set of visited vertices and updates their tentative distances
- Finds the shortest path to all vertices
Example:
- A motorist finding the shortest path from their place to another place among multiple routes
- Graph Example: A square with 4 vertices, multiple edges with weights, and the algorithm finds the shortest path between vertices.