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 n finds the max in L 0 n 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 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 a Explain how to represent this data as a graph b Explain how we would compute the Erd s number for a particular researcher c Explain 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
View Full Document
Unlocking...