CPSC490: Midterm 2 practice questions

Question 1

True or False: There are infinitely many primes.

Question 2

True or False: Branch-and-bound always improves the running time complexity of an algorithm.

Question 3

If p and q are two prime number, and n=p*p*q. What is phi(n)?

Question 4

Compute g = gcd(3453, 6534) and find integers A and B such that 3453A + 6534B = g.

Question 5

Euler's theorem tells us that a^phi(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 a^p-1 = 1 (mod p).
a) It is known that 6216541 is prime, then is 7^6216540 = 1 (mod 6216541)?
b) It is known that 7^1734250 = 1660565 (mod 1734251), then can we conclude that 1734251 is NOT prime?
c) It is known that 2²⁰⁴⁶ = 1 (mod 2047), then can we conclude that 2047 is prime?

Question 6

You 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 7

A 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;
}

Answers

Question 1

True. 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 2

False. 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=p₁^a₁ p₂^a₂... p_n^a_n is
phi(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/p_n).
In this case, there are only 2 primes that divide n - p and q. n can be written as n=p²q¹, so phi(n) = n(1-1/p)(1-1/q) = p(p-1)(q-1).

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    + 0

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.

Question 5

a)Yes. This is exactly what the theorem states.
b)Yes. If 1734251 were prime, then the theorem would apply, and 7^1734250 would have to be congruent to 1 (mod 1734251).
c)No. The theorem is not an if-and-only-if statement. In fact, 2047=23*89.

Question 6

First 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 7

The 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.