Algorithms

Question 1

explain the Dijkstra algorithm

Answer 1

while a BFS can find the shortest paths in a non weighted directed graph, a different approach is required for a weighted directed graph.

In the Dijkstra algorithm, in each step we look at the edge (u,v) where u€S and v€Q.

S is the group of vertices that we know the length to, and Q those we dont.

out of all available options, we add to S a vertex v such that dist(u) + W(u,v) is minimized.

We add 2 fields to each vertex -

• v.d - the length of the shortest path from s to v (\infty if it does not exist)
• v.π - the predecessor to v in the shortest path from s to v.

so practicaly, at each step we choose a vertex v with minimal v.d out of the group of vertices for which v.d = \infty.

Question 2

Breadth First Search

uses:

runtime (adjacency list):

runtime (adjacency matrix):

Answer 2

Breadth First Search

uses: find all vertices connected to source, find shortest path from source to all other vertices.

runtime (adjacency list): O(V+E)

runtime (adjacency matrix): O(V²)

Question 3

Depth First Search

uses:

runtime (adjacency list):

runtime (adjacency matrix):

Answer 3

Depth First Search

uses: find all vertices connected to source (undirected graph), find all circles in graph,

topological sort of a directed acyclic graph.

runtime (adjacency list): O(V+E)

runtime (adjacency matrix): O(V²)

Question 4

analize the runtime of the Dijkstra algorithm

see that you can write the algorithm

Answer 4

if using an adjacency list and a heap, the runtime is O((V+E)logV) and if the graph is connected then E>V so that the runtime is O(ElogV)

note: if the graph is acyclic this can be improved to O(E+V) by using topological sort insted of a heap.

Question 5

explain Topological sort

Answer 5

can be used to order the vertices in a Directed acyclic graph s.t if the edge (u,v) exists then u appears before v in the sorted list. can be implemented by running a DFS and ordering the vertices acording to the time it took to finish them. run time is thus O(V+E) for a graph represented as an adjacancy list.

Question 6

define a minimum spanning tree

Answer 6

given a connected, non directed and weighted graph G, a minimum spanning tree T of G is a subgroup of G’s edges, such that they conncect all the vertices in G and the sum of their weights is minimal.

Question 7

explain kruskal’s algorithm and analyze its runtime

Answer 7

we look at the graph as a forest of trees, at erach step we choose an edge with minimal distance connecting two different trees in the forest. we are done when all vertices are in the same tree.

assuming G is implemented via an adjacency list and using a union-find data structure, the runtime is O(ElogV) .

Question 8

describe prim’s algorithm for finding an MST and analize it’s runtime

Answer 8

we start with a vertex in G and at each step we add another vertex to the tree by chossing the outgoing edge with the minimal weight