Chapter 9 Exercises: Arrays: Fixed Collections and Multidimensional Data

Chapter 9 Exercises: Arrays: Fixed Collections and Multidimensional Data

Part A: Comprehension and Short Answer

Exercise 9.1 — Explain why an array is described as a "homogeneous" data structure. Give an example of a situation where this property is a limitation.

Exercise 9.2 — Consider the following declaration:

var
  temps: array[1..365] of Real;

(a) How many elements does this array contain? (b) What is the index of the first element? The last? (c) What expression would you use to access the temperature on the 100th day of the year? (d) If each Real occupies 8 bytes, how much memory does this array use?

Exercise 9.3 — Explain the difference between var, const, and open array parameters when passing arrays to subprograms. When should each be used?

Exercise 9.4 — Why must we define a named type (e.g., TGradeArray = array[1..30] of Integer) rather than declaring the array structure inline in both the variable declaration and the subprogram parameter? What compile-time error occurs if we do not?

Exercise 9.5 — A student writes the following code:

var
  data: array of Integer;
begin
  data[0] := 42;
  WriteLn(data[0]);
end.

Explain why this code fails. What is missing?

Exercise 9.6 — Explain what "row-major order" means for a 2D array. Why does the order in which we iterate over a 2D array matter for performance?

Exercise 9.7 — Compare static arrays and dynamic arrays in Pascal across these dimensions: (a) when the size is determined, (b) how indexing works, (c) where memory is allocated, (d) initialization behavior.

Part B: Reading and Tracing Code

Exercise 9.8 — Trace the following code. What does it print?

var
  a: array[1..5] of Integer;
  i: Integer;
begin
  for i := 1 to 5 do
    a[i] := i * i;

  for i := 5 downto 1 do
    Write(a[i], ' ');
  WriteLn;
end.

Exercise 9.9 — Trace the following code. What values are in the array after execution?

var
  b: array[1..6] of Integer;
  i: Integer;
begin
  b[1] := 1;
  b[2] := 1;
  for i := 3 to 6 do
    b[i] := b[i-1] + b[i-2];
end.

Exercise 9.10 — Trace the following code step by step. What does it print?

var
  data: array[1..5] of Integer = (3, 1, 4, 1, 5);
  i, temp: Integer;
begin
  for i := 1 to 4 do
    if data[i] > data[i + 1] then
    begin
      temp := data[i];
      data[i] := data[i + 1];
      data[i + 1] := temp;
    end;

  for i := 1 to 5 do
    Write(data[i], ' ');
  WriteLn;
end.

What well-known algorithm is this a single pass of?

Exercise 9.11 — Trace the following 2D array code. What does the final WriteLn statement output?

var
  grid: array[1..3, 1..3] of Integer;
  r, c: Integer;
begin
  for r := 1 to 3 do
    for c := 1 to 3 do
      if r = c then
        grid[r, c] := 1
      else
        grid[r, c] := 0;

  WriteLn(grid[1,1], grid[2,2], grid[3,3], grid[1,2], grid[2,3]);
end.

What mathematical structure does this grid represent?

Exercise 9.12 — The following function is supposed to return the index of the minimum element. Find the bug.

function FindMinIndex(const arr: array of Integer): Integer;
var
  i, minIdx: Integer;
begin
  minIdx := 1;
  for i := 1 to High(arr) do
    if arr[i] < arr[minIdx] then
      minIdx := i;
  FindMinIndex := minIdx;
end;

Part C: Writing Code

Exercise 9.13 — Write a procedure InitializeArray that takes an open array of integers and a fill value, and sets every element to that value.

procedure InitializeArray(var arr: array of Integer; value: Integer);

Exercise 9.14 — Write a function CountOccurrences that takes an open array of integers and a target value, and returns the number of times the target appears in the array.

Exercise 9.15 — Write a function IsSorted that takes an open array of integers and returns True if the array is sorted in non-decreasing order, False otherwise.

Exercise 9.16 — Write a procedure PrintHistogram that takes an array of positive integers and displays a horizontal bar chart using asterisks. For example, if the array contains [3, 7, 2, 5], the output should be:

[1]: ***
[2]: *******
[3]: **
[4]: *****

Exercise 9.17 — Write a function DotProduct that takes two open arrays of Real of the same length and returns their dot product (the sum of the element-wise products). Include a check that the arrays have the same length.

Exercise 9.18 — Write a procedure RotateLeft that shifts all elements in an array one position to the left, with the first element wrapping around to the last position. For example, [1, 2, 3, 4, 5] becomes [2, 3, 4, 5, 1].

