CS U111 · Lecture 8 · Notes — the compressed map

Arrays, in one page

The patterns from Lecture 8 as cards, three worked examples at evaluation level, and the traps that cost marks. This is the revision version. Seeing arrays for the first time? Read the lesson first, then come back. For hands-on practice, use the arrays ladder.

Start here · what's in scope, and what isn't here yet

Scope: Lecture 8, Arrays in C. Reading: Hanly & Koffman ch. 7. Lab sheet: Lab 6, which hasn't reached us yet, so this page is built from the lecture deck. When the sheet arrives, its problems get a worked page of their own. Lecture 8 relies only on Lab 4 (loops, nested loops, break, flags) and Lab 3 (if … else if). There's nothing else to catch up on first.

Arrays are new to everyone in the batch. Nobody came in knowing them. Lab evaluations are open book and unannounced, and count as best k of n for 10% of the course, so keeping this page open during one is what the format allows. Not covered yet: passing arrays to functions (after pointers), strings, and "deeper sorting" (a later lecture, per the deck).

The whole thing in one idea

An array is one name for a row of boxes of the same type, numbered from 0. The number in the brackets can be a variable, so a[i] inside a loop visits every box. Everything else on this page is a loop body.

Valid indices run from 0 to size − 1. C doesn't check, so marks[5] compiles and reads someone else's memory.

Declaration	What you get
`int marks[5];`	5 boxes of garbage. Fill them before reading.
`int marks[5] = {72, 85, 91, 68, 77};`	All five set
`int numbers[] = {10, 20, 30, 40};`	Size counted for you: 4
`int part[5] = {1, 2};`	`1 2 0 0 0`: missing values become 0 (tested)
`int zeros[100] = {0};`	All 100 are 0
`int numbers[];`	Error: "needs an explicit size or an initializer"
`int size = sizeof(a) / sizeof(a[0]);`	The element count (20 ÷ 4 = 5), but only where `a` is declared

The pattern cookbook

Thirteen shapes cover all of Lecture 8. Each one is Lab 4's traversal loop with a different body.

1 · Traverse: the four lines everything uses

"print all" · "for each element"

for (int i = 0; i < size; i++) { … a[i] … }

<, never <=. From 0 with i < size, the loop runs exactly size times and stops at the last index.

2 · Sum and average

"total" · "mean" · "average"

int sum = 0;
for (int i = 0; i < n; i++) sum += a[i];
double avg = (double) sum / n;       // cast BEFORE dividing

Add up a[i], not i. Tested on the lecture's marks: sum = 393 and average = 78.60. Without the cast you get 78.00.

3 · Minimum / maximum (value or index)

"smallest" · "largest" · "topper" · "position of the lowest"

int minVal = a[0];                           // seed with a real element
for (int i = 1; i < n; i++) if (a[i] < minVal) minVal = a[i];

int minIdx = 0;                              // index version
for (int i = 1; i < n; i++) if (a[i] < a[minIdx]) minIdx = i;

For the maximum, flip < to >. The index version is the inner loop of selection sort (card 10).

4 · Count the matches

"how many …" · "how many scored exactly 90"

int count = 0;
for (int i = 0; i < n; i++) if (a[i] == 90) count++;

No break: to count, you have to look at every box.

5 · Linear search

"is x in the array?" · "at which index?"

int foundIndex = -1;                         // -1 = not found; never a real index
for (int i = 0; i < n; i++)
    if (a[i] == target) { foundIndex = i; break; }

Works on any array, sorted or not. break gives you the first match. Check foundIndex == -1 before using the result.

6 · Binary search (sorted arrays only)

"sorted array" · "efficiently" · "halve"

int left = 0, right = n - 1, foundIndex = -1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (a[mid] == target)     { foundIndex = mid; break; }
    else if (a[mid] < target) left = mid + 1;
    else                      right = mid - 1;
}

"Not found" is when left passes right. The ±1s make that happen. Leave them out and the loop can run forever.

Unpack this step — why about 10 steps for 1000 elements

Each step halves the range: 1000 → 500 → 250 → … → 1 takes about 10 halvings, because 2¹⁰ = 1024. Linear search could take all 1000. Powers of two are in the prerequisite kit.

7 · Tally array (frequency count)

"grade distribution" · "how many in each category"

int counts[5] = {0};                         // one counter per category
for (int i = 0; i < n; i++) {
    if (a[i] >= 90) counts[0]++; else if (a[i] >= 80) counts[1]++; …
}

