Chapter 3 - Basic Computation

Basic Computation

We can create arrays, store references, and access individual elements by index. But accessing elements one at a time with hardcoded indices is not much better than having separate variables!

Consider the temperature array from the previous section. We stored seven values, and now we want to print all of them. With individual variables, we would need seven separate Console.WriteLine calls. With an array, we can write a loop that handles all seven, or seven hundred, or seven thousand, with the same code.

Traversal

Traversal is the process of visiting each element of an array in sequence.

The standard way to traverse an array is with a while loop and an index variable:

int[] numbers = new int[5];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
numbers[3] = 40;
numbers[4] = 50;
 
int i = 0;
while (i < numbers.Length)
{
    Console.WriteLine(numbers[i]);
    i++;
}

Output:

10
20
30
40
50

The loop translation: “Create an integer variable called i and bind 0 to it. While i is less than numbers.Length, go to the location of numbers, shift by i integers, and return the value there. Display it, then add 1 to i.”

Three pieces make this work. The variable i starts at 0, the first valid index. The condition i < numbers.Length keeps the loop running as long as i is a valid index. And i++ at the end of the body advances to the next position.

The condition uses < and not <=. The last valid index in this array is 4, which is Length - 1. Using <= would cause the loop to attempt numbers[5] on the final iteration, shifting past the end of the array.

Iteration Tables

We can trace a traversal the same way we trace state: by recording what happens at each step.

For the loop above:

Iteration	i	i < numbers.Length	numbers[i]	Output
1	0	0 < 5 → true	10	10
2	1	1 < 5 → true	20	20
3	2	2 < 5 → true	30	30
4	3	3 < 5 → true	40	40
5	4	4 < 5 → true	50	50
exit	5	5 < 5 → false	—	—

The loop runs exactly Length times. The variable i takes every valid index exactly once, in order, and when i reaches Length, the condition fails and the loop ends without accessing the array.

Iteration tables are the primary tool for understanding what a loop does. When a loop produces unexpected results, building an iteration table reveals exactly where the behavior diverges from what you expected.

The Loop Variable as an Index

In Chapter 1, the loop variable was a counter: it counted how many times the body ran. Here it plays a second role. The variable i is also an index into the array, and each iteration, i tells us where to shift.

To see why this distinction matters, consider a loop where the variable counts but is not used as an index:

int count = 0;
int i = 0;
while (i < numbers.Length)
{
    count++;
    i++;
}

Here i drives the loop forward, but the body only uses it to control when to stop. Contrast that with our traversal, where i appears inside the brackets: numbers[i]. In traversal, the loop variable does double duty. It controls the iteration and selects the element.

Shorter Translations

In the previous section, we used the full shift language for every array access: “Go to the location of ar, shift by i integers, and return the value there.” Now that the mechanism is familiar, we can use shorter translations when the focus is on the logic of a loop rather than the mechanics of a single access.

Full Form	Short Form
”Go to the location of ar, shift by i integers, and return the value there"	"Read ar[i]"
"Go to the location of ar, shift by i integers, and store 5 there"	"Store 5 at index i of ar"
"Create an integer variable called x and bind the result of going to ar, shifting by i integers, and returning the value there"	"Read ar[i] and bind it to x”

The full form is always accurate. The short form is convenient. When we need to think carefully about reference semantics or off-by-one errors, we return to the full form. When the focus is on a loop’s overall logic, the short form keeps things readable.

---

Try it yourself.

Translate this loop to English, then predict the output:

int[] vals = new int[4];
vals[0] = 2;
vals[1] = 4;
vals[2] = 6;
vals[3] = 8;
 
int i = 0;
while (i < vals.Length)
{
    Console.WriteLine(vals[i] * 2);
    i++;
}

Write your answer before revealing ours.

Reveal answer

Loop translation: “Create an integer variable called i and bind 0 to it. While i is less than vals.Length, go to the location of vals, shift by i integers, return the value there, multiply it by 2, and display the result. Then add 1 to i.”

Output:

4
8
12
16

If your answer differed, note what you missed before continuing.

---

Backward Traversal

Sometimes we need to visit elements from last to first. The loop structure changes in three places: where i starts, what condition we check, and how we update i.

