1  Asymptotic Analysis : Finding primes (16 points)

1.a : Write pseudocode for an algorithm which given an integer n > 0, as input, finds all prime numbers p ; 2 6 p 6 n. Recall that a number is prime if it can be only divided by itself and the number 1. (2 points)

Remark 1.  Any algorithm that is correct would do, it does not have to efficient, but it has to be correct.

1.b: Consider the following algorithm known as sieve of Eratosthenes for the same problem:

A      Boolean Array of size n indexed from 2 to n, initially set to true for i = 2 to n:

if A [i] = true :

j     2 . i

while j < n:

A [j]     false

j     j +i

return {ij A[i] = trueg

Prove that the algorithm is a correct algorithm for Q.1.a by showing that any number i ; 2 6 i 6 n for which A[i] = true at the end is indeed a prime number, and any number i ; 26i6n for which A [i] = false is a composite number.(5 points)

Remark 2.  First argue that any i we set A [i] to false, only when we witness that it is a composite number. It is easy to see that any composite number can be written as product of prime numbers alone.  To prove that any i for which A [i] is left true throughout the execution of the for loop is a prime number, try to prove the following inductively:

At the beginning of ith execution of the for loop, all numbers {jj A[j] = true; j 6 ig are prime numbers. For example in the base case i = 2 and {jj A[j] = true; j 6 ig = {2g and 2 is a prime number as it can only be divided by itself and the number 1.

1.c: Analyze the running time of your answer in Q.1.a and the algorithm in Q.1.b as a function of n. You are doing asymptotic analysis, and you can assume that each individual step in the algorithm takes 1 unit of time to execute, except for the first step which takes O (n) units of time as you are initializing an Boolean array to all true. (3 points)

Remark 3. You can use the fact from number theory that for any integer x > 1,

p<北:pis a(X) prime    =  loglog x+ O (1)

In particular this implies that for any integer x > 1,

p<北:pis a(X) prime    =  x . (loglog x+ O (1))

1.d: How much memory space do you need to run your algorithm in Q.1.a and the algo- rithm in Q.1.b. You can assume that each variable takes 1 unit of storage and each array takes k unit of storage if the array is of length k . (1 point)

1.e: Throughout the course we will measure the running time and the memory of an algorithm as a function of the input size.  Here the input is number n > 0. We usually represent an integer as a binary string in computer science. How many binary (0 / 1) bits do you need to represent an integer n? (1 point)

1.e: Is algorithm Q.1.b an efficient algorithm for finding primes if you measure its running time / memory space in terms of the number of bits needed to represent n? Recall that we say that an algorithm is efficient if its running time/space complexity is polynomially related to its input size. (1 point)

1.f: If a number m is composite, then it can be written as product of two numbers a ; b where 26a ; b < m. Since m = a . b, min{a ; bg <^m . Because otherwise a and b are both strictly greater than^m and as a consequence a . b>[^m . ^ m = m] which is contradiction to our assumption that a:b = m. Thus if m is a composite number then it will have at least one divisor which is <^m . Can you use this idea to speed up the algorithm in Q.1.b? (3 point)

2  Graph  algorithms  :  Minimum  Spanning  Tree  (16 points)

2.a: Prove by induction that any tree T (V ; E) on n vertices contains exactly n ¡ 1 edges.

Remark 4.  Let's assume that T has n > 2 vertices, and m edges. Since T is connected and has two vertices, say u and v, there is at least one path from u to v . Let (u ; w) be the first edge on this path (w could be v). Remove this edge. Since a tree is minimally connected, removing this edge would disconnect the tree. Apply induction on the connected components of the forest obtained from T by removing (u ; w). A connected component of an undirected graph is a subset C  V of vertices which are all connected to each other by paths, and they are not connected to any other vertex outside C (that is, to any vertex in V / C).

2.b: Consider the following undirected graph. Argue that it has exponentially many (nO(n) which is 2O(nlogn)  as we can write n = 2logn, and nO(n) = (2logn)O(n) = 2O(nlogn)) many minimum spanning trees : G(V ; E) where V = [n] and E = {(u ; v)j u ; v 2 V ; u  vg and weight of every edge (u ; v) is 1. This graph is known as a complete graph as there is an edge between any two pair of vertices. (1 point)

Remark 5.  Any spanning tree would touch all the n vertices of the graph G. Any tree with n vertices has n ¡ 1 edges. Use this fact to show that any spanning tree of the above graph has weight n ¡ 1. Use this fact to show that every spanning tree of G(V ; E) given above is a minimum spanning tree.

2.c: Consider the following simple algorithm for finding the minimum spanning tree:

Input: G(V ; E)

Output: A minimum spanning tree T of G

     {g (Empty tree)

minWeight    1

for every spanning tree T of G:

if weight(T)<minWeight:

minWeight     weight(T)

    T

end if

end for

return 

Assume that each step in the algorithm takes 1 unit time individually (this is a generous assumption, because it is not clear how we can cycle through spanning trees T of G with 1 unit time per tree). With this assumption, what is the running of time of the algorithm in the worst case as a function of number of spanning trees of the graph G. Combine this with the answer in Q.2.b, to show that the algorithm given the graph in Q.2.b as input takes exponential (2O(nlogn)) time. (2 points)

Remark 6. Greedy algorithms like Prims and Kruskals are thus extremely efficient solu- tions to the minimum spanning tree problem compared to the possible first solution in Q.2.c. In this course we will focus on tools and techinques that you can use to design faster algorithms for a variety of problems that you may encounter in real life.

2.d: A fast implementation of Prim's algorithm can be obtained using Fibonacci Heap data structure for implementing a priority queue. This implementation of Prim's algorithm takes O (E + V log V) running time. If you use a binary heap instead the running time changes to O (V logV + E logV). Using an efficient data structure for Union-Find, Kruskalas algorithm can be made to run in time O (E log E). Here we are slightly abusing the notation where E inside the order notation denotes the numebr of edges and V inside the order notation denotes the number of vertices. Whereas outside the order notation, E ; V refer to the set of edges and the set of vertices respectively.

2.d.I: Compare the running time of these three algorithms (Prim's with Fibonacci Heap, Prim's with binary heap, Kruskals with optimized Union-Find) when E = O (log V); O (log* V); O (V log V); O (V1.5) and O (V2). (2 points)

2.d.II: Note that by basic graph theory E < V2 .  Use this fact to simplify Kruskals running time to O (E log V).  (1 point)

2.d.III: A social network like Facbook had 721 million users  (read vertices of the graph) and 68.7 billion friendships (read edges of the graph) in 2011 alone (see https:// arxiv.org/pdf/1111.4503.pdf for details).  721 million is roughly  229  (see https:// www.wolframalpha.com/input?i=7.21*10%5E8+in+base+2&key=kx699) and 68.7 billion is roughly 235 (seehttps://www.wolframalpha.com/input?i=6.87*10%5E10+in+base+2). Use this information to compute the values of E log V , E + V log V and E log V + V log V (you may use tools like wolframalpha, and remember that in this course log V usually denotes log 2V). Finally comment in one-line on why this information alone cannot say which is the fastest alogrithm for finding MST of such a large graph  (Hint: n ; 1000n ;

1010n are all O (n)).  (2 points)

2.e: An example input graph that we considered while designing minimum spanning trees is the graph of road network between various cities. Suppose you are given the following road-network graph of n = 6 cities and a minimum spanning tree (highlighted in light-blue), where the edge between u and v gets the weight which is the length of the road between u ; v .