Office Hours Reminder
Office Hours Reminder
This information is all on the course syllabus online.
Daniel Kane: Thursday and Friday 2:30-4:00pm or by appointment
https://ucsd.zoom.us/my/dankane
TAs:
Jiabei Han:Monday, Wednesday, 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.
https://ucsd.zoom.us/my/dankane
https://ucsd.zoom.us/j/92571674513
https://ucsd.zoom.us/j/7577412678
https://ucsd.zoom.us/j/9029365896
https://ucsd.zoom.us/s/5785340529
https://ucsd.zoom.us/my/harrisonku
Today
• Levels of Algorithm Design
• Graph basics and representation
• Depth First Search
Levels of Algorithm Design
Naive Algorithms: Turn definition into algorithm
easy to write, good first pass, often very slow
Toolkit: Algorithm designed using standard tools
the main focus of this course
Optimized: Use data structures or other ideas to
make algorithm especially efficient
Magic: Sometimes, an algorithm requires a
surprising new insight
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.
Question: Which are graphs?
Which of the following could be modeled by a
graph?
A) The internet, V = {websites}, E = {links}
B) The internet, V = {computers},
E = {physical connections}
C) UCSD, V = {students}, E = {classes}
D) Highway System, V = {intersections},
E = {roads}
E) A book, V = {words}
Examples of Graphs in CS
• The Internet (either webpages, or physical
connections)
• Social Networks
• Transitions between states of a program
• Road maps
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}
Exploring Graphs
You’re playing a video game and want to make
sure that you’ve found all the areas in this
level before moving on to the next one.
How do you ensure that you have found
everything?
Basic Algorithm
Keep track of all areas discovered
While there is an unexplored path,
follow path
Systematize
Need to keep track of:
• Which vertices discovered
• Which edges have yet to be explored
Explore Algorithm will:
• Use a field v.visited to let us know which
vertices we have seen.
• Store edges to be explored implicitly in the
program stack.
Explore
explore(v)
v.visited ← true
For each edge (v,w)
If not w.visited
explore(w)
w.prev ← v
Example
A
B
C
D
E
F
G
H
explore(A)
explore(B)
explore(A)
explore(C)
explore(A)
explore(B)
explore(C)
explore(D)
explore(A)
explore(H)
explore(D)
explore(F)
explore(E)
explore(A)
explore(F)
explore(G)
explore(F)
explore(H)
explore(E)
Note: edges used leave
behind “DFS tree”.
Result
Theorem: If all vertices start unvisited,
explore(v) marks as visited exactly the vertices
reachable from v.
Proof:
• Only visits vertices reachable from v.
• If u is visited, eventually visit every adjacent w.
– If there is a chain of vertices
v → u1 → u2 → … → w
eventually visit all of them
Question: explore
Which vertices does explore(v) mark as
visited?
A
B
C
E
D
v
Depth First Search
explore only finds the part of the graph
reachable from a single vertex. If you want to
discover the entire graph, you may need to
run it multiple times.
DepthFirstSearh(G)
Mark all v ∈ G as unvisited
For v ∈ G
If not v.visited, explore(v)
Example
A
B
C
E
D
explore(A)
explore(D)
DFS(G) eventually discovers all vertices in G.
Runtime of DFS
explore(v)
v.visited ← true
For each edge (v,w)
If not w.visited
explore(w)
DFS(G)
Mark all v ∈ G as unvisited
For v ∈ G
If not v.visited, explore(v)
Run once per
vertex
Run once per
neighboring
vertex
O(|V|) total
O(|V|)
O(|E|) total
Final 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)
What algorithm is better may depend on
relative sizes of these parameters.
Sparse Graphs:
|E| small ( ≈ V )
Examples:
• Internet
• Road maps
Dense Graphs:
|E| large ( ≈ V2 )
Examples:
• Flight maps
• Wireless networks
Question: Graph Runtimes
Suppose that you have two graph algorithms for the same
problem
Alg1 has runtime O(|V|3/2)
Alg2 has runtime O(|E|)
Which of the following is likely true?
A) Alg1 is faster on most graphs
B) Alg2 is faster on most graphs
C) Alg1 is faster on sparse graphs, slower on dense graphs
D) Alg2 is faster on sparse graphs, slower on dense graphs
Graph Representations
How do you store a graph in a computer?
• Adjacency matrix: Store list of vertices and an array A[i,j] = 1 if
edge between vi and vj.
– Small space for dense graphs.
– Slow for most operations.
• Edge list: List of all vertices, list of all edges
– Hard to determine edges out of single vertex.
• Adjacency list: For each vertex store list of neighbors.
– Needed for DFS to be efficient
– We will usually assume this representation