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

1. Pre-order: (Visit node, then left subtree, then right)
2. In-order: (Left subtree, visit node, then right)
3. Post-order: (Left subtree, right subtree, then visit node)
4. 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.