int i = numbers.Length - 1;
while (i >= 0)
{
    Console.WriteLine(numbers[i]);
    i--;
}

Output:

50
40
30
20
10

Translation: “Create an integer variable called i and bind the result of evaluating numbers.Length - 1 to it. While i is greater than or equal to 0, go to the location of numbers, shift by i integers, return the value there, and display it. Then subtract 1 from i.”

We start at Length - 1 because that is the last valid index. The condition i >= 0 keeps the loop running as long as i is a valid index, and i-- moves toward the start of the array.

Here is the iteration table:

Iteration	i	i >= 0	numbers[i]	Output
1	4	4 >= 0 → true	50	50
2	3	3 >= 0 → true	40	40
3	2	2 >= 0 → true	30	30
4	1	1 >= 0 → true	20	20
5	0	0 >= 0 → true	10	10
exit	-1	-1 >= 0 → false	—	—

Notice that i reaches -1 before the loop exits. The condition is checked before the body runs, so the array is never accessed at index -1.

---

Try it yourself.

Given this array:

int[] ar = new int[4];
ar[0] = 100;
ar[1] = 200;
ar[2] = 300;
ar[3] = 400;

1. Write a backward traversal that displays each element.
2. Build the iteration table for your loop.

Write your answers before revealing ours.

Reveal answer

int i = ar.Length - 1;
while (i >= 0)
{
    Console.WriteLine(ar[i]);
    i--;
}

Iteration	i	i >= 0	ar[i]	Output
1	3	3 >= 0 → true	400	400
2	2	2 >= 0 → true	300	300
3	1	1 >= 0 → true	200	200
4	0	0 >= 0 → true	100	100
exit	-1	-1 >= 0 → false	—	—

Output:

400
300
200
100

If your answers differed, check three things: does your loop start i at Length - 1? Does the condition use >= 0? Does the body decrement with i--?

---

Writing During Traversal

Traversal is not just for reading. We can modify elements as we visit them. Here is a loop that doubles every value in the array:

int i = 0;
while (i < numbers.Length)
{
    numbers[i] = numbers[i] * 2;
    i++;
}

The loop body does two things at each index. First, it reads: go to the location of numbers, shift by i integers, and return the value there. Then it writes: multiply that value by 2, go to the location of numbers, shift by i integers, and store the result there.

Let’s trace this with an array that starts as {10, 20, 30, 40, 50}:

Iteration	i	numbers[i] (before)	Calculation	numbers[i] (after)
1	0	10	10 * 2	20
2	1	20	20 * 2	40
3	2	30	30 * 2	60
4	3	40	40 * 2	80
5	4	50	50 * 2	100

After the loop, the array is {20, 40, 60, 80, 100}. The original values are gone, replaced by the new ones.

Write-Traversal and References

The doubling loop modified the array through the variable numbers. What happens when another variable refers to the same array?

int[] numbers = new int[3];
numbers[0] = 10;
numbers[1] = 20;
numbers[2] = 30;
 
int[] alias = numbers;
 
int i = 0;
while (i < numbers.Length)
{
    numbers[i] = numbers[i] * 2;
    i++;
}
 
Console.WriteLine(alias[0]); // Output: 20
Console.WriteLine(alias[1]); // Output: 40
Console.WriteLine(alias[2]); // Output: 60

The loop modified through numbers, but alias sees the new values because both variables refer to the same array object. Changes through one are visible through the other. This is reference semantics from the previous section, now visible during traversal.

Filling an Array with Computed Values

A common use of write-traversal is filling an array with values that depend on the index:

int[] squares = new int[5];
 
int i = 0;
while (i < squares.Length)
{
    squares[i] = i * i;
    i++;
}

After the loop, the array is {0, 1, 4, 9, 16}. Each element holds the square of its own index.

Translation of the body: “Go to the location of squares, shift by i integers, and store the value of i × i there. Then add 1 to i.”

Reading Values from the User

So far, every array has been populated with hardcoded values or computed from the index. Real programs usually get their data from somewhere else.

int[] grades = new int[5];
 
int i = 0;
while (i < grades.Length)
{
    string input = Console.ReadLine();
    grades[i] = int.Parse(input);
    i++;
}

