MS

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.