Design and Analysis of Algorithms

CS41: Midterm Exam Study Guide

The midterm exam covers all material introduced before fall break, up to and including what we have covered so far from the section on Divide and Conquer. You are responsible for all material discussed in lecture or lab, and all material on homework assignments. You are also expected to be familiar with data structures introduced in CS35.

You should be able to define and explain the following terms:

  • Stable Matching
    • matching instability
    • Gale-Shapley Algorithm
  • Algorithm Analysis
    • Definitions of big-O, big-Theta, big-Omega
    • Direct proof
    • Induction
    • Proof by contradiction
  • Data Structures
    • List
    • Array
    • Adjacency List and Adjacency Matrix
    • any data structure from CS35 that you want to use
  • Graph Algorithms
    • Breadth-First Search
    • Depth-First Search
    • Topological Sort
    • Minimum Spanning Tree
    • Kruskal's Algorithm
    • Prim's Algorithm
  • Greedy Algorithms
    • Greedy Algorithm for interval scheduling, and minimizing maximum lateness
    • Methods for proving greedy algorithms are optimal (stays ahead, exchange argument)
  • Divide and Conquer
    • Divide and Conquer algorithm structure
    • Mergesort
    • Recurrence Relations
    • Recursion Tree and Substitution Methods

Practice problems:

  1. For each pair of functions, determine the tightest possible asymptotic comparison. e.g. if $f = O(g)$ and $f = \Omega(g)$, then write $f = \Theta(g)$. If no asymptotic comparison can be made, say so.
    • $f_1(n) = 2n^2 \log(n),\quad f_2(n) = n^3 + n^2/\log(n)$
    • $g_1(n) = n^{10},\quad g_2(n) = 2^{n/10}$
    • $h_1(n) = \sqrt{\log(n)}, \quad h_2(n) = \log(\log(n))$
  2. Prove the following statements.
    • If $f(n) \in \Omega(g(n))$ and $g(n) \in \Omega(h(n))$, then $f(n)\in \Omega(h(n))$.
    • If $f(n) \in \Omega(g(n))$, then $g(n) \in O(f(n))$.
  3. Order the following functions in increasing order of their asymptotic running time.
    • $f_1(n) = (\log\log(n))^2$
    • $f_2(n) = (3/2)^n$
    • $f_3(n) = n^2 + \log^{10}(n)$
    • $f_4(n) = n^{1.3}\log^5(n)$
    • $f_5(n) = 2^{\log^2(n)}$
    • $f_6(n) = (\sqrt{2})^{\log(n)}$
  4. For each of the following two statements, decide whether it is true or false. If it is true, give a short justification. If it is false, give a counterexample.
    1. Suppose we are given an instance of the Minimum Spanning Tree (MST) problem on a graph $G=(V,E)$, with edge costs that are all positive and distinct. Let $T$ be a minimum spanning tree on $G$. Now, suppose we replace each cost $c_e$ by its square $(c_e)^2$, thereby creating a new instance of the problem with the same graph but different costs.

      True or false: $T$ must still be a minimum spanning tree for the new instance.

    2. Suppose we are given an instance of the Shortest $s \leadsto t$ Path Problem on a directed graph $G = (V,E)$, with edge costs that are all positive and distinct. Let $P$ be a a minimum-cost $s \leadsto t$ path for this instance. Now, suppose we replace each edge cost $c_e$ by its square $c_e^2$, thereby creating a new instance of the problem with the same graph but different costs.

      True or false: $P$ must still be a minimum $s \leadsto t$ path for this new instance.

  5. Solve the following recurrence relations, using (i) recursion trees, and (ii) substitution method
    • $M(n) = 5M(n/2) + 3n, \text{for all } n > 2;\qquad M(2) = 5$
    • $A(n) = 3A(n/3) + 3n, \text{for all } n > 1;\qquad A(1) = 4$
    • $T(n) = 4T(n/2) + 4n^4, \text{for all } n >4;\qquad T(4) = 4$
  6. Suppose you are given two lists $A,B$ each of $n$ positive integers. You are allowed to reorder the elements in each list however you wish, after which you get paid $$\sum_{i=1} A[i]\cdot B[i]$$ Design and analyze a greedy algorithm to maximize your payout. Prove your algorithm returns the optimal payout. What is the running time of your algorithm?
  7. Finding a bichromatic edge. Suppose $G = (V,E)$ is a graph, whose vertices are colored red or blue. A bichromatic edge in G is an edge whose endpoints are colored differently.
    1. Design and analyze an algorithm that takes a graph $G = (V,E)$ with vertices colored red or blue, and returns a bichromatic edge, or says that none exists.
    2. Now, suppose that the graph $G$ is a path---$V = \{v_1,\ldots, v_n\}$, and $E = \{(v_i,v_{i+1}), 1 \leq i < n\}$. Further suppose that $v_1$ is red and $v_n$ is blue. Design and analyze an efficient algorithm that finds a bichromatic edge in this special case.
  8. In CS35, you saw that BFS can be used to find the shortest path in an unweighted graph, where "shortest path" here means the path with the fewest number of edges.
    1. Give an efficient algorithm which takes a directed acyclic graph $G=(V,E)$ as input and returns the length of the longest path in $G$.
    2. Give an efficient algorithm which takes a directed graph $G=(V,E)$ as input and returns the length of the longest simple path in $G$. (Recall that a simple path is a path where no vertex gets visited twice.)