$30.00
Description

[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, …, n1

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

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

j = p – 1

while bits[j] == 1:

bits[j] = 0

j = 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.)

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

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

[10 marks] Worstcase and bestcase 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 worstcase and bestcase 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.

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

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

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

[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 twodimensional nbyn array^{2} 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, …, n1

count = 0

for j in range(n):# j = 0, 1, …, n1
8 count = count + M[i][j]

if count == 0:
10 
found_isolated = True 
11 
break 
12 

if found_isolated:

for k in range(2 ** n):

print(’Degree too small’)


[3 marks] Prove that the worstcase running time of this algorithm is (2^{n}).

[3 marks] Prove that the bestcase running time of this algorithm is (n^{2}).



[1 mark] Let n 2 N. Find a formula for the number of adjacency matrices of size nbyn 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.)


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



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



[3 marks] Finally, let AC(n) be the averagecase 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 (n^{2}).

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