Tutorial 4 - Data Structures

Tutorial 4 - Data Structures '08

-

English
14 Pages
Read
Download
Downloading requires you to have access to the YouScribe library
Learn all about the services we offer

Description

Tutorial 4Data Structures ’08Jonathan Cederberg thFriday, October 10 , 2008OutlineExampleDFS vs. BFS1 ExampleAnotherExample2 DFS vs. BFS3 Another ExampleDS’08 Dept. of Information Technology - 2 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutlineExampleDFS vs. BFS1 ExampleAnotherExample2 DFS vs. BFS3 Another ExampleDS’08 Dept. of Information Technology - 3 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample exam questionExampleDFS vs. BFSAnother Prove or disprove:Examplen+1 nd) 2 =O(2 )e) lg(f (n)) =O(lg(g(n))) =) f (n) =O(g(n))f) max(f (n);g(n)) = (f (n) +g(n))DS’08 Dept. of Information Technology - 4 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutlineExampleDFS vs. BFS1 ExampleAnotherExample2 DFS vs. BFS3 Another ExampleDS’08 Dept. of Information Technology - 5 - Jonathan Cederberg | jonathan.cederberg@it.uu.seGraphs - what are they good for?Provide a good representation of...Example Data structures (linked lists, hash tables, trees)DFS vs. BFS The internetAnotherExample DNAA road networkA sewer systemThe circulation of your favorite bodily fluid...Google uses graphs! I use graphs!DS’08 Dept. of Information Technology - 6 - Jonathan Cederberg | jonathan.cederberg@it.uu.seWhether there is a path from every junction to all otherjunctions.And then?With the representation, we can isolate interesting properties ofExamplethe graph, and thus discover interesting properties ...

Subjects

Informations

Published by
Reads 21
Language English
Report a problem

Tutorial 4
Data Structures ’08
Jonathan Cederberg <jonathan.cederberg@it.uu.se>
thFriday, October 10 , 2008Outline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 2 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 3 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample exam question
Example
DFS vs. BFS
Another Prove or disprove:
Example
n+1 nd) 2 =O(2 )
e) lg(f (n)) =O(lg(g(n))) =) f (n) =O(g(n))
f) max(f (n);g(n)) = (f (n) +g(n))
DS’08 Dept. of Information Technology - 4 - Jonathan Cederberg | jonathan.cederberg@it.uu.seOutline
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 5 - Jonathan Cederberg | jonathan.cederberg@it.uu.seGraphs - what are they good for?
Provide a good representation of...
Example Data structures (linked lists, hash tables, trees)
DFS vs. BFS The internet
Another
Example DNA
A road network
A sewer system
The circulation of your favorite bodily fluid
...
Google uses graphs! I use graphs!
DS’08 Dept. of Information Technology - 6 - Jonathan Cederberg | jonathan.cederberg@it.uu.seWhether there is a path from every junction to all other
junctions.
And then?
With the representation, we can isolate interesting properties of
Example
the graph, and thus discover interesting properties of theDFS vs. BFS
underlying system.Another
Example Example: A road system is abstracted as a directed graph in
the natural way. What information would computing the
strongly connected components of this graph give us?
DS’08 Dept. of Information Technology - 7 - Jonathan Cederberg | jonathan.cederberg@it.uu.seAnd then?
With the representation, we can isolate interesting properties of
Example
the graph, and thus discover interesting properties of theDFS vs. BFS
underlying system.Another
Example Example: A road system is abstracted as a directed graph in
the natural way. What information would computing the
strongly connected components of this graph give us?
Whether there is a path from every junction to all other
junctions.
DS’08 Dept. of Information Technology - 7 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample
Fundamentals: DFS and BFS
DFS vs. BFS
Another We look a vertex at a time, examining it and discovering
Example
its neighbours (moving the frontier).
The difference lies in the order we explore the neighbours!
DS’08 Dept. of Information Technology - 8 - Jonathan Cederberg | jonathan.cederberg@it.uu.seExample
DFS
DFS vs. BFS
Another When examining a node, just tag it as discovered and
Example
examine all not yet discovered neighbours first.
So we examine the nodes using a LIFO policy.
DS’08 Dept. of Information Technology - 9 - Jonathan Cederberg | jonathan.cederberg@it.uu.se