22C:21: Computer Science II: Data Structures

Quiz 0


1. Consider the following function
	int max(int[][] X){
		int maximum = X[0][0];
		int rows = X.length;
		int cols = X[0].length;

		for(int i = 0; i < rows; i++)
			for(int j = 0; j < cols; j++)
				if (X[i][j] > maximum)
					maximum = X[i][j];

		return maximum;
	}
This function attempts to find the maximum element in a 2-dimensional array of integers and returns its value. Suppose you send in the following 2-d array
		20	40	10
		10	21
		100	30	23	12
as an argument to the function max. Will it work correctly and return the value 100 (Yes or No)? Justify your answer is one sentence.

Answer: No. The function assumes that all rows have the same length as the 1st row and so it looks for the 3rd element in the 2nd row, when there is none.

2. Your friend looks at the interface and implementation of the Vector class and says, "The function set is unnecessary. Instead you could use a call to remove followed by a call to add. For example, you could replace a call to set(index, element) by the following code." Your friend goes on write the following code.

	
			remove(index);
			add(index, element);
What is the problem with your friend's suggestion? Is it
  1. Incorrect (i.e., the code she suggests as a replacement for set does not do what set does).
  2. Inefficient (i.e., the code she suggests as a replacement for set is takes much more time to run as compared to set).
  3. Both
Pick one of the three choices above. Justify your answer is one sentence.

Answer: No. Inefficient. The remove operation takes approximately n steps in the worst case and so does the add operation, whereas set takes one step, independent of the size of the Vector.