Problem Set 4 Solution

[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



# 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] 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.




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





if found_isolated:



for k in range(2 ** n):



print(’Degree too small’)



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



[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.)




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



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



[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