CS代考 Review ofthe AsymptoticNotation – cscodehelp代写

Review ofthe AsymptoticNotation

Discussion 2
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 nn, n2, nlog n, n log log n, 2log n, log2 n, n􏰡2
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 2f(n) = O(2g(n) )?
3. Find an upper bound (Big O) on the worst case run time of the following code segment.
void bigOh1(int[] L, int n)
while (n > 0)
find_max(L, 􏰢); //fi􏰢d􏰝 􏰚he ma􏰣 i􏰢 L[0􏰑􏰢-1] n = n/4;
Carefully examine to see if this is a tight upper bound (Big 􏰤)
4. Find a lower bound (Big 􏰥) on the best case run time of the following code segment.
string bigOh2(int n)
if(n == 0) return “a”;
string str = bigOh2(n-1);
return str + str;
Carefully examine to see if this is a tight lower bound (Big 􏰤)
5. What Mathematicians often keep track of a statistic called their Erd􏰦s Number, after the
great 20th century mathematician. 􏰦s himself has a number of 􏰧ero. An􏰨one 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:
a. Explain how to represent this data as a graph.
b. E􏰣plain how we would compute the Erd􏰦s number for a particular researcher.
c. E􏰣plain how we would determine all researchers with Erd􏰦s number at most two.

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.

Come up with a greedy solution to this problem on your own and solve the above example numerically. Then try to prove that your solution is optimal.