Translation: “Create an integer variable called i and bind 0 to it. While i is less than grades.Length, read a line from the console, convert it to an integer, and store it at index i of grades. Then add 1 to i.”

The array must be created first with a fixed size, then filled one element at a time as the user provides input. We do not know the values at compile time, but we commit to the number of elements up front.

---

Try it yourself.

What does this array contain after the loop runs?

int[] countdown = new int[4];
 
int i = 0;
while (i < countdown.Length)
{
    countdown[i] = countdown.Length - i;
    i++;
}

Trace through the loop iteration by iteration.

Reveal answer

i	countdown.Length - i	countdown[i]
0	4 - 0 = 4	4
1	4 - 1 = 3	3
2	4 - 2 = 2	2
3	4 - 3 = 1	1

The array contains {4, 3, 2, 1}.

If your answer differed, trace through the loop one iteration at a time.

---

Swapping Two Elements

Swapping the values at two positions is a basic operation we will use repeatedly when we reach sorting. It requires a temporary variable.

Consider an array where ar[0] is 10 and ar[3] is 40. We want to swap them so that ar[0] becomes 40 and ar[3] becomes 10. The problem is that if we write ar[0] = ar[3]; first, the value 10 is overwritten before we can put it anywhere. We need to save it before overwriting.

int temp = ar[0];
ar[0] = ar[3];
ar[3] = temp;

Line 1: “Create an integer variable called temp and bind the result of going to ar, shifting by 0 integers, and returning the value there.”

Line 2: “Go to the location of ar, shift by 3 integers, and return the value there. Then go to the location of ar, shift by 0 integers, and store that value there.”

Line 3: “Go to the location of ar, shift by 3 integers, and store the value of temp there.”

State table (assuming ar starts as {10, 20, 30, 40, 50}):

after line	temp	ar[0]	ar[3]
1	10	10	40
2	10	40	40
3	10	40	10

After line 2, both ar[0] and ar[3] hold 40. The original value of ar[0] would be lost if we had not saved it in temp on line 1. Line 3 completes the swap by placing the saved value into ar[3].

The pattern works the same way with variable indices:

int temp = ar[i];
ar[i] = ar[j];
ar[j] = temp;

We will use this form when we reach sorting, where the positions to swap are determined during each iteration of a loop.

---

Try it yourself.

Write code to swap the elements at index 2 and index 4 of an array named data. Include a temporary variable.

Write your code, then check it below.

Reveal answer

int temp = data[2];
data[2] = data[4];
data[4] = temp;

---

Counting with a Condition

Sometimes we need to know how many elements satisfy a particular condition. This combines traversal with an if statement and a counter variable.

int[] values = new int[7];
values[0] = -3;
values[1] = 5;
values[2] = 0;
values[3] = -8;
values[4] = 12;
values[5] = -7;
values[6] = 9;
 
int count = 0;
int i = 0;
while (i < values.Length)
{
    if (values[i] > 0)
    {
        count++;
    }
    i++;
}
 
Console.WriteLine(count); // Output: 3

Translation: “Create an integer variable called count and bind 0 to it. For each index, go to the location of values, shift by i integers, and return the value there. If it is greater than 0, add 1 to count.”

The iteration table tracks the condition and the running count:

Iteration	i	values[i]	values[i] > 0	count (after)
1	0	-3	false	0
2	1	5	true	1
3	2	0	false	1
4	3	-8	false	1
5	4	12	true	2
6	5	-7	false	2
7	6	9	true	3

Three elements are positive: 5, 12, and 9. The counter only increments when the condition is true.

Summing All Elements

Summing follows the same shape as counting. Instead of incrementing by 1 when a condition is met, we add each element’s value to a running total.

int sum = 0;
int i = 0;
while (i < values.Length)
{
    sum += values[i];
    i++;
}
 
Console.WriteLine(sum); // Output: 8

Iteration table:

Iteration	i	values[i]	sum (before)	Calculation	sum (after)
1	0	-3	0	0 + (-3)	-3
2	1	5	-3	-3 + 5	2
3	2	0	2	2 + 0	2
4	3	-8	2	2 + (-8)	-6
5	4	12	-6	-6 + 12	6
6	5	-7	6	6 + (-7)	-1
7	6	9	-1	-1 + 9	8