Lecture's marks → A=1 B=1 C=2 D=1 F=0 (tested). The tallies need {0} for the same reason a sum needs = 0.

8 · Swap two boxes

inside every sort

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

Three lines and a spare variable. Two lines copy one value over the other: {3, 9} becomes 9 9 (tested).

9 · Bubble sort (with the early-exit flag)

"sort by comparing adjacent elements"

for (int pass = 0; pass < n - 1; pass++) {
    bool swapped = false;                    // #include <stdbool.h>
    for (int i = 0; i < n - 1 - pass; i++)
        if (a[i] > a[i+1]) { swap a[i], a[i+1]; swapped = true; }
    if (!swapped) break;                     // clean pass → sorted
}

Each pass moves the largest remaining value to the end, so the inner limit shrinks by one each pass (- pass). The lecture's version has no flag. On {72,85,91,68,77} both versions run 4 passes (10 comparisons, 5 swaps, tested). On already-sorted input, the flag version stops after 1 pass and 4 comparisons.

10 · Selection sort

"find the smallest, put it first, repeat"

for (int i = 0; i < n - 1; i++) {
    int minIdx = i;
    for (int j = i + 1; j < n; j++) if (a[j] < a[minIdx]) minIdx = j;
    swap a[i], a[minIdx];
}

This is card 3's index version, run on a part that shrinks each pass. The swap runs once per pass, 4 times for 5 elements, and the last one may swap a box with itself (it does on the lecture's marks: the data changes only 3 times).

11 · Traverse a 2D grid

"matrix" · "table" · "rows and columns"

int g[2][3] = {{1, 2, 3}, {4, 5, 6}};
for (int r = 0; r < 2; r++) {
    for (int c = 0; c < 3; c++) printf("%d ", g[r][c]);
    printf("\n");
}

Row first, always: g[row][col]. The outer loop picks a row and the inner loop walks across it. Same shape as Lab 4's pattern 10.

int grid[3][4]: 3 rows × 4 columns = 12 ints. The first index goes down, the second goes across.

12 · Matrix addition and transpose

"add two matrices" · "transpose"

C[i][j] = A[i][j] + B[i][j];     // same position in, same position out
T[j][i] = A[i][j];               // indices swapped; T is cols × rows

Both go inside the card-11 double loop over A's rows and columns. The transpose of a 2×3 matrix is 3×2, so declare T[3][2].

13 · Matrix multiplication: recognise the shape

"multiply" · the lecture shows it but doesn't trace it

R[i][j] = 0;
for (int k = 0; k < n; k++) R[i][j] += A[i][k] * B[k][j];   // inside loops over i, j

Three nested loops. A (m×n) × B (n×p) = m×p, and the middle numbers must match. Tested: [[1,2],[3,4]] × [[5,6],[7,8]] = [[19,22],[43,50]]. N-D arrays (int cube[2][3][4], 24 ints) just add one loop per dimension.

Three worked examples at evaluation level

Worked example 1

The lecture's "Class Statistics" activity, solved in full

Given int scores[8] = {55, 90, 72, 90, 61, 45, 90, 78}; (1) find the sum, average, minimum and maximum; (2) use linear search to find whether 61 appears, and at what index; (3) count how many scored exactly 90, and say what that shows about search vs. traversal; (4) sort the array.

Get the size without typing 8. int n = sizeof(scores) / sizeof(scores[0]); gives 32 ÷ 4 = 8. From here on every loop says n.

Part 1: one traversal for the sum, and min/max seeded with scores[0].

int sum = 0, minVal = scores[0], maxVal = scores[0];
for (int i = 0; i < n; i++) sum += scores[i];
for (int i = 1; i < n; i++) {
    if (scores[i] < minVal) minVal = scores[i];
    if (scores[i] > maxVal) maxVal = scores[i];
}
printf("sum = %d, average = %.3f, min = %d, max = %d\n", sum, (double) sum / n, minVal, maxVal);

Check the sum by hand, in pairs: (55+90) + (72+90) + (61+45) + (90+78) = 145 + 162 + 106 + 168 = 581. Average 581 ÷ 8 = 72.625. The smallest is 45 and the largest is 90.

