# MBD ALGO TABLE ENTRY

> ？？？

## Elementary
### Matrix
- Strassen’s Algorithm

### Sort
- Counting Sort

### Numeric
- Modular arithmetic (Mod)

## Graph
### Königsberg Bridge Problem
- Euler Path (Eulerian Path)
- Euler Cycle (Eulerian Cycle)
- Euler Graph (Eulerian Graph)
- Euler's Theorem

### Hamiltonian Cycle Problem
- Hamiltonian cycle
- Hamiltonian path

### Graph Traversal & Sort
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Topological sort

### Graph Properties
- Cut-Vertex (Articulation point)
- DAG (Directed acyclic graph)
- DFS forest edges
- Tree edge
- Forward edge
- Back edge
- Cross edge
- Strongly-Connected-Component (SCC)
- Bridge

### Minimum Spanning Tree
- Minimum spanning tree (MST)
#### Algorithm
- Kruskal's Algorithm
- Prim's Algorithm

### Shortest Path Tree
- Relaxation
- Bellman-Ford Algorithm ==Pseudo Code==
- Single-source shortest paths in DAGs
- DP solving in DAG
- Dijkstra's Algorithm
- Shortest-path tree
- Longest Common String (LCS)
- Longest Increasing String (LIS)
- Difference constraints
- Constraint Graph
- All-Pairs Shortest-Path Problem
- Floyd-Warshall Algorithm
- Transitive closure
- Johnson's Algorithm

### Flow & Cut
- Flow network
- Source (s)
- Sink (t)
- Flow
- Cut
- The maximum-flow problem
- Max-Flow Min-Cut Theorem
- Ford-Fulkerson Method
- Edmonds-Karp Algorithm
- Edge connectivity
- Perfect matching
- Hall’s Theorem
- Bipartitle graph

## Set
- Union-Find Operations (Disjoint-Set Unions)
- Find
- Union

## Data Structure
### Graph Record
- Adjacency Matrix
- Adjacency List

### Priority Queue
- Fibonacci Heap
- Van Emde Boas Queue

## Computational Complexity
- Travelling salesman problem (TSP)
- Reduction
- Euclidean MST problem
- Convex hull problem
- Tractable & Intractable
- P, NP, NP-Hard, NP-Complete, co-NP, co-P
- Abstract problem
- Decision problem

### Operations on Languages
- Union
- Intersection
- Complement
- Concatenation
- Kleene star (Closure)
- P closed under above

### Reducibility

- Formula Satisfiability
- Cook’s Theorem

- Conjunctive normal form (CNF)
- CNF satisfiability (CNF-SAT)
- Circuit satisfiability (CIRCIT-SAT)
### NP-Complete Problems
- Clique Problem (CLIQUE)
- Vertex-Cover Problem

- Nondeterministic Turing machine (NTM)

- Hamiltonian path
- Hamiltonian cycle

- 2-CNF-SAT
- Clique
- Subgraph-isomorphism problem

- BK
---

-