Section 10.1.1: Arrays

How do most programming languages store arrays in memory?
Most programming languages store arrays in memory as a contiguous sequence of bytes where each element is the same size.

What does storing equally sized elements in a contiguous sequence of bytes in memory allow?
Storing equally sized elements in a contiguous sequence of bytes in memory allows access time to the -th element.

Section 10.1.2: Matrices

What is a matrix?
A matrix is a two-dimensional array or table.

How can a matrix be represented?
A matrix can be represented by one or more one-dimensional arrays.

What are the three most common ways to store a matrix?
The three most common ways to store a matrix are:

  1. Row-major.
  2. Column-major.
  3. Multiple one-dimensional arrays.

How is a matrix stored using row-major order?
A matrix is stored using row-major order by storing row after row in a one-dimensional array.

How is a matrix stored using column-major order?
A matrix is stored using column-major order by storing column after column in a one-dimensional array.

How is a matrix stored using an array of arrays?
A matrix is stored using an array of arrays by storing each row or column as a separate array with another array of pointers to connect them together.

What is an example of storing a matrix using row-major order, column-major order, and multiple one-dimensional arrays?
An example of storing a matrix using row-major order, column-major order, and multiple one-dimensional arrays is:
Row-Major, Column-Major, and Multiple One-Dimensional Arrays.png

What is an example of creating a two-dimensional array as an array of arrays in Java?
An example of creating a two-dimensional array as an array of arrays in Java is:

Color[] matrix = new Color[3][];
for (int i = 0; i < matrix.length; i++)
	matrix[i] = new Color[5];
	

for (int i = 0; i < matrix.length; i++)
	for (int j = 0; j < matrix[i].length; j++)
		matrix[i][j] = new Color[i][j] = new Color(i+j, i+j, i+j);

Section 10.1.3 Stacks and Queues

What is the representation of a stack as an array?
The representation of a stack as an array is , where and represents the number of elements in the stack.

What is the other attribute that an array representing a stack has and what is it for?
The other attribute that an array representing a stack has is , which is for pointing to the array index of the most recently inserted element.

What is initially set to?
is initially set to 0.

What are the three operations you can perform on a stack?
The three operations you can perform on a stack are:

  1. Push - Add an element to the stack.
  2. Pop - Remove an element from the stack.
  3. Empty - Check if the stack is empty by looking at .

What is the pseudocode for the Stack-Empty procedure?
The pseudocode for the Stack-Empty procedure is:

Stack-Empty(S)
	if S.top = 0
		return true
	else
		return false

What is the pseudocode for the Push procedure?
The pseudocode for the Push procedure is:

Push(S, x)
	if (S.top + 1 == S.size)
		error "Overflow"
	else
		S.top = S.top + 1
		S[S.top] = x

What is the pseudocode for the Pop procedure?
The pseudocode for the Pop procedure is:

Pop(S)
	if Stack-Empty(S)
		error "Underflow"
	else
		S.top = S.top - 1
		return S[s.top + 1]

What is an example of an array representation of a stack?
An example of an array representation of a stack is:
Array Representation of a Stack.png

What is the worst-case running time for each stack operation?
The worst-case running time for each stack operation is .