Exercise 9.19 — Write a procedure RemoveElement that removes the element at a given index from an array by shifting all subsequent elements left and decrementing the count. The procedure should work with parallel arrays or a single array — your choice.

procedure RemoveElement(var arr: TIntArray; var count: Integer; index: Integer);

Exercise 9.20 — Write a function MatrixSum that takes a 2D array of integers (up to 10x10) along with the actual number of rows and columns, and returns the sum of all elements.

Exercise 9.21 — Write a procedure TransposeMatrix that takes a square 2D array (up to 10x10) and transposes it in place (swaps rows and columns).

Part D: Problem Solving and Application

Exercise 9.22 — Frequency Counter. Write a program that reads up to 100 integers (each between 1 and 20) from the user, then displays how many times each value appeared. Use an array indexed [1..20] as a frequency table.

Exercise 9.23 — Running Average. Write a program that reads real numbers from the user one at a time and, after each input, displays the running average of all values entered so far. Use a dynamic array to store the values. Stop when the user enters 0.

Exercise 9.24 — Pascal's Triangle. Write a program that uses a 2D array to compute and display the first 12 rows of Pascal's Triangle. Recall that each element is the sum of the two elements above it: triangle[r, c] := triangle[r-1, c-1] + triangle[r-1, c].

Exercise 9.25 — Sieve of Eratosthenes. Write a program that uses a Boolean array isPrime: array[2..1000] of Boolean to find all prime numbers up to 1000 using the Sieve of Eratosthenes algorithm:

Initialize all entries to True.
Starting from 2, for each number still marked True, mark all its multiples as False.
Print all numbers still marked True.

Exercise 9.26 — Matrix Multiplication. Write a program that multiplies two 3x3 matrices of real numbers and displays the result. Recall that element [i,j] of the product is the dot product of row i of the first matrix and column j of the second matrix.

Exercise 9.27 — Grade Curve. Extend the GradeBook Pro example from Section 9.9. Write a procedure that applies a curve to all grades: find the highest grade, calculate the difference between it and 100, then add that difference to every grade. Display the original and curved grades side by side.

Exercise 9.28 — Merge Two Sorted Arrays. Write a function that takes two sorted arrays of integers and produces a new (dynamic) array containing all elements from both arrays in sorted order. Do not simply concatenate and sort — use the merge algorithm (walk through both arrays simultaneously, always taking the smaller element).

Part E: Challenge Problems

Exercise 9.29 — Conway's Game of Life (One Generation). Represent a 20x20 grid of cells, where each cell is alive or dead (use a Boolean 2D array). Write a procedure that computes the next generation according to these rules:

A live cell with 2 or 3 live neighbors survives.
A dead cell with exactly 3 live neighbors becomes alive.
All other cells die or stay dead.

Display the grid before and after one generation step. (Hint: you need a second grid to store the new state, then copy it back.)

Exercise 9.30 — Magic Square Checker. A magic square is an n x n grid of numbers where the sum of every row, every column, and both diagonals are the same. Write a program that reads a 4x4 grid of integers and determines whether it is a magic square.

Exercise 9.31 — Sparse Array Simulation. A sparse array is one where most elements are zero. Rather than storing all elements, store only the non-zero ones using three parallel arrays: rowIndex, colIndex, and value. Write procedures to: (a) Add a non-zero element to the sparse representation. (b) Retrieve the value at a given (row, col) position. (c) Print the full matrix (including zeros) from the sparse representation.

Test with a 10x10 matrix that has only 5 non-zero elements.

Part M: PennyWise Milestone

Exercise 9.M1 — Implement the full PennyWise array checkpoint as described in Section 9.10. Your program should:

Read up to 100 expenses (amount, month 1-12, category as string).
Store them in parallel arrays.
Calculate and display monthly totals.
Find and display the highest-spending month.
Calculate and display the total across all months.
Find and display the average expense amount.

Exercise 9.M2 — Extend PennyWise with a category summary. Using the expense data from 9.M1, create a procedure that:

Identifies all unique categories (store in a dynamic array of strings).
For each category, calculates the total spent and the number of expenses.
Displays the categories sorted by total amount (highest first).

Hint: Finding unique categories requires scanning the category array and checking whether each category has been seen before. This is a practical application of linear search.

Exercise 9.M3 — Add a monthly comparison feature to PennyWise. After calculating monthly totals, display a simple bar chart showing each month's spending as a row of # symbols, where each symbol represents $50 (or another appropriate scale). Indicate the highest month with a * marker.

Jan: ##          ($100.00)
Feb: ####        ($200.00)
Mar: ########  * ($400.00)  <-- highest
Apr: ###         ($150.00)
...