Week 1

Question 1

What is the definition of a tree?

Answer 1

Question 2

What is a theorem about the number of edges and the number of vertices of a connected graph?

Answer 2

Question 3

When is a connected graph a tree?

Answer 3

Question 4

When is a simple graph a tree?

Answer 4

Question 5

When is a connected simple graph a tree?

Answer 5

Question 6

What is a spanning tree?

Answer 6

Question 7

What is the definition of a Minimum Spanning Tree?

Answer 7

Question 8

What is Kruskals algorithm? What is it used for?

Answer 8

It is used to find the minimum spanning tree.

Question 9

When does a weight departing from a subtree belong to a minimum spanning tree?

Answer 9

Question 10

When is a MST unique?

Answer 10

Question 11

What is the Prim(-Jarnik) algorithm?

Answer 11

Question 12

What are the commonalities and differences between Kruskals and Prims algorithm?

Answer 12

Question 13

What is the basic idea behind Dijkstra’s algorithm?

Answer 13

Question 14

What are the two algorithms used to find a shortest path?

Answer 14

Question 15

What is the notation used to find a shortest path (when using the Dijkstra’s algorithm)?

Answer 15

Question 16

What is Dijkstra’s algorithm?

Answer 16

Question 17

What is Dijkstra’s correctness theorem?

Answer 17

Question 18

What is the basic idea of the Bellman-Ford Algorithm?

Answer 18

Question 19

What is the Bellman-Ford algorithm?

Answer 19

Question 20

What is the Bellman-Ford correctness theorem?

Answer 20

Question 21

What is the complexity of the Dijkstra and Bellmand-Ford algorithm?

Answer 21