CS 310: Design and Analysis of Algorithms

All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

1. Consider the problem of finding the maximum number of floors that a student may be dropped from and survive. Assume that all students are equally resilient and will die from the same height. Given three students and that students are relatively heavy, what is an algorithm to minimize the number of trials in the experimental process?

   This problem is potentially addressed through a process called balancing. Balancing divides the problem into among subsolutions that deal with particular elements of the problem effectively. These subsolutions are then balanced in running time to find an efficient solution. For the student dropping problem with two students an effective division is:

   • With the first student, divide the building into $k$ divisions and drop the student from each $\frac{n}{k}$^th floor until a trial is unsuccessful. The maximum number of trials is $\frac{n}{k}$.
   • With the second student, start at the $\frac{\left(k_f-1\right)n}{k}$^th floor and drop the student at each successive floor until there is a second failure. This will identify the correct floor. The maximum number of trials is $k$.

   The value of k to balance these factors is:

   $$\begin{array}{ccccccccccc}\frac{n}{k}& =& k& \iff & n& =& k^2& \iff & k& =& \sqrt{n}\end{array}$$

   When adding an additional student the algorithm simply repeats. The first student is used to find a grand division, the second divides the grand division and the third is sequential within those bounds. The balancing of these three factors is:

   $$\begin{array}{ccccccccccccccc}\frac{n}{k_1}& =& \frac{\frac{n}{k_1}}{k_2}& =& \frac{n}{k_1{k}_2}& =& k_2& \Rightarrow & \frac{n}{k^2}& =& k& \iff & k& =& \sqrt[3]{n}\end{array}$$

2. Suppose a graph is known to be four-colorable. Design an algorithm that colors a graph with a minimum number of colors in the worst case. The algorithm should use the following properties:

   • the neighborhood of a vertex in a k-colorable graph is (k - 1)-colorable
   • if the neighborhood is small, the nodes can be colored with k colors

   Consider first the problem of coloring a graph that is known to be three-colorable. One method is to balance two strategies:

   • when degree(x) ≥ some factor k, two-color all the neighbors of x. this will use two colors.
   • when degree(x) < k, assign a distinct color to x and each of the neighbors of x

   The algorithm operates by only considering uncolored vertices and using the first method until there are no vertices with a degree ≥ k remaining. This will use, in the worst case, $2\frac{n}{k}$ colors. The remaining vertices are then colored with the second method. This will use $k$ colors in the worst case.

   Balancing these two factors is simply:

   $$\begin{array}{ccccccccccc}2\frac{n}{k}& =& k& \iff & 2n& =& k^2& \iff & k& =& \sqrt{2n}\end{array}$$

   The basic method used in the algorithm can be extended to handle four-colorable graphs through simple recognition that the neighborhood of a vertex in a four-colorable graph is a three-colorable graph.

   In the worst case, the number of colors used in the three-coloring algorihm when $k=\sqrt{2n}$ (recalling the sides are balanced at k) is:

   $$\begin{array}{ccc}2k& =& 2\sqrt{2n}\end{array}$$

   So, consider an algorithm where while there is a vertex with degree ≥ j, then three color the neighborhood of x. When there are no uncolored vertices remaining with degree ≥ j color the remainder with distinct colors. The balancing of these two stategies then is:

   $$\begin{array}{ccccccccccccccc}2\sqrt{2k}\frac{n}{k}& =& k& \iff & 2\sqrt{2}n& =& \frac{k^2}{\sqrt{k}}& =& k^{\frac{3}{2}}& \iff & k& =& {\left(2\sqrt{2}n\right)}^{\frac{2}{3}}& =& \sqrt[3]{8n^2}\end{array}$$

3. Consider a three-colorable graph with $O\left(\sqrt{n}\right)$ edges. Design a polynomial time algorithm to color the edges with $o\left(\sqrt{n}\right)$ colors.

   To say that a graph has $O\left(\sqrt{n}\right)$ edges means that the number edges is ≤ $c\sqrt{n}$.

   Consider the previously presented balancing solution for coloring a graph that is known to be three-colorable, with an additional step added

   • ∀ x ∋ degree(x) ≥ k, two-color neighbors(x) and remove them from consideration
   • ∀ x ∋ 0 > degree(x) < k, assign a distinct color to each of neighbors(x) and remove them from consideration
   • ∀ x remaining (degree(x) = 0), color with a single color

   The previous analysis looked at computational complexity in terms of the number of vertices eliminated. It is also possible to conceptualize the complexity in terms of edges eliminated. Because each iteration of the algorithm draws from a new set of colors, if a vertex at one end of an edge is colored during one iteration the other vertex can only be colored with the same colors during that particular step. Future iterations will draw from a different set of colors. So, once one end of an edge has been colored the edge can no longer be a source of conflict in the coloring problem.

   The maximum number of vertices connected with m edges is if each edge connects two vertices with degree 1. In this situation there are 2m nodes with degree > 0. In a graph with m vertices, there must be ≥ n - 2m initially disconnected vertices (degree(x) = 0). Additionally, each iteration of the other two coloring schemes will each leave a disconnected vertex.

   The addition of a consideration for those disconnected vertices in a graph with a low number of edges allows the number of colors to be bounded by the number of edges rather than the number of vertices. Omitting the one color used at the end to color all the degree 0 vertices, the balancing peoblem is now:

   $$\begin{array}{ccccccccccccc}\frac{2m}{k}& =& \frac{c\sqrt{n}}{k}& =& k& \iff & c\sqrt{n}& =& k^2& \iff & k& =& \sqrt{c\sqrt{n}}\end{array}$$

   The number of colors used with this value of k is:

   $$\begin{array}{ccccccccc}\frac{c\sqrt{n}}{k}+k& =& \frac{c\sqrt{n}}{\sqrt{c\sqrt{n}}}+\sqrt{c\sqrt{n}}& =& 2\sqrt{c\sqrt{n}}& =& O\left(\sqrt[4]{n}\right)& =& \mathrm{o}\left(\sqrt{n}\right)\end{array}$$

4. A clique within a graph is a fully connected subgraph. Suppose that a graph has a clique of size $\frac{n}{2}$. Show that there is a polynomial time algorithm to find a clique of size $\Omega \left(log\left(n\right)\right)$.