Algorithms on Graphs Coursera Quiz Answers

All Weeks Algorithms on Graphs Coursera Quiz Answers

Algorithms on Graphs Coursera Quiz Answers

Week 6: Bidirectional Dijkstra, A* and Contraction Hierarchies

Q1. The Bidirectional Dijkstra algorithm from the lectures stops processing nodes as soon as it finds some node vv that is processed (that is, extracted from the priority queue, and all the outgoing edges from it are relaxed) both by forward and backward search. Will the algorithm still work correctly if it stops processing nodes as soon as it finds some node vv that is discovered (that is, put into the priority queue after some relaxation of the incoming edge) by both forward and backward searches?

Q2. Suppose we’ve launched a correct Bidirectional Dijkstra algorithm from ss and tt, and it has stopped processing nodes after it had found a node vv processed by both forward and backward searches. Is it necessarily true that for any shortest path PP between ss and tt, any node uu of this path is processed by either forward or backward search or both?

Q3. If given a weighted graph we substitute Dijkstra’s algorithm by Breadth-First Search for forward and backward searches of the Bidirectional Search, and do everything else the same way, will this combination find correct distances?

Q4. In the Bidirectional Dijkstra algorithm from the lectures, we alternated steps of the forward and backward search. We want to optimize our algorithm, and instead alternate taking several steps of the forward search with taking several steps of the backward search, such that we switch from one search to another as soon as the last processed node in the current search is at strictly greater distance from the source of the current search than the last processed node from the alternative source in the alternative search. Will this algorithm work correctly?

No
Yes

Q5. We want to implement an algorithm to solve the famous 15 puzzle for us. This puzzle can be thought of as a problem of finding the shortest path between the current configuration and the ideal configuration of the tiles when all the tiles are put in order as required. There is an edge from a configuration c_1c1 to another configuration c_2c2 if and only if there is a single move in position c_1c1 such that after making this move we get configuration c_2c2. The length of each edge is 11. Then the shortest path between the current configuration and the ideal one corresponds to the shortest sequence of moves solving the puzzle. As all the edges have length 11, we could try solving this puzzle with a Breadth-First Search algorithm. However, it turns out that there are so many different configurations of the 15 puzzle that this Breadth-First Search will require a lot of time to find solutions for some of the configurations.

The running time can be significantly improved by using A* algorithm. To do this, we need to find a good potential function which would be a lower bound on the distance from the current configuration to the ideal one. Which of the following heuristics would be a feasible potential function (select all that apply)?

π(c) = number of tiles in cc which are in the wrong positions (different from their final positions).
π(c) = row number of the free tile + column number of the free tile
π(c) = sum of the taxicab distances (or manhattan distances) from the current tile position to the position of this tile in the ideal configuration, over all the tiles.
π(c) = sum of the numbers written on the tiles

Q6. Consider the A* algorithm with the best possible potential \pi(v) = d(v, t)π(v)=d(v,t). Is it true that A* algorithm given such potential will only discover the edges of some shortest path from the source node to the target node?

Q7. If the forward potential for the bidirectional A* algorithm is the best possible (\pi_f(v) = d(v, t)πf(v)=d(v,t)), and the backward potential is just constant 00 (\pi_r(v) = 0πr(v)=0), will this combination of forward and backward potentials work?

Q8. If we store everything optimally, is it possible that the amount of memory needed to store the graph preprocessed by Contraction Hierarchies is smaller than the graph without preprocessing used by a regular Dijkstra’s algorithm?

No, it is not possible, because we add edges to the graph in the preprocessing phase, so the graph only gets bigger.
Yes, it is possible.

Q9. Can we stop the bidirectional search used in the query phase of Contraction Hierarchies as soon as some node vv is processed both by forward and backward search?

Algorithms on Graphs Coursera Quiz Answers

Q10. During the preprocessing phase, we need to know the following for each node:

1. Lists of incoming and outgoing edges.

2. Rank of the node r(u)r(u) – its position in the order of contraction, to be used in the query phase.

4. Number of shortcuts added s(u)s(u) in case uu is contracted.

5. Edge difference ed(u)ed(u).

6. Number of contracted neighbors cn(u)cn(u).

7. Shortcut cover sc(u)sc(u) – the number of neighbors of uu for which we will add at least one shortcut after contracting uu.

8. Level L(u)L(u) of the node uu – an upper bound on the number of edges in any shortest path from any node ss to uu in the augmented graph.

9. Node importance I(u) = ed(u) + cn(u) + sc(u) + L(u)I(u)=ed(u)+cn(u)+sc(u)+L(u).

We want to reduce the amount of memory needed for preprocessing, so we want to store only some of these variables for each node, and compute the others on the fly while checking which shortcuts should be added if node uu is contracted. Which of the following can be done efficiently?

Store only the lists of incoming and outgoing edges and the rank r(u) of the node (store some special value instead of the rank if the node is not contracted yet), and compute everything else based on it.
Store only the lists of incoming and outgoing edges and the number of shortcuts added in case uu is contracted, and compute everything else based on it.
Store only the lists of incoming and outgoing edges, the rank r(u) of the node (store some special value instead of the rank if the node is not contracted yet) and the level L(u) of the node (store some special value instead of the level if the node is not contracted yet), and compute everything else based on it.