CPSC490: Midterm 2 practice questionsThese questions didn't make it to the midterm because they were either too hard or too similar to some of the questions that did make it.Question 1True or False: There are infinitely many primes. Question 2True or False: Branch-and-bound always improves the running time complexity of an algorithm. Question 3If p and q are two prime number, and n=p*p*q. What is phi(n)? Question 4Compute g = gcd(3453, 6534) and find integers A and B such that 3453A + 6534B = g. Question 5Euler's theorem tells us that aphi(n) = 1 (mod n). Hence, because
phi(p)=p-1 when p is prime, we get Fermat's Little Theorem:
if p is prime, then ap-1 = 1 (mod p). Question 6You are given a set S of at most 30 integers. The sum of all the integers in S is at most 1000. Describe an algorithm that finds a subset of S (if one exists), such that all the numbers in the subset add up to a prime number. Compute the running time of your algorithm. It should be able to run in a few seconds on a reasonable desktop computer. Hint: there are 168 primes in the range [2, 1000]. Question 7A clique in an undirected graph is a set of k vertices that
have all the k(k+1)/2 possible edges between them. The problem
of determining whether a graph has a clique of size k is
NP-complete. Here is a simple backtracking algorithm for it. bool used[64], graph[64][64], n; // i is the vertex we are considering // k is the size of the clique bool hasClique( int i, int k ) { if( i == n ) { // considered all vertices - // check that we have k of them int usedVertices = 0; for( int j = 0; j < n; j++ ) if( used[j] ) usedVertices++; if( usedVertices != k ) return false; // check that they make up a clique - // that is, we have an edge between each pair of // used vertices for( int u = 0; u < n; u++ ) if( used[u] ) for( int v = 0; v < n; v++ ) if( used[v] ) if( !graph[u][v] ) return false; return true; } // skip vertex i if( hasClique( i + 1, k ) ) return true; // add vertex i to our clique used[i] = true; bool result = hasClique( i + 1, k ); used[i] = false; return result; }Desribe how you would apply branch-and-bound to reduce, in general, the number of recursive calls made by hasClique(). Scroll down for the answers. AnswersQuestion 1True. We saw a proof in class. The trick was to assume that X was the largest prime. Then we construct Y=X!+1, which is a number larger than X and is not divisible by any integer between 2 and X, inclusive (it always gives remainder 1). Hence, Y must itself be prime, but it is larger than X. This is a contradiction. Therefore, there is no largest prime, and since we know that at least one prime exists, there must be an infinite number of them. Question 2False. Any question that tries to make a broad statement like that is most likely false. Branch-and-bound tries to cut off (or prune) some of the branches in a recursive solution. To do that, we usually need to use extra memory (like the arrays for slash and backslash codes in the 8 queens problem) or spend extra time (like in the Firetruck problem from the homework). The hope is that we gain a significant overall improvement in the running time because we save a lot of recursive calls. Of course, we are not guaranteed that this will work in every case. For example, in the Firetruck problem, if the graph is complete (has all the possible edges), then doing a BFS in every recursive call will only make the running time worse. In this case, branch-and-bound slows down the algorithm. Question 3
The formula that we had for phi(n) when
n=p1a1
p2a2...
pnan is Question 4
gcd(3453, 6534) = gcd(6534, 3453). The extended Euclidean algorithm
would do the following: 6453 = 1*3453 + 3000 3453 = 1*3000 + 453 3000 = 6*453 + 282 453 = 1*282 + 171 282 = 1*171 + 111 171 = 1*111 + 60 111 = 1*60 + 51 60 = 1*51 + 9 51 = 5*9 + 6 9 = 1*6 + 3 6 = 2*3 + 0This tells us that the GCD is g=3. To get A and B, we can work from the bottom up, substituting each equation into the one above. 3 = 1*9 - 1*6 = 1*9 - 1*( 51 - 5*9 ) = -1*51 + 6*9 = -1*51 + 6*( 60 - 1*51 ) = 6*60 - 7*51 = 6*60 - 7*( 111 - 1*60 ) = -7*111 + 13*60 = -7*111 + 13*( 171 - 1*111 ) = 13*171 - 20*111 = 13*171 - 20*( 282 - 1*171 ) = -20*282 + 33*171 = -20*282 + 33*( 453 - 1*282 ) = 33*453 - 53*282 = 33*453 - 53*(3000 - 6*453 ) = -53*3000 + 351*453 = -53*3000 + 351*(3453 - 1*3000) = 351*3453 - 404*3000 = 351*3453 - 404*(6453 - 1*3453) = 404*6453 - 755*3453.This gives us A=-755 and B=404. Question 5
a)Yes. This is exactly what the theorem states. Question 6First of all, we need to find all the primes in the range [2,1000]. This is done by sieve(). We could also run the isPrime() function on each of the 1000 numbers - that would be fast enough. Once we have computed all the primes, we need to check whether there is a subset of S that adds up to a particular prime. This is precisely problem S from the homework (Reviving Kenny). See the solution to problem S (once it is posted). We solve this problem for each of the 168 primes and return true if at least one of them gives us a Yes answer. Question 7The algorithm is very similar to the plain recursive solution to the Partition problem that we saw in class. For each vertex, it either adds the vertex to the clique or it doesn't. In both cases, it calls itself on the rest of the vertices. We would like to avoid many of these recursive calls by detecting early on that the vertices we have picked so far cannot possibly be part of a clique. Note that in a clique, each vertex is connected to each other vertex. This means that when we add a vertex to the clique, we should check whether it is connected to all the vertices we already have. If not, then we should not add this vertex. Another improvement is to note that once we have successfully added k vertices to the clique, we do not need to add any more - we are done and can simply return true. Once we have added these two improvements, there is no longer a need to check that we have a clique when i reaches n. It is guaranteed by the way we add vertices. Here is the code. bool used[64], graph[64][64], n; int verts[64]; // the vertices we have picked int numPicked; // the number of vertices in verts[] // i is the vertex we are considering // k is the size of the clique bool hasClique( int i, int k ) { // do we have a complete clique? if( numPicked == k ) return true; // have we considered all vertices? if( i == n ) return false; // skip vertex i if( hasClique( i + 1, k ) ) return true; // check whether vertex i is connected to all // the vertices we already have for( int j = 0; j < numPicked; j++ ) if( !graph[verts[j]][i] ) return false; // add vertex i to our clique used[i] = true; verts[numVerts++] = i; // recurse bool result = hasClique( i + 1, k ); // remove the vertex from the clique (backtrack) numVerts--; used[i] = false; return result; } Surprisingly, the code even becomes shorter with these optimizations because the complicated check at the end is gone. We need to add a verts[] array that stores the vertices currently in the clique. numPicked is the number of vertices we have picked so far to be in the clique (they have edges between all of them). numPicked should be initialized to 0. |