D4.2 · Investigate a theoretical computer-science topic

Ontario Grade 12 Computer Science

Topics in Computer Science

A focused theoretical investigation for Ontario Grade 12 Computer Science

What you will learn

• Describe a theoretical computer-science investigation as a focused question supported by evidence and a reasoned conclusion.
• Explain the precondition that makes binary search valid.
• Trace binary search and count comparisons for a particular input.
• Distinguish what one example shows from what can be concluded more generally.

1. Start with a question and assumptions

• Define a focused question before examining an algorithm.
• Make input assumptions explicit.
• Use a trace as evidence about its stated example, not as a universal result.

2. The model: inspect the middle and narrow the range

• Sorted order justifies discarding one side after a comparison.
• The midpoint must be an integer index within the current range.
• An empty candidate range means the target was not found.

3. Trace and count carefully

• Count each inspected value once.
• Show enough trace detail to justify each range change.
• Compare algorithms on a specified, shared input.

4. Draw a conclusion within the evidence

• Separate a calculated result from a general claim.
• Explain the assumption that makes an algorithm step valid.
• A conclusion should answer the question and state the limits of the evidence.

Worked example

Trace a successful search

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

1. Set the initial range
   The list has indexes 0 through 6, so all seven positions are candidates. The midpoint index is 3.
   $$low=0,\quad high=6,\quad mid=3$$
2. Check the midpoint
   The value at index 3 is 22, equal to the target. The search stops after this single comparison and returns the index.
   $$A[3]=22$$

Worked example

Trace an absent target and compare counts

def linear_search(values, target):
    for index in range(len(values)):
        if values[index] == target:
            return index
    return -1

1. Inspect the first midpoint
   The initial range is indexes 0 through 6. Its midpoint is index 3, containing 19. Since the target is larger, only indexes 4 through 6 remain candidates.
   $$mid=3,\quad A[3]=19$$
2. Narrow the range again
   The midpoint of indexes 4 through 6 is index 5, containing 35. Since the target is smaller, only index 4 remains a candidate.
   $$mid=5,\quad A[5]=35$$
3. Finish binary search
   Index 4 contains 27. The target is smaller, so the remaining range becomes empty. Binary search reports absence after three comparisons.
   $$mid=4,\quad A[4]=27$$
4. Count linear-search checks
   Because 20 is absent, linear search must check all seven values before it can report absence. The binary-search count of three and linear-search count of seven describe only this list and target.
   $$3<7$$

Worked example

Investigate why sorted input matters

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

1. Check the precondition
   The list is not ascending: 14 is followed by 6. Binary search relies on sorted order to justify discarding a portion, so its conclusion on this input is not reliable.
2. Examine the first decision
   The midpoint of indexes 0 through 4 is index 2, containing 6. Since 11 is larger, the method would keep indexes 3 through 4. Here 11 happens to be at index 4, so this decision keeps it. That outcome does not justify binary search on unsorted lists: another arrangement could place the target in the discarded portion.
   $$mid=2,\quad A[2]=6$$
3. Make the method appropriate
   Sort the values into ascending order before using binary search. Then its ordering-based decisions have the required condition. Alternatively, use a search method that does not rely on sorted order.
   $$[2,6,11,14,20]$$

Common mistakes and how to avoid them

Lesson summary

• A theoretical investigation uses a focused question, explicit assumptions, evidence, and a conclusion supported by that evidence.
• Binary search checks a midpoint and keeps only the portion that could contain the target.
• Ascending sorted order is essential to the reasoning that makes discarded portions impossible candidates.
• Count comparisons from the actual trace; do not turn one example count into an unsupported general claim.

Check your understanding

Key terms

Theoretical computer-science investigation

A focused study of a computer-science idea using clear assumptions, examples or other evidence, and a supported conclusion.

Precondition

A condition that must be true before an algorithm is used. Binary search requires sorted input.

Midpoint

The middle index of the current range of candidate positions.

Comparison count

The number of element-to-target checks made in a particular search trace.

Continue through ICS4U

View the complete ICS4U Ontario Grade 12 Computer Science curriculum and lessons

• D4.1 · Report on interdisciplinary computer-science research
• D4.3 · Research computer-science careers and education
• D1.1 · Assess ways to reduce computing impacts
• D1.2 · Investigate sustainability initiatives
• D2.1 · Analyse an ethical computing issue
• D2.2 · Explain why programmers need a code of ethics

Tutor support for D4.2 · Investigate a theoretical computer-science topic

Working on D4.2 · Investigate a theoretical computer-science topic in ICS4U? Bring the question and your own attempt. In a live session, you can trace a small example and find the first step where the output differs from what you expected. Ask about the first step that does not make sense, then try a similar question yourself.

Explore coding tutoring · Request an eligible free 30-minute introduction. Your request is matched by subject and language; a tutor must accept before a time is confirmed.

برای مبحث D4.2 · بررسی موضوع نظری علوم رایانه در درس ICS4U، سؤال و تلاش خود را همراه بیاورید. در جلسه می‌توانید یک مثال کوچک را دنبال کنید و نخستین گامی را که خروجی با انتظار شما فرق دارد پیدا کنید. راهنمای معلم برنامه‌نویسی را ببینید یا جلسهٔ معارفهٔ رایگان ۳۰ دقیقه‌ای درخواست کنید. زمان جلسه پس از پذیرش معلم قطعی می‌شود.

About this lesson and its review

Published by DoAssignment. This reviewed lesson follows Ontario Grade 12 Computer Science (ICS4U), expectation D4.2. 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