DoAssignment.ca

DoAssignment study guide

B3.1 · Design simple array algorithms to a specification

Learn to design simple array algorithms to a specification through clear examples and targeted practice.

Ontario Grade 11 Computer Science

Software Development

ICS3U study topic B3.1: turn a clear requirement into steps that process an array

An array stores a sequence of related values so a program can work with them by position. An array algorithm is a set of steps for examining or changing those values to achieve a stated result. Designing the algorithm begins with understanding the specification: what information is provided, what result is required, and what conditions must be followed. For example, “count the temperatures that are at least 20” is more precise than “process the temperatures.” This lesson develops simple array algorithms from such requirements. The code examples use Python 3, where array-like lists use zero-based indexes: the first item is at index 0. Classrooms may use another language, where array syntax or indexing rules can differ. Code is shown for reading and tracing, not executed.

What you will learn

  • Explain how a specification describes an algorithm’s inputs, processing, and expected output.
  • Plan a simple algorithm that examines or updates the items in a one-dimensional array.
  • Trace array indexes and variables to check that an algorithm meets its specification.

1. Read the specification before designing

A specification states what an algorithm must do. A useful first step is to restate it in plain language. Identify the inputs, the required result, and any important conditions. If the task says “count scores of 70 or higher,” the input is a collection of scores and the output is one count. The condition is that a score qualifies when it is at least 70.
Separate the required result from the method. A specification usually describes the result, not every line of code needed to produce it. Your design supplies those steps. For a counting task, a natural plan is to start a counter at zero, examine each item once, and increase the counter when the item meets the condition.
Check that the specification is clear enough to guide a design. Ask what the array contains, whether it can be empty, whether the original values should change, and what to return. Do not silently add requirements. If a detail is missing and affects the answer, state a reasonable assumption or ask for clarification.
  • Inputs are the data the algorithm receives.
  • Processing is the sequence of steps applied to the data.
  • Output is the result required by the specification.
  • An assumption should be stated when the specification leaves an important detail open.

2. Choose steps that cover the array

For a one-dimensional array, a loop can visit its items in order. In Python 3, a loop such as `for value in values` visits each value without explicitly using its index. A loop using indexes is useful when the specification requires a position or an update at a particular position. Python list indexes start at 0, and the last valid index is one less than the number of items.
For a task that must consider every item, make sure the loop includes the first and last items and does not skip any in between. Then identify what must be remembered while the loop runs. A counter remembers how many qualifying values have been found; a running total remembers the sum so far. State the starting value and the rule for updating it.
A trace checks the design by following a small input one step at a time. Record the current item and any changing variables after each step. This can reveal an incorrect starting value, a condition that excludes a boundary value, or a loop that stops too early. A trace predicts what the shown code should produce; it is not a claim that the code was run.
  • Use a loop when the same kind of step must be applied to several array items.
  • Choose a variable that records exactly the information the specification needs.
  • Trace values in order, including items that do not meet a condition.

3. Check the design against the requirement

After writing the steps, compare them with the specification. Does the algorithm use the correct input? Does it apply the stated condition exactly? Does it return the requested kind of result? For example, a task asking for a count needs a number of matching items, not the matching items themselves.
Try a small, carefully chosen input. Include ordinary values and, where relevant, a value exactly on a threshold. Also consider an empty array if the specification permits one. These cases help check whether the initial value and loop condition fit the requirement. For an empty array, a counting algorithm that starts at zero and has no loop iterations should return zero.
A design is not complete just because it looks plausible. Explain why its steps produce the required result: each item is considered, the stated condition determines whether the stored result changes, and the final result has the form the specification asks for. Keep the explanation at the level of the task; the goal here is a simple, correct array algorithm.
  • Test the wording of the condition carefully, especially equality at a boundary.
  • Use a trace or small test cases to check the design.
  • Confirm that the final output matches the specification’s requested form.

Trace for counting scores

Score examinedCondition score >= 70Count after check
62No0
70Yes1
84Yes2

Trace for the first-position search

Index checkedValueMatches Mina?Action
0MinaYesReturn 0

Worked example

Count values that meet a threshold

Specification: Given a list of whole-number quiz scores, return how many scores are at least 70. Input: scores. Output: one count. The list may be empty, and the input values must not be changed.
Input scores
Index → stored value062170284

Python 3 list indexes are zero-based; this algorithm counts values, not indexes.

Python 3

def count_passing(scores):
    count = 0
    for score in scores:
        if score >= 70:
            count += 1
    return count
  1. Plan
    Start the count at zero. Examine each score and add one only when it is at least 70. The comparison includes 70 because the specification says “at least.”
  2. Trace
    For the input scores 62, 70, and 84, the first score leaves the count at zero. The second raises it to one, and the third raises it to two. The array remains unchanged.
  3. Conclude
    The final count is two, so the predicted output is 2. Each input score was considered once and only qualifying scores changed the count.
