Q1 - Q4 are related to the ADT material. In the lecture, we talked about "outside the black box" and "inside the black box". The related discussion question will give you some practice with working "outside the black box". The assignment is intended to help you think about "inside the black box", by having you look at alternative representations. In Q1, you look at an alternative to binary. In Q2, you look at where stuff might be stored as a consequence of a selected implementation. In Q3 and Q4, you look at an alternative data structures to leverage the fact that many locations in a standard array might always be empty. In Q6 and Q7 you look at how the time is affected by the underlying cost of the algorithm.

Q3 A lower triangular matrix is an nxn array in which has a[i][j] = = 0 if i

Q4 A tridiagonal matrix is an nxn array in which has a[i][j] = = 0 if |i-j| > 1. What is the maximum number of non zero elements? How can they be stored in memory sequentially? Find a formula k= f(i,j) to store location a[i][j] in k, when |i-j| <=1 (you only want to store the nonzero elements). Do not write code. Code would work if you were manually converting the matrix from one form to the other all at once, but you need the formula to convert otherwise.