Programming Assignment Question 3

ASSIGNMENT 1

Question 1.

Pseudocode:       x ← 0 
for k ← 1 to n do 
for j ← k to 2n do 
x ← x + 1

1. The inner most statement x <- x + 1 will be executed 2n²

Using the summation notation, for every item in loop i up to n. The inner loop will perform the operation X = x + 1 a total of 2n times which is the outer boundary loop for the inner loop.

This means that the operation would be preformed 2n * n times. The figure above shows the progressive count of j (representing x = x + 1) as it loops till 2n and then begins again for the next value of n in the outer loop.

1. When computing the time complexity of a given function, it is given by

T_(n) = 4n² – 2n + 2.

Giving the fact that theses numeric constants 4 and 2 tend to reduce in effective account with increasing size of n, we can give the time complexity formula as

T_(n) = O(n²). Where n is number of times to totality of the operations in a function would be carried out.

Giving the fact that in part a we estimated that the code x = x + 1 would run 2n² times. That would be the value of n in the time complexity equation, meaning that

T_(n) = O(2n⁴) after substituting 2n for n.

This means that if n in the pseudocode was 9, the number of times the code will run would ne 162 and the time complexity is given by 1.3122 * 10⁴

Question 2.

T_(n)  = if n = 1

3T(n/3) + 2cn

Assuming n to be 3^m, we derive the linear equation 3^m +6c^m.

We can discount c as its influence on the result will decrease with increase in m.

We can get a closed form by sequentially increasing m.

E.g. if m = 1, T(n) = 9. m = 2, T(n) = 42……….

Question 3.

prices = [1,2,3,4,5,6,7,8]

budget = 6

combos = list()

for x in range(7):

if prices[x] + prices[x+1] <= budget and prices[x] != prices[x+1]:

combos.append("" + str(prices[x]) + ", " + str(prices[x+1]))

print("The number of possible combinations is " , len(combos))

for combo in combos:

print(combo)

The code declares and integer array prices and an integer for variable budget.

It ten has an outer for loop looping over the entire array and then an inner one looping over the array beginning from the value on the array index just after the current index of the outer loop. For a combination to be valid hence, it must give to distinct numbers whose sum is less than or equals to the budget.

Question 4. From the pseudocode, the loop starts from the 0 meaning the first entry into the data structure making the appropriate data structure to be used a queue based on its first in last out framework as the loop starts from the first index position of the array dequeuing would remove the first entry and enqueuing would add a last entry into the queue.

4 b.

Adjacency Matrix

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

Question 5.

area = [[1,1,0,1],[0,1,0,0],[0,0,1,1],[0,1,1,1]]

def checkRight(i,j,connectedNodes = [],area=[]):

if j < (len(area) - 1) :

if area[i][j+1] == 0 :

cord1 = "" + str(i) + " , " + str(j + 1)

connectedNodes.append(cord1)

checkDown(i,j+1,connectedNodes)

checkRight(i,j+1,connectedNodes)

def checkDown(i,j,connectedNodes = [],area=[]):

if i < (len(area) - 1) :

if area[i+1][j] == 0 :

cord = "" + str(i+1) + " , " + str(j)

connectedNodes.append(cord)

checkRight(i+1,j,connectedNodes,area)

checkDown(i+1,j,connectedNodes,area)

 

def checkBurntArea(area=[],finalConnectedNodes = []):

for x in range(0,len(area) - 1):

for y in range(0,len(area) - 1):

if area[x][y] == 0:

connectedNodes = []

cor = "" + str(x) + " , " + str(y)

connectedNodes.append(cor)

checkRight(x,y,connectedNodes,area)

checkDown(x,y,connectedNodes,area)

if len(finalConnectedNodes) < len(connectedNodes):

finalConnectedNodes = connectedNodes

print("Total connections in largest burnt area : " , len(finalConnectedNodes))

for m in range(0,len(finalConnectedNodes)):

print(finalConnectedNodes[m])

checkBurntArea(area,list())

The code block loops through the individual points in the 2D array, for each point it checks if the values is equal to zero, if so it adds the coordinates of that point to the list. It then class two functions to check the coordinate to the right and directly below the present coordinate. If they are zero they are added to the list. This functions then recursively checks if those coordinates to the right and below have zero values around them. The loop is broken for a none zero value. The program then check if the length of the resulting list is larger than that of the holding list we created, if so the contents of the holding list are replaced with this new list. The program does this for all values in the values in the array. The final list is then printed out.