CSE 373: Data Structures and Algorithms Graphs Autumn 2018 Shrirang (Shri) Mare [email protected] Thanks to Kasey Champion, Ben Jones, Adam Blank, Michael Lee, Evan McCarty, Robbie Weber, Whitaker Brand, Zora Fung, Stuart Reges, Justin Hsia, Ruth Anderson, and many others for sample slides and materials ... Technique 3: Master Theorem Revie w Given a recurrence of the following form: ( ) = h =1 + h ( ) Where , , and are constants, then has the following asymptotic bounds If log < then ( ) ( ) If log =
then ( ) ( log 2 ) If log > then ( ) ( log ) CSE 373 AU 18 2 Recurrence analysis techniques Revie w 1. Unfolding method - more of a brute force method - Tedious but works 2. Tree methods - more scratch work but less error prone 3. Master theorem - quick, but applicable only to certain type of recurrences - does not give a closed form (gives big-Theta) CSE 373 AU 18

3 Desired properties in a sorting algorithm Revie w Stable - In the output, equal elements (i.e., elements with equal keys) appear in their original order In-place - Algorithm uses a constant additional space, extra space Adaptive - Performs better when input is almost sorted or nearly sorted - (Likely different big-O for best-case and worst-case) Fast. No algorithm has all of these properties. So choice of algorithm depends on the situation. CSE 373 AU 18 4 Merge sort Split array in the middle Sort the two halves 0 1 2 3 4

8 2 57 91 22 0 1 0 1 2 8 2 57 91 22 0 0 0 0

