Old Exams Practice (topics may be different)

You are not logged in.
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

These questions are for study purposes. They are from past quizzes, so the content/topics may not necessarily match up. We do not provide solutions, but encourage you to come to office hours or post on piazza if you have any questions.

Topic: Graphs

Which of the following are true? Check all that apply.

	1-1. If the heuristic, h(n), used to estimate distance in A* underestimates the distance to the destination, A* will still always find an optimal answer.
	1-2. If the heuristic, h(n), used to estimate distance in A* overestimates the distance to the destination, A* will still always find an optimal answer.
	1-3. Dijkstra's algorithm is a variant of depth-first search.
	1-4. In a tree, the depth-first search and breadth-first search algorithms both find the same path between a source and destination node.

Consider this graph:

Which of the following are true? Check all that apply.

	2-1. This graph is a digraph.
	2-2. This graph is a tree.
	2-3. This graph is unweighted.
	2-4. On this graph, breadth-first search visits fewer distinct nodes than depth-first search when finding the shortest path from node A to node D.
	2-5. There is exactly one path between any pair of nodes.

Consider this graph:

Which of the following are true? Check all that apply.

	3-1. This graph has exactly 1 cycle.
	3-2. Breadth-first search can be used to find a path between any pair of nodes in this graph.

A town wants to build the minimum total length of bicycle lanes needed so that it will be possible to bike from any address in town to any other address on bicycle lanes. This can best be viewed as (select only one):

	4-1. A shortest path problem.
	4-2. A minimum spanning tree problem.
	4-3. A graph flow problem.
	4-4. A graph partition problem.

Here is the depth-first search code from lecture, which finds a shortest path between a source and target. Modify it so that it finds a longest path between a source and target. You can assume that the graphs the function will run on are acyclic, directed, and unweighted.

def dfs_graph_search(graph, source, target, verbose=False):
    def dfs_internal(path, shortest):
        if verbose:
            print('Current DFS path:', path_to_string(path))

        last_node = path[-1]
        if last_node == target:
            if verbose:
                print('Path found')
            return path

        if shortest and len(path) + 1 >= len(shortest):
            return None

        best_path = None
        for next_node in graph.children_of(last_node):
            if next_node in path:
                continue
            new_path = dfs_internal(path + [next_node], shortest)
            if new_path:
                if not best_path or len(new_path) < len(best_path):
                    best_path = new_path
                if not shortest or len(new_path) < len(shortest):
                    shortest = new_path
        return best_path

    return dfs_internal([source], None)