DAGs, SCC, Square root decomposition,.pptx

Analysis and Design of Algorithms, Directed Acyclic Graph, SCC, Square root decomposition

1. DAGs, SCC, Square root decomposition, Asymptotiv analysis, Greedy algorithms. By Deeksha M Sr. Asst. Professor Dept of CSE AIET

2. Graph Terminology Graphs Multigraphs Adjacent nodes Isolated node Path Cycle Complete graph Labeled graph Weights Multiple edges Loops

3. Directed graph Arc Outdegree Indegree Source Sink Path matrix Directed Acyclic graph

4. Representation of graphs Adjacency matrix Adjacency list

5. Implement a program to create a graph of n vertices using adjacency matrix. Also write the code to read and print the information. Implement a program to create a graph of n vertices using adjacency list. Also write the code to read and print the information and delete the graph.

6. Detect a cycle in the directed graph. Detect a cycle in the undirected graph

7. Strongly Connected Components A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component ( SCC ) of a directed graph is a maximal strongly connected subgraph.

8. Square root decomposition Square root decomposition is the process of separating a structure of size O(N) into O(SQRT(N)) blocks. Square Root Decomposition Technique is one of the most common query optimization techniques used by competitive programmers. This technique helps us to reduce Time Complexity by a factor of sqrt(N) Queries of calculating sum in the range [ l,r ] Brute force->O(N) SDD->O(SQRT(N))

9. Asymptotic Analysis Efficiency Time complexity Space Complexity

10. Greedy technique Prim’s Algorithm Kruskal’s Algorithm Dijkstra’s Algorithm Huffman’s coding