1 8 2 57 91 22 Merge them together ( ) = { 1 if 1 2 + 2 otherwise 2 ( ) Revie w 0 0 91 22 0

1 22 91 0 1 0 1 2 2 8 22 57 91 0 1 2 3 4 2

8 22 57 91 CSE 373 AU 18 5 Quick Sort 0 1 2 3 4 5 6 20 50 70 10 60 40

30 0 0 1 2 3 4 10 50 70 60 40 30 0 1 0 1 40 30 70

60 quickSort(input) { if (input.length == 1) return else pivot = getPivot(input) smallerHalf = quickSort(getSmaller(pivot, input)) largerHalf = quickSort(getBigger(pivot, input)) return smallerHalf + pivot + largerHalf } Worst case runtime?T(n) = Best case runtime? Average runtime? T(n) = Stable? No In-place? Can be 1 if n<= 1 n + T(n - 1) otherwise 1 if n<= 1 n + 2T(n/2) otherwise 0 10 0 0 30
60 0 1 0 1 30 40 60 70 0 1 2 3 4 30 40 50 60 70

1 2 3 4 5 6 20 30 40 50 60 70 6 CSE 373 AU 18 Choosing a Pivot Average case behavior depends on a good pivot. Pivot ideas: Just take the first element - Simple. But an already sorted (or reversed) list will give you a bad time. Pick an element uniformly at random. - Regardless of input! - Probably too slow in practice :( Median of Three -Take the median of the first, last, and midpoint as the pivot.

-Fast! -Unlikely to get bad behavior (but definitely still possible) -Reasonable default choice. CSE 373 AU 18 7 Worksheet Questions 1-3 CSE 373 AU 18 8 Parting thoughts on sorts - Hybrid sorts - Internal vs. external sorting CSE 373 AU 18 9 Graphs Inter-data Relationships Arrays Trees Graphs Categorically associated Directional Relationships Multiple relationship connections

Sometimes ordered Ordered for easy access Relationships dictate structure Limited connections Connection freedom! Elements store data and connection info Both elements and connections can store data Typically independent Elements only store pure data, no connection info 0 1 2 A B A B C B

C C A CSE 373 AU 18 11 Applications Physical Maps - Airline maps - Vertices are airports, edges are flight paths - Traffic - Vertices are addresses, edges are streets Relationships - Social media graphs - Vertices are accounts, edges are follower relationships - Code bases - Vertices are classes, edges are usage Influence - Biology - Vertices are cancer cell destinations, edges are migration paths Related topics - Web Page Ranking - Vertices are web pages, edges are hyperlinks - Wikipedia - Vertices are articles, edges are links SO MANY MORREEEE www.allthingsgraphed.com CSE 373 AU 18 12

Graph Vocabulary Undirected Graph: Graph Direction A - Undirected graph edges have no direction and are two-way B V = { A, B, C } E = { (A, B), (B, C) } inferred (B, A) and (C,B) Undirected Graph: - Directed graphs edges have direction and are thus one-way V = { A, B, C } E = { (A, B), (B, C), (C, B) } B C A Degree of a Vertex - Degree the number of edges containing that vertex A : 1, B : 1, C : 1 - In-degree the number of directed edges that point to a vertex A : 0, B : 2, C : 1 - Out-degree the number of directed edges that start at a vertex A : 1, B : 1, C : 1 C CSE 373 AU 18

13 Food for thought Is a graph valid if there exists a vertex with a degree of 0? B B B A A A C C A has an in degree of 0 Is this a valid graph? C B has an out degree of 0 Are these valid? A C has both an in degree and an out degree of 0 Yup B A

Yes! Yes A B C Sure D C CSE 373 AU 18 14 Graph Vocabulary Self loop an edge that starts and ends at the same vertex A Parallel edges two edges with the same start and end vertices A B Simple graph a graph with no self-loops and no parallel edges CSE 373 AU 18 15 Graph Vocabulary Walk A sequence of adjacent vertices. Each connected to next by anA edge.B A,B,C,D is a walk. C

D So is A,B,A (Directed) the direction of is the edges walk. B A Walkmust Cfollow D A,B,C,D,B a directed A,B,A is not. Length The number of edges in a walk - (A,B,C,D) has length 3. CSE 373 AU 18 16 Graph Vocabulary Path A walk that doesnt repeat a vertex. A,B,C,D is a path. A,B,A is not. B A C D Cycle Apath with an extra edge from last vertex back to first. B C D Be careful looking at other sources. Some people call our walks paths and our paths simple paths

CSE 373 AU 18 17 Worksheet Question 4 CSE 373 AU 18 18 Implementing a Graph Implement with nodes Implementation gets super messy What if you wanted a vertex without an edge? How can we implement without requiring edges to access nodes? Implement using some of our existing data structures! CSE 373 AU 18 19 Adjacency Matrix A Assign each vertex a number from 0 to V 1 A Create a V x V array of Booleans C T T D B

If (x,y) E then arr[x][y] = true C Runtime (in terms of V and E) - get out - edges for a vertex O(v) - get in edges for a vertex O(v) - decide if an edge exists O(1) - insert an edge O(1) - delete an edge O(1) - delete a vertex - add a vertex B T D T T B A C How much space is used? V2 D CSE 373 AU 18 20 Graph Vocabulary A

B C D Dense Graph a graph with a lot of edges E (V2) Sparse Graph a graph with few edges E (V) F E An Adjacency Matrix seems a waste for a sparse graph G I H CSE 373 AU 18 21 Adjacency List B A Create a Dictionary of size V from type V to Collection of E C If (x,y) E then add y to the set associated with the key x D Runtime (in terms of V and E)

- get out - edges for a vertex O(1) - get in - edges for a vertex O(V + E) - decide if an edge exists O(1) - insert an edge O(1) - delete an edge O(1) - delete a vertex - add a vertex 0 A 1 B 2 3 B C C B D D A How much space is used? V+E CSE 373 AU 18 22

Graph Vocabulary -- Connected Graphs Connected graph a graph where every vertex is connected to every other vertex via some path. It is not required for every vertex to have an edge to every other vertex There exists some way to get from each vertex to every other vertex - There exists some way to get from each vertex within the connected component to every other vertex in the connected component - A vertex with no edges is itself a connected component B C A Connected Component a subgraph in which any two vertices are connected via some path, but is connected to no additional vertices in the supergraph G H D E F CSE 373 AU 18 23