Tutorial 4 - Data Structures '08

Jonathan Cederberg <[e-mail]>

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 | [e-mail] vs. BFS1 ExampleAnotherExample2 DFS vs. BFS3 Another ExampleDS’08 Dept. of Information Technology - 3 - Jonathan Cederberg | [e-mail] 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 | [e-mail] vs. BFS1 ExampleAnotherExample2 DFS vs. BFS3 Another ExampleDS’08 Dept. of Information Technology - 5 - Jonathan Cederberg | [e-mail] - 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 | [e-mail] 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 ...

Informations

• Publié par: Zawyug
• Nombre de lectures: 21
• Langue: English

Extrait

Tutorial 4
Data Structures ’08
Jonathan Cederberg <[e-mail]>
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 | [e-mail]
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 3 - Jonathan Cederberg | [e-mail] 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 | [e-mail]
Example
DFS vs. BFS
1 Example
Another
Example
2 DFS vs. BFS
3 Another Example
DS’08 Dept. of Information Technology - 5 - Jonathan Cederberg | [e-mail] - 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 | [e-mail] 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 | [e-mail] 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 | [e-mail]
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 | [e-mail]
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 | [e-mail]