Implement algorithms with lists

List or trace

\(\displaystyle L=[4,-2,4,0,7]\)

A list records five temperature changes in order. Positions start at 1. What value is at position 2?

In L = [4, −2, 4, 0, 7], two entries are both 4. Does the list store both occurrences?

Use L = [4, −2, 4, 0, 7]. Build a count of entries at least 4 using the condition and action controls. Initialisation is fixed before the loop. Read the pseudocode and trace. Then change the action to sum, and finally append. Compare the outputs

For the full list, which outputs should those three implementations give?

A list holds related values

A variable can hold one running total. A list holds an ordered collection of entries. We use positions 1, 2, 3, … here; some programming languages start at 0. Always state the convention. The assignment arrow means evaluate the right side, then store the result on the left

1. 1One position at a time An indexed assignment replaces the named entry and preserves the others

List or trace

\(\displaystyle -2+5\)

For L = [4, −2, 4, 0, 7], execute L[2] ← L[2] + 5. What is the new second entry?

Start with L = [4, −2, 4, 0, 7] and assign L[2] ← L[2] + 5. What happens to the first and third entries?

List or trace

\(\displaystyle [4,-2,4,0,7]\)

Start total at 0. Visit each entry of [4, −2, 4, 0, 7]. Add 1 whenever x ≥ 4. What is the final total?

Which update counts passing entries rather than summing their values?

List or trace

\(\displaystyle [4,-2,4,0,7]\)

A sum algorithm starts total at 0 and adds x only if x ≥ 4. After visiting 4, −2 and 4, what is total?

Filtering appends each passing entry to an initially empty list. Which order should [7, 4, 7, −2] produce when keeping entries at least 4?

The specification says “at least 4”. Which condition implements it?

Use L = [4, −2, 4, 0, 7] and the fixed threshold 4. Compare strict > with ≥. Then use zero entries and try count, sum and append. Read what happens with an empty input; initialisation stays outside the loop

Which statement matches these boundary tests?

List or trace

\(\displaystyle L=[]\)

For a count, total starts at 0. If L is empty, how many times does the FOR EACH loop run?

Why should the running total normally be initialised before an accumulation loop?

This program sums every entry of L = [4, −2, 4, 0, 7], starting at 0. Compare no inside reset with resetting each time. Trace where earlier work disappears. Restore no reset, then test an empty list

What does resetting before every addition do for the full list?

A maximum algorithm starts best at 0, then replaces it only with a larger list entry. Why does [−4, −2, −7] expose a bug?

List or trace

\(\displaystyle [-4,-2,-7]\)

For the non-empty list [−4, −2, −7], initialise best at the first entry and compare each remaining entry. What maximum is found?

What extra decision is needed before using “the first entry” to initialise a maximum?

One example passes. What can you conclude about the algorithm?

Implement your own list task

On paper, write complete pseudocode that returns all even entries in their original order, including repeats. State the input, initialise an empty output list, loop over every input entry, test whether it is even, append passing entries, and output after the loop. Trace your design on [4, −2, 4, 0, 7], its first two entries and an empty list. This open implementation is a self-check, not an automatically graded proof

1. 1Explain why it works After any number of iterations, selected contains exactly the even entries visited so far, in their original order. Starting with [] and appending only passing entries preserves this statement

Build your even-entry filter: use “x is even”, append x, and no inside reset. Test L = [4, −2, 4, 0, 7], then its first two entries, then an empty list. Compare the generated pseudocode with your own version

Which full-list result preserves both order and repeated entries?