Exam 1 Review
Exam 1 Review
CSE 101
Winter 2021
Office Hours
Daniel Kane: Thursday and Friday 2:30-4:00pm or by appointment
https://ucsd.zoom.us/my/dankane
TAs:
Jiabei Han:Monday, Thursday, Friday 4:00-5:00pm pacific over zoom at https://ucsd.zoom.us/j/92571674513.
Vaishakh Ravindrakumar:Monday, Wednesday, Friday 11:00am-12:00pm pacific over zoom at https://ucsd.zoom.us/j/7577412678.
Manish Kumar Singh:Tuesday 4:00-6:00pm and Thursday 5:00-6:00pm pacific over zoom at https://ucsd.zoom.us/j/9029365896.
Chutong Yang:Tuesday 8:00-9:00pm and Thursday 7:00-9:00pm pacific over zoom at https://ucsd.zoom.us/s/5785340529.
Tutor:
Harrison Matt Ku:Tuesday, Thursday 1:00-2:30pm pacific over zoom at https://ucsd.zoom.us/my/harrisonku.
Other Review Options
Old homeworks and exams from problem archive
Suggested textbook problems from website
Remember
Read exam instructions carefully
Complete instructions assignment on gradescope
Have a plan for how you are going to complete the exam
Graph and Connectivity (Ch 3)
Graph basics and representation
Depth First Search
Connected components
Pre- and Post- orderings
DAGs / Topological Sort
General directed graphs & strongly connected components
Graph Definition
Definition: A graph G = (V,E) consists of two things:
A collection V of vertices, or objects to be connected.
A collection E of edges, each of which connects a pair of vertices.
Drawing Graphs
Draw vertices as points
Draw edges as line segments or curves connecting those points
A
B
C
D
E
V = {A,B,C,D,E}
E = {AB,AC,AD, BD,CE,DE}
Explore
explore(v)
v.visited ← true
For each edge (v,w)
If not w.visited
explore(w)
w.prev ← v
Result
Theorem: If all vertices start unvisited, explore(v) marks as visited exactly the vertices reachable from v.
Depth First Search
DepthFirstSearh(G)
Mark all v ∈ G as unvisited
For v ∈ G
If not v.visited, explore(v)
Runtime O(|V|+|E|)
Note on Graph Algorithm Runtimes
Graph algorithm runtimes depend on both |V| and |E|. (Note O(|V|+|E|) is linear time)
Graph Representations
Adjacency list: For each vertex store list of neighbors.
Needed for DFS to be efficient
We will usually assume this representation
Connected Components
Theorem: The vertices of a graph G can be partitioned into connected components so that v is reachable from w if and only if they are in the same connected component.
DFS for computing Connected Components
ConnectedComponents(G)
CCNum ← 0
For v ∈ G
v.visited ← false
For v ∈ G
If not v.visited
CCNum++
explore(v)
explore(v)
v.visited ← true
v.CC ← CCNum
For each edge (v,w)
If not w.visited
explore(w)
Runtime O(|V|+|E|).
Pre- and Post- Orders
Keep track of what DFS does & in what order.
Have a “clock” and note time whenever:
Algorithm visits a new vertex for the first time.
Algorithm finishes processing a vertex.
Record values as v.pre and v.post.
Computing Pre- & Post- Orders
ConnectedComponents(G)
clock ← 1
For v ∈ G
v.visited ← false
For v ∈ G
If not v.visited
explore(v)
explore(v)
v.visited ← true
v.pre ← clock
clock++
For each edge (v,w)
If not w.visited
explore(w)
v.post ← clock
clock++
Runtime O(|V|+|E|).
What do these orders tell us?
Prop: For vertices v, w consider intervals
[v.pre, v.post] and [w.pre, w.post].
These intervals:
Contain each other if v is an ancestor/descendant of w in the DFS tree.
Are disjoint if v and w are cousins in the DFS tree.
Never interleave
(v.pre < w.pre < v.post < w.post)
Directed Graphs
Definition: A directed graph is a graph where each edge has a direction. Goes from v to w.
Draw edges with arrows to denote direction.
DFS on Directed Graphs
Same code
Only follow directed edges from v to w.
Runtime still O(|V|+|E|)
explore(v) discovers all vertices reachable from v following only directed edges.
Topological Orders
Definition: A topological ordering of a directed graph is an ordering of the vertices so that for each edge (v,w), v comes before w in the ordering.
Cycles
Definition: A cycle in a directed graph is a sequence of vertices v1, v2, v3,…,vn so that there are edges
(v1,v2), (v2,v3),…,(vn-1,vn),(vn,v1)
Obstacle
Proposition: If G is a directed graph with a cycle, then G has no topological ordering.
DAGs
Definition: A Directed Acyclic Graph (DAG) is a directed graph which contains no cycles.
Existence of Orderings
Theorem: Let G be a (finite) DAG. Then G has a topological ordering.
Algorithm for Topological Sort
TopologicalSort(G)
Run DFS(G) w/ pre/post numbers
Return the vertices in reverse postorder
Runtime: O(|V|+|E|).
Correctness
Proposition: If G is a DAG with an edge v → w then w.post < v.post.
Strongly Connected Components
Definition: In a directed graph G, two vertices v and w are in the same Strongly Connected Component (SCC) if v is reachable from w and w is reachable from v.
Metagraph
Definition: The metagraph of a directed graph G is a graph whose vertices are the SCCs of G, where there is an edge between C1 and C2 if and only if G has an edge between some vertex of C1 and some vertex of C2.
Example
A
B
C
D
E
F
G
H
BCDE
A
H
G
F
Result
Theorem: The metagraph is any directed graph is a DAG.
Result
Proposition: Let C1 and C2 be SCCs of G with an edge from C1 to C2. If we run DFS on G, the largest postorder number of any vertex in C1 will be larger than the largest postorder number in C2.
C1
C2
Reverse Graph
Definition: Given a directed graph G, the reverse graph of G (denoted GR) is obtained by reversing the directions of all of the edges of G.
A
B
C
A
B
C
Algorithm Idea
Run DFS on GR computing post-orders.
Vertex v with largest postorder is in a source SCC of GR, thus a sink SCC of G.
Running explore(v) finds exactly the SCC of v.
Repeat for largest undiscovered postorder.
Algorithm for computing SCCs
SCCs(G)
Run DFS(GR) record postorders
Mark all vertices unvisited
For v ∈ V in reverse postorder
If not v.visited
explore(v) mark component
Just 2 DFSs! Runtime O(|V|+|E|).
Shortest Paths
Problem: Given a graph G with vertices s and t, find the s-t path using the fewest number of edges.
Observation
If there is a length ≤d s-v path, then there is some w adjacent to v with a length ≤(d-1) s-w path.
For each distance d, compute all vertices at distance d from s.
These are the vertices adjacent to vertices at distance d-1.
Simplify some by using a queue to keep track of unprocessed vertices
For v ∈ V, dist(v) ← ∞
dist(s) ← 0
For (u,v) ∈ E
If dist(v) = ∞
Initialize Queue Q
Q.enqueue(s)
u ← front(Q)
Q.enqueue(v)
v.prev ← u
BreadthFirstSearch(G,s)
While Q not empty
dist(v) ← dist(u)+1
Total runtime:
O(|V|+|E|)