Homework 6

Given a connected acyclic graph $latex G(V,E)$, a source vertex $latex u $ and a destination vertex $latex v$, provide an algorithm that uses union find data structure to count the number of vertices between $latex u$ and $latex v$ in linear time. You are given pseudocode for three different algorithms. Each one takes a …

Lecture 13: Minimum Spanning Tree and Greedy Algorithm

Previous Lecture : In the previous lecture we decided that if the height of a tree $latex =k$ and $latex n$ is the number of nodes then a relation between them can be made as $latex n \geq 2^k$ An example to justify $latex n \geq 2^k$ and show that there also exists graphs which …

Lecture 12: “Disjoint Sets” Data Structure

Disjoint Sets A family F={S1, S2, …, Sn}, where Si ∩ Sj = ∅ ∀ i, j Example 1: A1={1, 2, 3}, A4={4, 5}, A6={6}, A7={7}, A8={8, 9, 10}, A12={11, 12} are all disjoint sets. Basic Functions for Disjoint Sets For a disjoint set data structure, we need two basic functions: Find (x): Which set …

Homework 5

How do we check if a graph is strongly connected using only one DFS traversal? Comment on the correctness of your algorithm. Let $latex G = (V, E)$ be a directed graph in which each vertex $latex u$ in $latex V$ is labeled with a unique integer $latex L(u)$ from the set $latex \{1, 2,..., …

Lecture #11: Topological Sort

In order to carry out this sort we go the following steps: - Apply Depth First Search (DFS) It is a linear sort of nodes or vertices in a Directed Acyclic Graph (DAG). This gives us the discovery time of a node as well as the its finishing time (when it fully gets traversed). Sort …

Lecture 10: Graph Traverse Theory

note: every strongly connected graph is connected but no every connected graph is strongly connected for example: This graph is connected but not strongly connected because the path does not lead back to A. This graph is strongly connected because this graph is cyclic. Depth First Search Algorithm: Change color of every node to white …

Quiz 3 Solution

Q1. Use indicator random variables to compute the expected value of the sum of $latex n$ dice. Show all steps with proper reasoning while computing the result. Let us define six indicator random variables for each die roll. $latex X_{ik} = \begin{cases} 1 & \text{if }  i \text{th roll shows}\; k\\ 0 & \text{otherwise} \end{cases}  $ …

Homework 4

Solve the following recurrences using Master theorem(if  applicable): $latex T(n) = 3T(\frac{n}{4}) + O(n) $ $latex T(n) = 8T(\frac {n}{4}) + O(n^{1.5})  $ $latex T(n) = 2^{n} T(\frac{n}{2}) + O(n) $ $latex T(n) = 3^{n} T(\frac{n}{2}) + O(\sqrt n) $ $latex T(n) = 3T(\frac{3}{5} n) + O(n) $ Asymptotic Notation for each list of functions, …

Lecture #9 : Graphs

Graphs Graphs are the set of edges and vertices(nodes). G = (V, E)V represents number of vertices/ nodes whereas E represents number of edges.Graphs are of two types Simple GraphsMulti-graphs Multi Graphs Multi-Graphs are the graphs having multiple edges. They have loop edges i.e. they have edge with themselves. Simple Graphs Simple graphs are the …