Extra Practice for Exam 2

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.

Below are some additional questions that our TAs have written/collected for you to study. These are entirely optional; we do not record your scores, and these do not factor into your final grade.

These questions were chosen based on their relevance to topics we've covered so far. However, they should not be taken as representive of the types of questions on our exam, whether in format, difficulty, or coverage.

Question 1. Implement the function that meets the specification below.

def reverse_graph(g):
    """
    Create a reversed directed graph from a given directed graph.
    If node u points to node v in the original graph, node v should
    point to node u in the returned graph.

    Parameters:
        g (dict): A mapping from starting nodes (str) to lists of
            neighboring nodes.

    Return a dict representing the reversed graph, in the same form as
    g. It should only include as keys nodes that have at least one
    outgoing edge in the reversed structure. Each list of neighbors
    should be sorted lexicographically.
    """

For example, when g = {"A": ["B", "D"], "B": ["C", "D"]}, reverse_graph(g) should evaluate to:

{
    "B": ["A"],
    "C": ["B"],
    "D": ["A", "B"],
}

Question 2. Implement the function that meets the specification below.

def flatten(seq):
    """
    Extract all the non-list objects within a structure of nested lists
    to arbitrary depth.

    Parameters:
        seq (list): A sequence of elements, some of which may be lists,
            or lists containing other lists, etc.

    Return a new list that contains all the non-list objects in the
    order they would appear if seq were printed.
    """

For example, when L = [ [1, 4, [6], 2], [ [[3]], 2 ], 4, 5 ], flatten(L) should return:

[1, 4, 6, 2, 3, 2, 4, 5]

Hint: Consider a DFS-style traversal of the nested lists.

Question 3. Which of the following statements are true? Select all that apply.

Exhaustive search is only useful for sorted data; if data is unsorted, a different strategy must be used.

In the best-case scenario, exhaustive search can find the target in a single step, regardless of the size of the dataset.

Bisection search is a suitable algorithm for determining if a large integer is prime.

Bisection search will work correctly on any range as long as the target value is within the initial low and high bounds.

Question 4. Which of the following statements are true? Select all that apply.

Linear regression can be framed as an optimization problem where the goal is to find parameters that minimize an objective function representing the error of the fit.

Fitting a higher-order polynomial degree to training data is guaranteed to produce an r^2 that is at least as high as a fitting a lower-degree model on the same data.

A higher-order polynomial is always preferred over a linear model because it ensures more accurate predictions on new, unseen data.

A polynomial of degree n can be used to perfectly fit n + 1 data points.

Splitting data into training and validation sets is only necessary for small datasets; for large datasets, fitting the model to all available data is sufficient to verify predictive power.

K-fold cross-validation is a technique used to mitigate the risk of getting "unlucky" with a single random split of training and validation data.

Question 5. An experiment was conducted to determine how much longer a new "focus mode" feature helps students to study. Students were divided into two groups, one that received the "focus mode treatment," and a control group that did not. Based on measurements students' study times, a 95% confidence interval for the difference in their mean study times, \mu_{treatment} - \mu_{control}, was computed to be [1.2, 10.5].

Which of the following statements are true? Select all that apply.

The data provides evidence at the 5% significance level that the feature increases study time.

It is plausible that the true difference in means is zero.

If the experiment were repeated many times, 95% of the computed confidence intervals would contain the true difference in means.

If the experiment were repeated many times, 95% of the computed differences between the treatment and control groups' means would lie in the range [1.2, 10.5].

The feature is guaranteed to increase study time for every individual student.

The average increase in study time is estimated to be between 1.2 and 10.5 minutes.

Question 6. Consider the following weighted, undirected graph.

What is the order of nodes visited by both BFS and DFS starting from A? You can assume that the neighbors of each node are explored in alphabetical order.

Provide your answer as a dictionary where the keys are "dfs" and "bfs", and each value is a list of strings. Include the starting node A.

Example format:

{
    "dfs": ["A", ...],
    "bfs": ["A", ...],
}

Question 7. You are a hiker preparing for an upcoming hike. You are given grid as list of rows lists, each of length columns, where grid[row][col] represents the altitude of cell (row, col) in a 2D grid. You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1).

You can move up, down, left, or right, and you wish to find a route that requires the minimum effort. A route's effort is the maximum absolute difference in altitudes between any two consecutive cells of the route.

Find the minimum effort and the path required to travel from the top-left cell to the bottom-right cell. For example:

Input: grid = [ [1, 2, 2], [3, 8, 2], [5, 3, 5] ]
Output: 2, [1, 3, 5, 3, 5]
Explanation: The route [1, 3, 5, 3, 5] (highlighted in green) has a maximum absolute difference of 2 across consecutive cells. This is better than the route [1, 2, 2, 2, 5], where the maximum absolute difference is 3.

This problem can be solved by adapting Dijkstra's algorithm. To do so, we've provided in the submission box most of the code for the neighbors() and minimum_effort_path() functions. Complete the lines marked # TODO, so these functions satisfy their specifications below.

You may assume the remove_min(), find_node(), and update_node() functions from lecture are available.

def neighbors(grid, cell):
    """
    Retrieve the neighbors of a cell location within grid. Valid
    neighbors of a given cell are the cells to the top, down, left, and
    right that are within bounds.

    Parameters:
        grid (list): A list of lists of ints, representing a 2D grid,
            and grid[i][j] is the altitude at cell location (i, j).
        cell (tuple): An (i, j) index location within the grid.

    Return a list of (neighbor, weight) tuples, where neighbor is an
    (i, j) tuple, and weight is the effort of traversing from cell to
    neighbor.
    """


def minimum_effort_path(grid):
    """
    Given a grid (as described above), return the minimum effort
    required to travel from the top-left cell to the bottom-right cell.
    """

Hint 1: In this problem, grid cells can be thought of as nodes in a graph, where edges connect neighboring cells. What is the weight of an edge in this graph?

Hint 2: In lecture, the cost of a path was the sum of all the weights of the edges in that path. What is the cost of a path in this problem?