1 of 25

Sp18 CS 61B Discussion 11

2 of 25

Welcome!

Wayne Li

wli2@berkeley.edu

https://wayne-li2.github.io/

​

​

3 of 25

Announcements

  • Midterm II scores are out (@3262)
    • Regrade requests will open on April 4th, at noon
    • Regrade requests will close on April 9th, at noon
    • Special regrade instructions for FLIGHT
  • Algorithm design problems (@3259)
  • HW 4 (Puzzle Solver) due tomorrow 4/4
  • Hope you all had a restful and fun spring break!

4 of 25

Quiz Instructions

  • If you haven’t yet, please also neatly put your email address outside the name box if you want to be emailed!
  • Bubble number 41.

5 of 25

Aside

6 of 25

Resilience

  • If you didn’t get the score you wanted
    • I’m here for you!
  • Want to meet with me specifically?
    • https://goo.gl/forms/3HyKxt0ZAWHKRmij2
    • Can chat about anything, serious or light!
  • Want to meet with any TA (not me)? @3258

​

7 of 25

Feedback

  • Not many responses :(
  • New survey! (much shorter, 1 Q!)
  • https://goo.gl/forms/qxZ8qzS47HB62wiE3
  • Will give the option of non-anonymity.
  • Give me criticism!! Nothing too small to bring up.

8 of 25

Feedback so Far

  • Room’s too small!
    • Sorry… :( Trying to find a 61C TA that will switch rooms with me

9 of 25

Feedback so Far

  • Speed: Just right -> Too Fast
    • Want to gather more data from this week!
    • Remember this is exam prep: come with the concepts learned from regular discussion!
    • If you’re struggling, email me on the side! More than happy to explain concepts.

10 of 25

Why is this Important?

11 of 25

Onto Discussion

12 of 25

Q1 (Warmup)

13 of 25

Runtimes

idea

addEdge(s, t)

for(w : adj(v))

printgraph()

hasEdge(s, t)

space used

adjacency matrix

Θ(1)

Θ(V)

Θ(V2)

Θ(1)

Θ(V2)

list of edges

Θ(1)

Θ(E)

Θ(E)

Θ(E)

Θ(E)

adjacency list

Θ(1)

Θ(1) to Θ(V)

Θ(V+E)

Θ(degree(v))

Θ(E+V)

14 of 25

Key Idea: How to Represent Graphs

  • Important real-life considerations.

15 of 25

Key Idea: How to Represent Graphs

  • Adjacency Matrix
    • Fast hasEdge(u, v). Probably the most common operation on a graph.
    • Ex: Facebook - are A and B friends?

16 of 25

Key Idea: How to Represent Graphs

  • Adjacency Matrix
    • If graph is sparse, a lot of wasted space.
    • Ex: Facebook - 2.2 billion users, most users have between 100-1000 friends.

17 of 25

Question

  • Should Facebook use an adjacency matrix?

18 of 25

Question

  • Should Facebook use an adjacency matrix?
    • They pay someone a lot more than me to answer this question.

19 of 25

Key Idea: How to Represent Graphs

  • Adjacency List
    • Slower hasEdge(u, v).
    • But faster on everything else! Namely:
      • O(V + E) instead of O(V2)

20 of 25

Key Idea: How to Represent Graphs

  • Adjacency List
    • Important: Know what size of E is relative to size of V.
    • Therefore, on dense graphs, E ~ O(V2), and adjacency lists lose their speed.

21 of 25

Key Idea: How to Represent Graphs

  • Edge Set
    • Seems fast! Everything O(1) or O(E).
    • But hasEdge(u, v) is O(E).

22 of 25

Q2 (skip)

23 of 25

Q3

24 of 25

Berkeley CS Courses

25 of 25

Q4