Part 2: linear search for 61. Card 5 with target = 61. Checking boxes 0–3 gives 55, 90, 72, 90: no match. Box 4 is 61, a match, so break. Answer: index 4.
Part 3: count the 90s. Card 4, with no break. The 90s are at indices 1, 3 and 6, so 3. The point of the question: a search can stop at the first 90 (index 1), but a count has to visit all 8 boxes. "Is it there?" can stop early. "How many?" can't.

Part 4: selection sort, one pass at a time (each row is from the compiled program):

pass i	minIdx	array after the swap
0	5 (45)	45 90 72 90 61 55 90 78
1	5 (55)	45 55 72 90 61 90 90 78
2	4 (61)	45 55 61 90 72 90 90 78
3	4 (72)	45 55 61 72 90 90 90 78
4	7 (78)	45 55 61 72 78 90 90 90
5	5 (itself)	45 55 61 72 78 90 90 90
6	6 (itself)	45 55 61 72 78 90 90 90

Sorted: 45 55 61 72 78 90 90 90. Notice pass 1: the minimum of the unsorted part (index 1 onward) is the 55 that pass 0's swap moved to index 5.

sum = 581, average = 72.625, min = 45, max = 90
61 found at index 4
scored exactly 90: 3
sorted: 45 55 61 72 78 90 90 90

Worked example 2

Binary search by hand: one hit, one miss

On the sorted array from Example 1, {45, 55, 61, 72, 78, 90, 90, 90}, trace binary search for 61, then for 80. Show left, right and mid at every step.

Check it's sorted. It is, so binary search is valid. (On unsorted data it gives wrong answers. See the traps.)
Start with the whole array: left = 0, right = n − 1 = 7.
Target 61. Each row works out mid = left + (right − left)/2 with integer division:

step left, right mid a[mid] decision

1 0, 7 3 72 72 > 61 → right = 2

2 0, 2 1 55 55 < 61 → left = 2

3 2, 2 2 61 match → index 2

Step 1: 0 + (7 − 0)/2 = 0 + 3 = 3. The 3.5 is cut down to 3, the integer division from Lab 4.
Target 80.

step left, right mid a[mid] decision

1 0, 7 3 72 72 < 80 → left = 4

2 4, 7 5 90 90 > 80 → right = 4

3 4, 4 4 78 78 < 80 → left = 5

— 5, 4 — — left > right → not found, −1
Sanity-check the miss. 80 would sit between 78 (index 4) and 90 (index 5), and that's exactly where left and right ended up crossing. When a search fails, the crossing point shows where the value would go.

step	left, right	mid	a[mid]	decision
1	0, 7	3	72	72 > 61 → right = 2
2	0, 2	1	55	55 < 61 → left = 2
3	2, 2	2	61	match → index 2

step	left, right	mid	a[mid]	decision
1	0, 7	3	72	72 < 80 → left = 4
2	4, 7	5	90	90 > 80 → right = 4
3	4, 4	4	78	78 < 80 → left = 5
—	5, 4	—	—	left > right → not found, −1

Unpack this step — why left + (right − left)/2 equals (left + right)/2

l + (r − l)/2 = (2l + r − l)/2 = (l + r)/2. The lecture uses the first form only because left + right can overflow on huge arrays. Either one gets full marks at this level.

Worked example 3

Add two 2×3 matrices and transpose one

With A = {{1,2,3},{4,5,6}} and B = {{10,20,30},{40,50,60}}, compute C = A + B and T, the transpose of A. Print both.

Get the shapes right before any loop. A and B are 2×3, so C is 2×3. T swaps rows and columns, so it's 3×2: int C[2][3], T[3][2];

One double loop over A covers both:

for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++) {
        C[i][j] = A[i][j] + B[i][j];
        T[j][i] = A[i][j];
    }

Spot-check two cells by hand. C[1][2] = A[1][2] + B[1][2] = 6 + 60 = 66. A[0][1] = 2 goes to T[1][0], which is row 1, column 0 of T.
Print each result with its own limits. T has 3 rows of 2, so loop i < 3, j < 2. Reusing C's limits (2 and 3) would read past the end of each row of T.

A+B:
11 22 33 
44 55 66 
transpose:
1 4 
2 5 
3 6

Classic traps — the standard ways marks are lost

