a. Pick an x∈A, set S:=S∪{x}

        b. Let UnseenChild(x):={y|(x,y)∈E ∧ y∉S}

        c. Set A:=(A ∪ UnseenChild(x))−{x}

Group members: Sonja Boytcheva, Ben Foley, Edgar Velazquez Given a graph G=(V,E) and two vertices s,t∈V, give the algorithm from class to determine a path from s to t in G if it exists. Solution: 1. Initialize A={s}, S=∅. 2. Repeat the following until either t∈A or A=∅: a. Pick an x∈A, set S:=S∪{x} b. Let UnseenChild(x):={y|(x,y)∈E ∧ y∉S} c. Set A:=(A ∪ UnseenChild(x))−{x} 3. If A=∅ then output "there is no path s to t" 4. Otherwise, we can find a path in reverse order by looking in S for some x such that (x,t) ∈ E, then looking in S for some y such that (y,x) ∈ E, and so on until we get back to s. This will be a simple path.

-- Practice Midterm Problem 4 Solution

* Group members: Phuc Phan, Rayyan Khan, Prajesh Shrestha * check reflexive: (a,b) ~ (a,b) because a.b = c.d * check symmetric: if (a,b) ~ (c,d) which means a.b = c.d -> c.d = a.b -> (c,d)~(a,b) * check transitive: if(a,b) ~(c,d) and (c,d)~(e,f) which means a.b = c.d and c.d = e.f -> a.b = e.f -> (a,b)~(e,f) * Conclude: ~ is an equivalence relation