Graph Theory and Algorithms
Sample Problems: Counting Sort
- Counter Array After Initializing: The counter array holds the frequency of each element in the input data. It is initialized based on the range of possible input values.
- Finding the Number of 7s in the Counter Array: To find the number of occurrences of 7, access the value at the index corresponding to 7 in the counter array.
Key Result: Expectation
- Definition: For a discrete random variable X, its expectation E[X] is given by:
E[X] = ext{Σ}_{j=0}^{ ext{JP}} j imes ext{Pr}[X = j] - Example with Coin Flips: The probability of the first heads in coin flips, where heads occur with probability p and tails with probability 1 - p. The expected number of flips until the first heads is:
E[X] = ext{Σ}_{j=0}^{ ext{∞}} j imes (1 - p)^{j} imes p
Hitting Time Result
- Definition: If the probability of achieving a hit is 1/k, then the average hitting time is exactly k.
Randomized ONEMAX Problem
- Bit-flips: The probability of flipping an A to a G can be expressed in terms of the harmonic series, indicating a relationship between the number of bits and success probability.
Gambling Addiction Statistics
- Impact on Mental Health: 15% to 20% of addicted gamblers attempt suicide, with a higher suicide rate than for drug addiction.
Graphs Basics
Undirected Graphs
- Definition: Undirected graph G = (V, E) where:
- V represents nodes (e.g., V = {1, 2, 3, 4, 5, 6, 7, 8})
- E includes edges between pairs of nodes (e.g., edges include pairs like (1,2), (2,3))
- Parameters: n = |V|, m = |E|; for this example, n = 8, m = 11.
Directed Graphs
- Definition: Directed graph G = (V, E) where edges point from one node to another (e.g., web pages linked). Important for search engine algorithms that rank pages based on hyperlink structure.
Examples of Graphs
- Social Networks: Nodes represent people or web pages, while edges represent connections or relationships (directed or undirected).
- Transportation Graphs: Nodes represent street addresses, and edges represent the roads connecting them.
Graph Applications
- Used to model:
- Transportation networks (intersections and highways)
- Communication networks (computers and connections)
- Social relationships (people and their connections)
Graph Representation
Adjacency Matrix
- An n imes n matrix indicating edges (if edge exists, represent with 1, else 0).
- Space complexity is O(n^2); checking edges takes O(1) time.
Adjacency List
- An array where each entry corresponds to a node and stores a list of edges.
- More space-efficient: O(m + n) for storage.
- Checking edges takes O( ext{deg}(u)) time.
Paths and Connectivity
- Paths: A sequence in an undirected graph where each pair of consecutive nodes is connected.
- Connected Graph: A graph is connected if there is a path between every pair of nodes.
Cycles in Graphs
- A cycle is a connected path where the starting node is the same as the ending node, and all other nodes are distinct.
Trees
- A connected undirected graph without cycles. A tree with n nodes contains exactly n-1 edges.
- Rooted Trees: A specific structure where one node is designated as root, and every edge directs away from it.
Traversing Trees and Graphs
Tree Traversal Methods
- Pre-order: (Visit node, then left subtree, then right)
- In-order: (Left subtree, visit node, then right)
- Post-order: (Left subtree, right subtree, then visit node)
- Level-order: (Visit nodes level by level)
Graph Traversal Techniques
- Depth-First Search (DFS): Explores as far as possible along each branch before backtracking.
- Breadth-First Search (BFS): Explores neighbors level by level, useful for finding shortest paths in unweighted graphs.
Connectivity in Directed Graphs
- Strong Connectivity: A directed graph is strongly connected if there is a path between all pairs of nodes.
Topological Sorting for DAGs
- Definition: DAG is a directed graph with no cycles. Topological ordering ensures that for every directed edge u -> v, node u comes before v in the ordering.
- Topological sort can be performed in linear time O(m+n).
Conclusion
- Bipartite Graphs: An undirected graph is bipartite if nodes can be colored with two colors with no adjacent nodes sharing the same color.
- Testing Bipartiteness: Utilize BFS or DFS to verify by checking if any two adjacent nodes are of the same color.