The mistake	What you see	The fix
`i <= size` in a traversal	One extra, junk element. Tested: `sum = 394` instead of 393, with no warning. Sometimes a crash.	`i < size`. The last valid index is size − 1. Going past the end is undefined behaviour: it can give junk or crash.
Integer-division average: `sum / n`	`78.00` instead of `78.60`	`(double) sum / n`. Cast before dividing, not `(double)(sum / n)`.
Min seeded with 0 (or max with 0 on negative data)	Minimum reported as 0, a value that isn't in the array	Seed with `a[0]` and start the loop at 1.
Binary search on unsorted data	"Not found" for a value that's there. Tested: 68 in `{72,85,91,68,77}` → −1.	Sort first, or use linear search.
Swap without `temp`	Both boxes hold the same value (`9 9`)	Three lines: save, overwrite, restore.
Row and column swapped: `g[c][r]`	Transposed output, or reading past the end of a row	Always `[row][col]`. Name the loop variables `r` and `c` so the mistake is easy to see.
`sizeof(a)/sizeof(a[0])` inside a function that received `a`	Tested: `2` instead of 5. clang warns "sizeof on array function parameter…"	Use it only where the array is declared. Pass the size as its own parameter (coming after pointers).
`int a[];` with no size and no values	Compile error: "needs an explicit size or an initializer"	Give the size, or give the values and let C count.
Accumulator or tally not zeroed: `int counts[5];`	Huge random counts	`int counts[5] = {0};`
Search result used without checking	`a[foundIndex]` with `foundIndex = -1` reads outside the array	`if (foundIndex == -1) { … not found … }` first.

Two trace details the lecture slides skip over

"Sorted after 3 passes" is true of the data, but the lecture's bubble loop pass < 4 still runs pass 4 (1 comparison, no swap). Selection sort's "exactly one swap per pass" includes a swap of box 3 with itself on the last pass, so the code performs 4 swaps while the data changes 3 times. If a trace question asks "how many swaps does the code perform?", count the ones the code executes.

Minimal prerequisite kit

Everything this lecture takes from school or from earlier labs. Nothing else is assumed.

Fact	Where it's used
`for (i = a; i < b; i++)` runs b − a times (Lab 4)	Why `i < size` visits exactly every box
int ÷ int drops the fraction (Lab 4)	The average cast; `mid` in binary search (7/2 = 3)
Powers of 2: 2¹⁰ = 1024	Binary search needs about 10 steps for 1000 elements
A byte; an `int` is 4 bytes on your machines (Lecture 4)	The `sizeof` trick: 20 ÷ 4 = 5
Nested loops: the inner loop runs completely for each outer pass (Lab 4)	Both sorts, every 2D loop
A flag: assume, then disprove (Lab 4, pattern 5)	Bubble sort's `swapped` early exit
Matrix = rows × columns; row·column products (school, if met)	Only the "recognise it" glimpse of multiplication

What to practise

Ranked for a short evening. Once the Lab 6 sheet arrives, its problems come first, because evaluations are drawn from it.

Skill	Drill it on	Textbook backup Hanly ch. 7	How many
Traversal, sum, min/max	Arrays ladder, first rungs	Self-checks for "Declaring and referencing arrays", "Array subscripts", "Using for loops for sequential access"	odd-numbered · 15 min
Predicting output	Predict-the-output drill (array families)	The same self-checks: trace them on paper before checking	1 sheet · 10 min
Linear and binary search	Worked examples 1–2 above, then invent a target of your own	"Searching and sorting an array"	2 traces · 10 min
Sorting by hand	The lesson's sort stepper: predict each step before clicking	"Searching and sorting an array": selection sort	1 array · 10 min
Write a sort from memory	Card 9 or 10, typed blind, then run on Example 1's scores	End-of-chapter programming exercises on sorting	1 · 15 min
2D arrays	Worked example 3, then transpose a 3×3	Self-checks for "Multidimensional arrays"	odd-numbered · 15 min

Section titles instead of numbers, because editions renumber. In the 8th edition they should be §7.1–7.3, §7.6 and §7.8, but check your copy. Hanly's searching-and-sorting section teaches linear search and selection sort. Bubble sort and binary search come from the lecture, and the lecture is what you're examined on. Array arguments to functions (§7.4–7.5) are deferred until after pointers, so skip them for now. If the instructor names specific sections, go with those.

Don't do this tonight

Don't start merge sort, quicksort, or "top 50 array interview questions". The deck says deeper sorting comes in a later lecture, and none of it is in Lecture 8. Don't go down the pointer-arithmetic path either: that's Block I. Four traces done properly with the cards above are worth more than forty problems skimmed. And type the sorts yourself: lab evaluations test your hands, not an AI's.