The midterm exam covers all material introduced before fall break, up to and including the section on Divide and Conquer. You are responsible for all material discussed in lecture or lab, all material on homework assignments, and material from assigned readings. 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
  • Induction
  • Proof by contradiction
• Data Structures
  • List
  • Priority Queue
  • Hash Table
  • Adjacency List and Adjacency Matrix
• Graph Algorithms
  • Breadth-First Search
  • Depth-First Search
  • Topological Sort
  • Dijkstra's Algorithm
  • Minimum Spanning Tree
  • Kruskal's Algorithm
  • Prim's Algorithm
• Greedy Algorithms
  • Greedy Algorithm for interval scheduling, minimizing maximum lateness
  • Methods for proving greedy algorithms are optimal (stays ahead, exchange argument)
• Divide and Conquer
  • Divide and Conquer algorithms for sorting, integer multiplication, counting inversions
  • Recurrence Relations
  • Recursion Tree, Substitution Method, Partial Substitution

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. 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)}$
3. In the shortest paths problem, you are given a graph $G = (V,E)$ with nonnegative lengths $\{\ell_e : e \in E\}$ along with a vertex $s \in V$, and you must return for each vertex $v \in V$ the length of the shortest path $s \leadsto v$.

   Dijkstra's algorithm provides an efficient solution to the shortest paths problem. Consider the following pseudocode for Dijkstra's algorithm:

   Dijkstra($G,s,\ell$) {
   

   S = {s}
   Initialize d[i] = $\infty$ for all vertices i
   d[s] = 0
   while $S \neq V$ {
   

   pick $v \in V\setminus S$ with the cheapest $\mathsf{cost}(v)$, where
   $\qquad\mathsf{cost}(v) := \min_{u \in S} d[u] + \ell_{(u,v)}$
   $d[v] := \mathsf{cost}(v)$
   add $v$ to $S$
   

   }

   }

   1. Show that Dijkstra's algorithm correctly returns the shortest paths. You can assume the graph is connected.
   2. What is the running time of Dijkstra's algorithm? You're free to choose whatever data structure(s) you need to answer this problem, but must provide the most efficient running time you can.
4. Solve the following recurrence relations, using (i) recursion trees, (ii) substitution method, and (iii) partial substitution
   • $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$
5. 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?
6. 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.