Answer: 2
Check: The boundary value 70 is counted, as required by “at least 70.”

Worked example

Find the first position of a value

Specification: Given a list of names and a target name, return the index of its first occurrence. If the target is absent, return -1. Input: names and target. Output: an index or -1. Python 3 indexes are zero-based.
Names to search
Index → stored value0Mina1Omar2Mina

The first matching value is at index 0.

Python 3

def first_position(names, target):
    for index in range(len(names)):
        if names[index] == target:
            return index
    return -1
  1. Plan
    Check positions in increasing order. Return as soon as the target is found; because positions are checked from first to last, this is its first occurrence. If the loop ends without a match, return -1.
  2. Trace
    For names containing Mina, Omar, Mina and target Mina, index 0 is checked first and matches. The algorithm returns 0 without needing to check later positions. If the target were Zed, every position would be checked and the result would be -1.
  3. Conclude
    The predicted output for target Mina is 0. Returning the position, rather than the name itself, matches the specification.
Answer: 0
Check: The search begins at Python index 0, so the first item’s position is reported as 0.

Worked example

Create a new array with adjusted values

Specification: Given a list of whole-number prices and a fixed discount of 3 units, return a new list with 3 subtracted from each price. Keep the input list unchanged. Input: prices. Output: a new list in the same order.
Input and result
Index → stored valueInput 012Input 18Input 215Output 09Output 15Output 212

Each result item is made from the input item at the same zero-based index.

Python 3

def discounted(prices):
    result = []
    for price in prices:
        result.append(price - 3)
    return result
  1. Plan
    Start an empty result list. For each input price, calculate the adjusted value and add it to the result list. This preserves the original order and leaves the input list untouched.
  2. Trace
    With input values 12, 8, and 15, the result begins empty. Processing 12 adds 9; processing 8 adds 5; processing 15 adds 12. The input still contains 12, 8, and 15.
  3. Conclude
    The predicted output is the new list 9, 5, 12. Each output item corresponds to the input item at the same position, with 3 subtracted.
Answer: [9, 5, 12]
Check: The result has three items in the same order as the three input items; the input list is not modified.

Common mistakes and how to avoid them

Using a condition that excludes a value equal to the threshold.
Correction: Translate the specification’s exact words into the comparison. “At least 70” includes 70, so use a condition equivalent to score greater than or equal to 70.
Reporting a position as though Python indexes began at 1.
Correction: In Python 3, the first item is at index 0. State the language’s indexing convention when presenting a position.
Returning a matching item when the specification asks for its position.
Correction: Check the required output form. A search can return an index, the item, or another result; follow the specification.
Changing the input list when the specification says to keep it unchanged.
Correction: Build a separate result list and add the adjusted values there.
Forgetting the result when no search item matches.
Correction: Follow the specified no-match case. In the search example, the loop ends and returns -1.

Lesson summary

  • Start with the specification: identify the input, processing requirement, output, and any conditions.
  • Choose simple steps that visit the required array items and keep only the information needed for the result.
  • Trace a small input to check the changing variables, indexes, and final result.
  • Check that boundary cases and the output form agree with the specification.

Check your understanding

Question 1

A Python 3 list contains 5, 9, and 9. An algorithm counts values greater than 5. What should it return?
  1. 0
  2. 1
  3. 2
  4. 3
Show answer and explanation
2
Both 9s are greater than 5, while 5 is not. The count is 2.

Question 2

A Python 3 search checks a list from index 0 upward and returns the first matching index. If the target is at the second position, which index is returned?
  1. 0
  2. 1
  3. 2
  4. -1
Show answer and explanation
1
Python uses zero-based indexes, so the second position has index 1.

Question 3

A specification asks for a new list with 4 added to each input value and says to preserve the input. Which design best fits?
  1. Add 4 to each item in the input list.
  2. Build a new list by adding 4 to each input item in order.
  3. Return the number of items in the input list.
  4. Return only the first input value plus 4.
Show answer and explanation
Build a new list by adding 4 to each input item in order.
A separate result list meets both requirements: adjust every item and leave the input unchanged.

Key terms

Array
An ordered collection of related values that a program can access by position. Python examples here use lists as array-like collections.
Index
A number used to identify an item’s position in an array-like collection. Python 3 list indexes begin at 0.
Specification
A description of what an algorithm receives, what it must do, and what result it must provide.
Trace
A record of how an algorithm’s values and variables change as its steps are followed for a chosen input.

Continue through ICS3U

View the complete ICS3U Ontario Grade 11 Computer Science curriculum and lessons

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 11 Computer Science (ICS3U), expectation B3.1. It is a study resource, not an official curriculum publication.

Before publication, content is checked for structure, mathematical or chemical notation, calculations, course boundaries, and readability. Errors can still occur, so corrections are welcomed.

Official curriculum reference

Report a correction or ask a question