Both summing and counting start with an initial value of 0, visit every element, and update a running result along the way. This shared shape is a pattern we will name and explore further in the next section.

---

Try it yourself.

Given this array:

int[] scores = new int[5];
scores[0] = 80;
scores[1] = 95;
scores[2] = 72;
scores[3] = 88;
scores[4] = 65;

1. Write code that counts how many scores are 80 or above.
2. Write code that computes the sum of all scores.
3. Build an iteration table for your counting code.

Write your answers before revealing ours.

Reveal answer

Counting:

int count = 0;
int i = 0;
while (i < scores.Length)
{
    if (scores[i] >= 80)
    {
        count++;
    }
    i++;
}
// count is 3  (80, 95, 88)

Summing:

int sum = 0;
int i = 0;
while (i < scores.Length)
{
    sum += scores[i];
    i++;
}
// sum is 400

Iteration table for counting:

Iteration	i	scores[i]	scores[i] >= 80	count (after)
1	0	80	true	1
2	1	95	true	2
3	2	72	false	2
4	3	88	true	3
5	4	65	false	3

If your answers differed, note what you missed before continuing.

---

Off-by-One Errors

The most common bug when working with arrays is the off-by-one error: the loop visits one index too many or one too few. These bugs come in two forms.

Going past the end:

int i = 0;
while (i <= numbers.Length)
{
    Console.WriteLine(numbers[i]);
    i++;
}

The condition uses <= instead of <. On the final iteration, i equals numbers.Length. For an array of size 5, that means i is 5, and there is no element at index 5. The shift goes past the end of the array, and the program crashes with an IndexOutOfRangeException.

Skipping the first element:

int i = 1;
while (i < numbers.Length)
{
    Console.WriteLine(numbers[i]);
    i++;
}

The loop starts i at 1 instead of 0, so index 0 is never visited and the first element is silently skipped. The program does not crash, which makes this bug harder to spot. Everything looks correct, but the output is missing a value.

The iteration table is the best tool for catching both of these. If you trace a loop and find that i takes a value outside the valid range, or that a valid index is never reached, you have found the bug.

Three checks that prevent most off-by-one errors:

• Forward loops start i at 0
• Forward conditions use < (not <=) when comparing to Length
• Backward loops start i at Length - 1 and continue while i >= 0

Out-of-Bounds Errors in Context

Off-by-one errors are one source of out-of-bounds access, but they can also arise from computed indices.

int[] data = new int[5];
int position = 7;
data[position] = 10; // IndexOutOfRangeException

The variable position holds 7, but valid indices for data are 0 through 4. The shift goes past the end of the array.

Whenever an index comes from a variable or a calculation rather than a literal number, the program cannot guarantee at compile time that the index is valid. The error only appears when the code runs with certain values, which makes these bugs particularly frustrating: the code compiles without complaint but crashes on certain inputs.

---

Try it yourself.

Each loop below has a bug. Identify the problem and write the corrected version.

Bug 1:

int[] ar = new int[4];
int i = 0;
while (i <= ar.Length)
{
    ar[i] = i * 2;
    i++;
}

Bug 2:

int[] ar = new int[4];
int i = 1;
while (i < ar.Length)
{
    Console.WriteLine(ar[i]);
    i++;
}

Bug 3:

int[] ar = new int[4];
int i = ar.Length;
while (i >= 0)
{
    Console.WriteLine(ar[i]);
    i--;
}

Identify each bug before checking.

Reveal answer

Bug 1: The condition i <= ar.Length should be i < ar.Length. When i equals 4, ar[4] is out of bounds for a 4-element array.

while (i < ar.Length)

Bug 2: The loop starts i at 1, skipping index 0. The first element is never printed.

int i = 0;

Bug 3: The loop starts i at ar.Length, which is 4. But the last valid index is 3. The first access ar[4] is out of bounds.

int i = ar.Length - 1;

If anything tripped you up, trace through each original loop with an iteration table to see where the bug occurs.

---

Putting It Together

