\$30.00

Category:

## 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 =  * 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  * 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