Problem 4. Consider the Dynamic Matrix ADT for representing an matrix A = {a}{j=1 that supports...

   

Transcribed Image Text:

Problem 4. Consider the Dynamic Matrix ADT for representing an matrix A = {a}{j=1 that supports the following operations: CREATE(): creates a 1 x 1 matrix where a1,1 = 0. SET/GET (i, j): set or get the value of the entry aj. INCREASE-SIZE: If the current size of the matrix is n x n, increase it to n+1 xn+1 such that the new entries are set of 0. In other words, A becomes A' such that aj aj if 1 i, j < n, and a = 0 otherwise. = Your task is to come up with a data structure implementation for the Dynamic Matrix ADT that uses O(n) space, where n is the size of the matrix, and CREATE, SET, GET take O(1) and INCREASE-SIZE takes O(n) time. Remember to: a) Describe your data structure implementation in plain English. b) Prove the correctness of your data structure. c) Analyze the time and space complexity of your data structure. [6 marks] [6 marks] [6 marks] Problem 4. Consider the Dynamic Matrix ADT for representing an matrix A = {a}{j=1 that supports the following operations: CREATE(): creates a 1 x 1 matrix where a1,1 = 0. SET/GET (i, j): set or get the value of the entry aj. INCREASE-SIZE: If the current size of the matrix is n x n, increase it to n+1 xn+1 such that the new entries are set of 0. In other words, A becomes A' such that aj aj if 1 i, j < n, and a = 0 otherwise. = Your task is to come up with a data structure implementation for the Dynamic Matrix ADT that uses O(n) space, where n is the size of the matrix, and CREATE, SET, GET take O(1) and INCREASE-SIZE takes O(n) time. Remember to: a) Describe your data structure implementation in plain English. b) Prove the correctness of your data structure. c) Analyze the time and space complexity of your data structure. [6 marks] [6 marks] [6 marks]