University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page
Course Page

CSC 477/677 Assignment 8

Due date: Wednesday, November 6, 2013, 2:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on or before the due date.

  1. A is a 7×8×6 array, stored in row major order in RAM, where each entry of A is stored in two memory locations. The indices start at 0, that is, A[i,j,k] is defined if i is in 0..6, j is in 0..7, and k is in 0..5. The base address of A is 1000. What is the base adress of A[5,3,4]?

  2. X is a two-dimensional array with n rows, whose indices are 0 .. n-1. whose first row has length 1, and whose ith row is twice as long as the previous row for each i > 1. That is, the column indices that are possible in the ith row are 0 .. 2i-1.
    Notice that X is a sparse array. To store X efficiently, you will create an array A such that A[t] is the tth entry of X.
    That is, A[1] = X[0,0], A[2] = X[1,0], A[3] = X[1,1], A[4] = X[2,0], and so forth.
    In order to execute fetch and store for X, you will use a "helper" array B, which will have the property that
    X[i,j] = A[B[i]+j].

    Thus, the statement:
    X[3,5] = X[2,2]+X[2,3]
    Would actually be executed as:
    A[B[3]+5] = A[B[2]+2]+A[B[2]+3]

    1. Find i and j such that X[i,j] = A[113].
    2. What is the value of B[3]?
    3. What is the value of B[5]?


Back to Course Page