CS 215 Homework 7

1. We used an argument based on decision trees to prove a lower bound of floor(lg(n)) + 1 for the worst case number of comparisons required for searching in a sorted array. Sketch out an alternative proof of this lower bound using an adversary argument. Don't worry about getting the details exactly right, just give the adversary's strategy, and evaluate the number of comparisons that will result.¹
2. The INDEPENDENT SET decision problem is defined as follows: given a graph G, and an integer k, determine whether there is a set of k vertices in G such that no two vertices in the set are connected to each other. Prove that INDEPENDENT SET is NP complete.
3. The PATH decision problem is defined as follows: given a directed graph G, and two nodes i and j, determine whether there is a directed path from i to j.
   • It is generally believed that PATH is not NP-complete. Why?
   • Show that proving PATH is not NP-complete would prove that P is not equal to NP. ²