Discussion 02

1. Arrange the following functions in increasing order of growth rate with $g(n)$ following $f(n)$ in your list if and only if $f(n) = O(g(n))$

   $\log(n^n)$

   $n^2$

   $n^{\log(n)}$

   $n \log(\log(n))$

   $2^{\log(n)}$

   $log^2(n)$

   $n^{\sqrt{2}}$

   Answer:

   • $log^2(n)$
   • $n \log(\log(n))$
   • $\log(n^n)$
   • $n^{\sqrt{2}}$
   • $n^2$
   • $2^{\log(n)}$
   • $n^{\log(n)}$

   Incorrect!

   The correct answer is:

   • $log^2(n)$
   • $2^{\log(n)} = n$
   • $n \log(\log(n))$
   • $\log(n^n) = n\log(n)$
   • $n^{\sqrt{2}}$
   • $n^2$
   • $n^{\log(n)}$

2. Suppose that $f(n)$ and $g(n)$ are two positive non-decreasing functions such that

   $f(n) = O(g(n))$

   Is it true that $2^{f(n)} = O(2^{g(n)})$?

   Answer: False: Consider $f(n) = 2n$, with $O(g(n))$ in which $g(n) = n$

   $2^{2n}$ is not $O(2^{n})$

3. Find an upper bound (Big $O$) on the worst case run time of the following code segment.

   Carefully examine to see if this is a tight upper bound (Big $\Theta$)

   void bigOh1(int[] L, int n)
       while (n > 0)
           find_max(L, n) // Finds the max in L[0..n-1]
           n /= 4
   

   Answer: The time complexity of the function is $O(n)$, and is $\Theta(n)$ when $L$ contains $n$ or more elements. If, for instance, $L$ only contains 1 element, then it is actually $\Theta(\log_{4}(n))$.

4. Find a lower bound (Big Ω) on the best case run time of the following code segment.

   Carefully examine to see if this is a tight lower bound (Big θ)

   string bigOh2(int n) if(n == 0) return "a"; string str = bigOh2(n-1); return str + str;

   Answer: The time complexity of the function is $\Omega(n)$, where $n$ is the value of the integer provided as input. but it is not $\Theta(n)$ unless string concatenation is a constant time operation. Typically, string concatenation has a time complexity of $\Theta(n)$, where $n$ is the length of the string. In this case, the length of the string is $2^n$ giving this function a time complexity of $\Theta(2^n)$, where $n$ is the number provided to the function as input. The space complexity of the function is $\Theta(2^n)$ as well. Also, wouldn't this function never end if it was provided a negatively-valued integer as input?

5. What Mathematicians often keep track of a statistic called their Erdős Number, after the great 20th century mathematician. Paul Erdős himself has a number of zero. Anyone who wrote a mathematical paper with him has a number of one, anyone who wrote a paper with someone who wrote a paper with him has a number of two, and so forth and so on. Supposing that we have a database of all mathematical papers ever written along with their authors:

   1. Explain how to represent this data as a graph.

   2. Explain how we would compute the Erdős number for a particular researcher.

   3. Explain how we would determine all researchers with Erdős number at most two.

   Answer:

   1. We would represent this data as an undirected graph where every edge within the graph had a weight of exactly one.

      To construct the graph...

      1. Enumerate all of the mathematical papers that had ever been published, keeping a record of the papers, and the authors of each paper.

      2. Every time an new author is encountered in the database, create a new vertex in the graph to represent that author.

      3. Create a fully connected subgraph among the co-authors of a given paper, where the vertices represent the authors, and the edges represent co-authorship.

   2. We would compute the Erdős number for a researcher by finding the shortest length path from a particular author vertex to the vertex representing Erdős.

   3. We would determine all researchers with Erdős number at most two by

      1. Starting from the vertex representing Erdős, enumerate the edges and compile the set of vertices adjacent to the Erdős vertex.

      2. Create an empty set $S_1$, and insert every vertex adjacent to Erdős.

      3. Create another empty set $S_2$.

      4. Enumerate the set of vertices in $S_1$, and for each vertex $v$, insert into $S_2$ all vertices adjacent to $v$, as well as $v$ itself, so $S_2 \supseteq S_1$.

      5. The answer is the set of vertices in $S_2$.

6. In class, we discussed finding the shortest path between two vertices in a graph. Suppose instead we are interested in finding the longest simple path in a directed acyclic graph. In particular, I am interested in finding a path (if there is one) that visits all vertices. Given a DAG, give a linear-time algorithm to determine if there is a simple path that visits all vertices.

   Answer: If a simple path visits all vertices, then there can only be one vertex with no inbound edges. If there are 2 vertices of this nature, then there is no path from one to the other. If there are 0 vertices of this nature, then the graph contains a cycle, and is thereby not a DAG. To solve this problem, start with the vertex with no inbound edges.

   Finding a topological ordering is a procedure that can be achieved in linear time, with a time complexity of $\Theta(m+n)$, where $n$ is the number of vertices and $m$ is the number of edges.

   If there exists exactly one topological ordering, then there is a simple path that visits all vertices.

Docs just now