Skip to main content

2 posts tagged with "CS3230"

View All Tags

Prove that the problem of determining whether a graph is connected is evasive

· 3 min read

P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference. (warning: possibly erroneous)

Claim: The problem of determining whether a graph is connected is evasive​

  • evasive as in it requires n C 2 queries i.e checking all the edges
  • Prove by making an adversary argument
  1. Suppose M is an algorithm that makes m < (n C 2) queries to decide whether the graph is connected
  2. The adversary responds to each query as follows:
    • suppose it receives the x th query for 1 <= x <= m
    • it considers the graph x defined by taking
      • all the responses before this query (those that have reply of 1 => those edges that exist)
      • all unqueried edges are set to 1 and hence considered as exist
      • the current queried edge is set to 0 and hence not included
    • if this graph is still connected without the current edge, then the adversary replies 0, else replies 1
      • it's like if the graph does not need the current edge to be fully connected, then return 0
  3. After all m queries, there are
    • responses for previously queried edges, which can be 1 or 0
    • one unqueried edge that is unknown
  4. The adversary makes two graphs using the above information:
    • G0: take all edges that are connected according to the responses + set the unqueried edge to 0 (ignore the unknown edge)
    • G1: take all edges that are connected according to the responses + set the unqueried edge to 1 (include the unknown edge)
  5. M cannot distinguish between G0 and G1 because both are consistent with its queries.
  6. The argument is that G0 is disconnected while G1 is connected, and hence since M can only decide whether the graph is connected or not, M must be wrong for one of the above inputs.
  7. G1 is connected trivially because it is consistent with the adversary's response strategy.
    • If you set the unqueried edges to 1, then the graph must be connected (together with those edges that exist, i.e. previously answered 1)
  8. G0 is disconnected by contradiction:
    • Suppose G0 is connected for purpose of contradiction
    • Then let (i, j) = the last unqueried pair of nodes be connected, i.e there is a path between i and j
    • Given the adversary strategy, it must replied 1 to all edges on this path, because they exist
    • let (i', j') be the edge on this path that was queried last. Then the adversary should have answered 0 as i and j will be set as connected since they are unqueried at that point.
    • So a contradiction arises and the assumption is incorrect.

Concrete Example​

  • n = 3 example

  • Since the algorithm is going to decide whether the graph is connected or not, the adversary simply takes the input that is not consistent with the algorithm.

Prove that every sorting algorithm must make at least lg(n!) comparisons

· 5 min read

P.S. My proof attempt/rewrite based on the solution discussed, uploaded mainly for my own reference.(warning: possibly erroneous)

Claim: Every sorting algorithm must make at least lg(n!) comparisons​

  • the log here is of base 2
  • Prove by making an adversary argument
  1. When we talk about running time, input size is an important consideration.
  2. The adversary wants to make life difficult for the algorithm, hence it will make choices that are against the algorithm's interest.
  3. Suppose we are given an array of n integers (input size = n), there are n! unique permutations of the set {1, ..., n}.
    • They are unique because if they are the same, then sorting the same array will take the same steps.
  4. The adversary could chose any of the permutations. It does not fix the input in advance in the hope that if the algorithm makes too few comparisons, there will be an example of how the algorithm fails to sort the array. In particular, there will be two inputs that are treated the same from the algorithm's perspective. And yet, one of them will not be correctly sorted.
  5. What the (sorting) algorithm can do is to issue a comparison query to ask whether the integer at the ith position is larger than the integer at the jth position.
  6. The adversary takes the following strategy to respond:
    • It looks through the current set of permutations(P), makes the comparison as required and takes note of the number(X) of permutations in P that satisfy the query i.e the ith integer is indeed larger than the jth integer.
    • It takes n comparisons in the very first run, since there are n permutations in P.
    • Suppose the number(X) of permutations that satisfy the query is larger or equal to the total size of the permutations / 2, the adversary returns YES and update the permutation set(P) to the satifying set.
    • Else (meaning less than half of the permutations satisfy the comparison query, more than half does not satisfy the comparison query), the adversary replies NO and set the permutations(P) to the larger set of permutations that does not satisfy the comparison query.
    • Either way the set of permutations to be examined next decreases. With the above strategy, the adversary is able to decrease at a slower rate, as it always try to keep at least half of the permutations. This makes sense because the goal of the adversary as mentioned earlier, is to come to a situation where there are more than one permutations left.
  7. Since the permutations decreases by at most half for every comparison query issued by the algorithm, there are at least two distinct permutations left. The algorithm will re-order both of the permutations in the same way, and must make one mistake. As all permutations are distinct, it is not possible to sort and re-order two different permutations in the same way to get the correct output.

Concrete Example​

  • n = 3
  • current set of permutations = {[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}
    • 6 different permutations
  • The algorithm will make less than lg(3!) = lg(6) = 2.584963 = ceil(2.584963) = 3 comparisons.
    • meaning it asks at most 2 comparison queries
    • trying to sort 3 items with 2 comparisons is not always possible (but ok for finding maximum)
  • The algorithm asks(0 indexed): is 0th > 1st?
  • The adversary checks the current set:
    • [1, 2, 3] No
    • [1, 3, 2] No
    • [2, 1, 3] Yes
    • [2, 3, 1] No
    • [3, 1, 2] Yes
    • [3, 2, 1] Yes
  • X = 3 (count of permutations that satisfy the comparison query)
  • The adversary answers Yes (Or No, but it does not matter)
  • The current set becomes {[2, 1, 3], [3, 1, 2], [3, 2, 1]}
  • The algorithm asks(0 indexed): is 1st > 2nd?
  • The adversary checks the current set:
    • [2, 1, 3] No
    • [3, 1, 2] No
    • [3, 2, 1] Yes
  • X = 1
  • The adversary answers No (to go against the algorithm's interest)
  • The current set becomes {[2, 1, 3], [3, 1, 2]}
  • The algorithm now makes a decision about how to sort the array, given the response.
  • To recall,
    • 0th > 1st is True
    • 1st > 2nd is False
    • So the algorithm does not know whether 0th is larger or smaller than 2nd. Suppose the algorithm choose 0th to be larger and arrange as such: 0th > 2nd > 1st
  • In the available set, [3,1,2] will be sorted correctly. However, the set [2, 1, 3] does not.
    • [2, 1, 3] becomes [2, 3, 1], which is still not sorted!
  • The algorithm fails at sorting with less than lg(n!) comparisons.