Question

Algorithm and computing system(Python)

1. What is dynamic programming? Why does it usually work faster?

2. Using the dynamic programming solution for the knapsack problem, compute a solution to this knapsack problem:

Weight          value

2                     16

3                     19

4                     23

5                     28

total number of items = 4

capacity of the knapsack = 7

3. Suppose that the similarity between an object O and 6 other objects in the database A,B,C,D,E and F are as follows:

sim(A,O) = 0.1

sim(B,O) = 0.3

sim(C,O) = 0.85

sim(D,O) = 0.8

sim(E,O) = 0.9

sim(F,O) = 0.6

Also, suppose objects A, B and C are in class 1 and

D,E and F are in class 2.

With k=4, what class should O be in, using the kNN algorithm?

With k=2, what class should O be in, using the kNN algorithm?

Answer 1

QUESTION 1:

Dynamic Programming is a class of algorithms in computer programming which solves a problem by dividing a problem into sub-problems and optimum substructure of the problem so that they can be reused.

They are usually faster because each sub-problem is solved only once and is saved for future use. So that if in another solution path the same sub-problem is encountered again it does not solve it completely and instead uses the value stored previously for the sub-problem since it had already been solved once. This saves time and memory thus it is said to work faster.

QUESTION 2:

THE CODE IS:

def knapSack(W, wt, val, n):

  K = [[0 for x in range(W + 1)] for x in range(n + 1)]

  # Build the table for k[][] in bottom-top/backtracking approach

  for i in range(n + 1):

    for w in range(W + 1):

      if i == 0 or w == 0:

        K[i][w] = 0

      elif wt[i-1] <= w:

        K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])

      else:

        K[i][w] = K[i-1][w]

# return the max value

  return K[n][W]

# driver function

def main():

# initialising the value list

val = [16, 19, 23, 28]

# initialising the weightlist

wt = [2, 3, 4, 5]

# initialising the maximum weight of the sack

W = 7

# length of the list of items

length = len(val)

print('The max value of items is:', knapSack(W, wt, val, length))

if __name__ == '__main__':

main()

SCREENSHOT OF CODE TO UNDERSTAND INDENTATION AND OUTPUT:

The max value of items is: 44 Qe 1 4 5 main.py saved def knapsack(W, wt, val, n): 2 K = [[@ for x in range (W + 1)] for x in range(n + 1)] 3 # Build the table for k[][] in bottom-top/backtracking approach for i in range(n + 1): for w in range(W + 1): 7 if i == or w == 0: K[i][w] = 0 elif wt[i-1] <= W: 10 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 11 else: 12 K[i][w] = K[i-1][w] 6 8 9 13 14 # return the max value return K[n][W] 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 # driver function def main(): # initialising the value list val = [16, 19, 23, 28] # initialising the weightlist wt = [2, 3, 4, 5] # initialising the maximum weight of the sack W = 71 # length of the list of items length = len(val) print('The max value of items is:', knapsack(W, wt, val, length)) if name == '_main_': main()

QUESTION 3:

i) k = 4. Since k = 4, we need to consider it's nearest 4 neighbours to classify O as either Class 1 or Class 2.
It's 4 nearest neighbours are A(0.1), B(0.3), F(0.6) & D(0.8) with A being the nearest and D being the 4th nearest point.
Since A & B belong to class 1 and D & F belong to class 2 it's a tie with a vote of 2 - 2. Therefore, O could either be in class 1 or class 2.

ii) k = 2. Since k = 2 we will consider it's 2 nearest neighbours to classify O. The two closest points are A(0.1) and B(0.3). Since A & B both belong to class 1 O belongs to Class 1 with a vote of 2 - 0.