Graph Theory Pop Quiz

* What is the best implementation, an adjacency List or Adjacency Matrix type implementation for a BFS Algorithm when dealing with a sparse graph ?

Why ?

What is the time complexity of the following algorithms:

* Dijkstra's shortest Path algorithm

* Kruskal's algorithm

* BFS

* DFS

*A* ?

* Dual Source Implementation of Dijkstra's Algorithm ?

* describe what an bipartite graph is...

* What is he number of edges of a connected undirected graph containing 47 vertices ?

* in what situation will Dijkstra's algorithm not function correctly?

* what does DAG stand for ?

* can a connected graph have several components ?

* Which algorithm would a Topological Sort make use of ?

* which algorithm is defined recursively out of either BFS or DFS ?

* What is a Digraph ?

* What is the difference between a connected graph and a

disconnected graph ?

* How many types of connectedness can a Directed Graph have ?

* What is the meaning of weakly connected graph ?

* Describe the Shortest Path Compositionality Property ?

* How many bridges of Konigsberg were there back in the day when the problem was introduced to Edgar W. Dijkstra ?

:D you nerd

* Name 3 common applications of Graph theory

a)

b)

c)

## Monday, November 10, 2014

Post a Comment

Subscribe to:
Post Comments (Atom)