Algorithm Design and Analysis

  1. Graph Algorithms
    1. Graph Representations
      1. Adjacency Matrix
        1. Representation
          1. Space Complexity
            1. Time Complexity for Operations
              1. Advantages and Disadvantages
              2. Adjacency List
                1. Representation
                  1. Space Complexity
                    1. Time Complexity for Operations
                      1. Advantages and Disadvantages
                      2. Edge List
                        1. Representation
                          1. Use Cases
                          2. Choosing Appropriate Representation
                          3. Graph Traversal
                            1. Breadth-First Search
                              1. Algorithm Description
                                1. Implementation with Queue
                                  1. Time and Space Complexity
                                    1. Applications
                                      1. Shortest Path in Unweighted Graphs
                                        1. Connected Components
                                          1. Bipartiteness Testing
                                            1. Level-Order Traversal
                                          2. Depth-First Search
                                            1. Algorithm Description
                                              1. Recursive Implementation
                                                1. Iterative Implementation
                                                  1. Time and Space Complexity
                                                    1. Applications
                                                      1. Topological Sort
                                                        1. Strongly Connected Components
                                                          1. Cycle Detection
                                                            1. Path Finding
                                                          2. Comparison of BFS and DFS
                                                          3. Topological Sorting
                                                            1. Problem Statement
                                                              1. DFS-Based Algorithm
                                                                1. Kahn's Algorithm
                                                                2. Strongly Connected Components
                                                                  1. Kosaraju's Algorithm
                                                                    1. Tarjan's Algorithm
                                                                    2. Minimum Spanning Trees
                                                                      1. Problem Statement
                                                                        1. Properties of MST
                                                                          1. Kruskal's Algorithm
                                                                            1. Algorithm Description
                                                                              1. Union-Find Data Structure
                                                                                1. Implementation
                                                                                  1. Analysis
                                                                                  2. Prim's Algorithm
                                                                                    1. Algorithm Description
                                                                                      1. Priority Queue Implementation
                                                                                        1. Analysis
                                                                                        2. Comparison of Algorithms
                                                                                          1. Applications of MST
                                                                                          2. Single-Source Shortest Paths
                                                                                            1. Problem Statement
                                                                                              1. Dijkstra's Algorithm
                                                                                                1. Algorithm Description
                                                                                                  1. Priority Queue Implementation
                                                                                                    1. Correctness Proof
                                                                                                      1. Analysis
                                                                                                        1. Limitations with Negative Weights
                                                                                                        2. Bellman-Ford Algorithm
                                                                                                          1. Algorithm Description
                                                                                                            1. Handling Negative Weights
                                                                                                              1. Detecting Negative Cycles
                                                                                                                1. Analysis
                                                                                                                2. Shortest Paths in DAGs
                                                                                                                  1. Topological Order Approach
                                                                                                                    1. Algorithm Description
                                                                                                                      1. Analysis
                                                                                                                      2. Single-Source Longest Paths
                                                                                                                      3. All-Pairs Shortest Paths
                                                                                                                        1. Problem Statement
                                                                                                                          1. Floyd-Warshall Algorithm
                                                                                                                            1. Dynamic Programming Approach
                                                                                                                              1. Algorithm Description
                                                                                                                                1. Analysis
                                                                                                                                  1. Path Reconstruction
                                                                                                                                  2. Johnson's Algorithm
                                                                                                                                    1. Reweighting Technique
                                                                                                                                      1. Using Dijkstra's Algorithm
                                                                                                                                        1. Analysis
                                                                                                                                        2. Matrix Multiplication Approach
                                                                                                                                        3. Maximum Flow
                                                                                                                                          1. Flow Networks
                                                                                                                                            1. Definitions and Terminology
                                                                                                                                              1. Capacity Constraints
                                                                                                                                                1. Flow Conservation
                                                                                                                                                2. The Ford-Fulkerson Method
                                                                                                                                                  1. Residual Networks
                                                                                                                                                    1. Augmenting Paths
                                                                                                                                                      1. Max-Flow Min-Cut Theorem
                                                                                                                                                      2. The Edmonds-Karp Algorithm
                                                                                                                                                        1. BFS for Finding Paths
                                                                                                                                                          1. Analysis
                                                                                                                                                          2. Push-Relabel Algorithm
                                                                                                                                                            1. Preflow and Height Functions
                                                                                                                                                              1. Push and Relabel Operations
                                                                                                                                                              2. Applications of Maximum Flow
                                                                                                                                                                1. Bipartite Matching
                                                                                                                                                                  1. Edge Connectivity
                                                                                                                                                                    1. Circulation Problems

                                                                                                                                                                Previous

                                                                                                                                                                7. Backtracking and Branch-and-Bound

                                                                                                                                                                Go to top

                                                                                                                                                                Next

                                                                                                                                                                9. String Matching Algorithms