Problem Set 4 Solution

$30.00

Description

  1. [4 marks] Binary representation and algorithm analysis. Consider the following algorithm, which manually counts up to a given number n, using an array of 0’s and 1’s to mimic binary notation.1

  • from math import floor, log2

2

3

  • def count(n: int) -> None:

  • # Precondition: n > 0.

  • p = floor(log2(n)) + 1# The number of bits required to represent n.

7 bits = [0] * p # Initialize an array of length p with all 0’s.

8

  • for i in range(n): # i = 0, 1, …, n-1

  1. # Increment the current count in the bits array. This adds 1 to

  1. # the current number, basically using the loop to act as a “carry” operation.

  1. j = p – 1

  1. while bits[j] == 1:

  1. bits[j] = 0

  1. j -= 1

  1. bits[j] = 1

For this question, assume each individual line of code in the above algorithm takes constant time, i.e., counts as a single step. (This includes the [0] * p line.)

  1. [3 marks] Prove that the running time of this algorithm is O(n log n).

  1. [1 mark] Prove that the running time of this algorithm is (n).

  1. [10 marks] Worst-case and best-case algorithm analysis. Consider the following function, which takes in a list of integers.

  • def myprogram(L: List[int]) -> None:

  • n = len(L)

  • i = n – 1

  • x = 1

  • while i > 0:

  • if L[i] % 2 == 0:

7

i

= i // 2 # integer division, rounds down

8

x

+= 1

  • else:

10 i -= x

Let W C(n) and BC(n) be the worst-case and best-case runtime functions of myprogram, respectively, where n represents the length of the input list L. You may take the runtime of myprogram on a given list L to be equal to the number of executions of the while loop.

  1. [3 marks] Prove that W C(n) 2 O(n).

  1. [2 marks] Prove that W C(n) 2 (n).

  1. [2 marks] Prove that BC(n) 2 O(log n).

  1. [3 marks] Prove that BC(n) 2 (log n).

Note: this is actually the hardest question of this problem set. A correct proof here needs to argue that the variable x cannot be too big, so that the line i -= x doesn’t cause i to decrease too quickly!

3. [14 marks] Graph algorithm. Let G = (V; E) be a graph, and let V = f0; 1; : : : ; n

1g be the vertices

of the graph. One common way to represent graphs in a computer program is with an adjacency matrix, a two-dimensional n-by-n array2 M containing 0’s and 1’s. The entry M[i][j] equals 1 if fi; jg 2 E, and 0 otherwise; that is, the entries of the adjacency matrix represent the edges of the graph.

Keep in mind that graphs in our course are symmetric (an edge fi; jg is equivalent to an edge fj; ig), and that no vertex can ever be adjacent to itself. This means that for all i; j 2 f0; 1; : : : ; n 1g, M[i][j] == M[j][i], and that M[i][i] = 0.

The following algorithm takes as input an adjacency matrix M and determines whether the graph contains at least one isolated vertex, which is a vertex that has no neighbours. If such a vertex is found, it then does a very large amount of printing!

  • def has_isolated(M):

  • n = len(M)# n is the number of vertices of the graph

  • found_isolated = False

4

  • for i in range(n): # i = 0, 1, …, n-1

  • count = 0

  • for j in range(n):# j = 0, 1, …, n-1

8 count = count + M[i][j]

  • if count == 0:

10

found_isolated = True

11

break

12

  1. if found_isolated:

  1. for k in range(2 ** n):

  1. print(’Degree too small’)

    1. [3 marks] Prove that the worst-case running time of this algorithm is (2n).

    2. [3 marks] Prove that the best-case running time of this algorithm is (n2).

    1. [1 mark] Let n 2 N. Find a formula for the number of adjacency matrices of size n-by-n that represent valid graphs. For example, a graph G = (V; E) with jV j = 4 has 64 possible adjacency matrices.

Note: a graph with the single edge (1; 2) is considered di erent from a graph with the single edge (2; 3), and should be counted separately. (Even though these graphs have the same \shape”, the vertices that are adjacent to each other are di erent for the two graphs.)

    1. [2 marks] Prove the formula that you derived in Part (c).

    1. [2 marks] Let n 2 N. Prove that the number of n-by-n adjacency matrices that represent a graph with at least one isolated vertex is at most n 2(n 1)(n 2)=2.

    1. [3 marks] Finally, let AC(n) be the average-case runtime of the above algorithm, where the set of inputs is simply all valid adjacency matrices (same as what you counted in part (c)).

Prove that AC(n) 2 (n2).

  • In Python, this would be a list of length n, each of whose elements is itself a list of length n.

Page 4/4