A teacher records quiz scores for a class. Before computing the final total, she wants to drop any scores below a passing threshold by replacing them with zero. Then she needs to know how many students passed and what the total of all remaining scores is.

This requires three traversals after the setup: replace the failing scores with zero, count how many passed, and sum the results.

int[] scores = new int[6];
scores[0] = 55;
scores[1] = 82;
scores[2] = 41;
scores[3] = 90;
scores[4] = 73;
scores[5] = 68;
 
// Replace any score below 60 with 0
int i = 0;
while (i < scores.Length)
{
    if (scores[i] < 60)
    {
        scores[i] = 0;
    }
    i++;
}
// scores is now {0, 82, 0, 90, 73, 68}
 
// Count passing scores
int passing = 0;
i = 0;
while (i < scores.Length)
{
    if (scores[i] != 0)
    {
        passing++;
    }
    i++;
}
// passing is 4
 
// Sum all scores
int total = 0;
i = 0;
while (i < scores.Length)
{
    total += scores[i];
    i++;
}
// total is 313

Three loops, each doing one job: replacing, counting, and summing. Notice that i is reused across the loops by resetting it to 0 before each traversal.

---

Try it yourself.

Translate the first loop (the one that replaces scores below 60 with 0) to English, and build its iteration table.

Write your answers before checking.

Reveal answer

Translation: “Create an integer variable called i and bind 0 to it. While i is less than scores.Length, go to the location of scores, shift by i integers, and return the value there. If it is less than 60, store 0 at index i of scores. Then add 1 to i.”

Iteration table (starting with scores as {55, 82, 41, 90, 73, 68}):

Iteration	i	scores[i] (before)	scores[i] < 60	scores[i] (after)
1	0	55	true	0
2	1	82	false	82
3	2	41	true	0
4	3	90	false	90
5	4	73	false	73
6	5	68	false	68

If your answer differed, note what you missed before continuing.

---

Review

Before continuing, test yourself on what you have learned. Use the protocol from Chapter 0: attempt each exercise from memory, then check, then note what you missed.

Part 1: Definitions

Write the definition from memory, then find it in the chapter to check.

1. What is traversal?

If your answer differed, note what you missed and write the corrected version.

Part 2: Translations

Translate each loop to English using shift language.

1. A forward traversal that prints every element of an integer array named ar.
2. A backward traversal that prints every element of ar.
3. A loop that stores the value i * 3 at each index of ar.

Check against the translation patterns in this section.

Part 3: Iteration Tables

Build a complete iteration table for this code:

int[] ar = new int[5];
ar[0] = 3;
ar[1] = 7;
ar[2] = 1;
ar[3] = 9;
ar[4] = 4;
 
int sum = 0;
int i = 0;
while (i < ar.Length)
{
    if (ar[i] > 3)
    {
        sum += ar[i];
    }
    i++;
}

Your table should include columns for i, ar[i], the condition result, and sum after each iteration.

What is the final value of sum?

Part 4: Writing Code

Write C# code for each description.

1. Create an integer array of size 6 and store a reference to it in data. Fill it so that each element holds its index times 10.
2. Traverse data backward and display each element.
3. Swap the elements at index 1 and index 4 of data.
4. Count how many elements of data are greater than 30.
5. Compute the sum of all elements in data.

Check your code against the examples in this section.

Part 5: Bug Identification

Each loop has a bug. Identify the problem and write the corrected version.

int[] ar = new int[5];
int sum = 0;
int i = 0;
while (i <= ar.Length)
{
    sum += ar[i];
    i++;
}

int[] ar = new int[5];
int i = ar.Length;
while (i > 0)
{
    Console.WriteLine(ar[i]);
    i--;
}

int[] ar = new int[5];
int count = 0;
int i = 1;
while (i < ar.Length)
{
    if (ar[i] > 0)
    {
        count++;
    }
    i++;
}

For each, trace the loop with an iteration table to confirm your fix.

Part 6: Complete Program

Write a program that creates an integer array of size 8, fills it with the values 1 through 8, then replaces every even-indexed element with 0. After the replacement, compute and display the sum of the remaining nonzero elements.

Trace through your program with a state table to verify it produces the correct result.