Computational Thinking

Example: Java

public class Rectangle {
    private double width;
    private double height;

    public Rectangle(double w, double h) {
        width = w;
        height = h;
    }

    public double getArea() {
        return width * height;
    }

    public double getPerimeter() {
        return 2 * (width + height);
    }
}

The caller uses getArea() and getPerimeter() without knowing that width and height are Stored as doubles. The implementation could be changed to store different data (e.g., coordinates of Corners) without affecting any code that uses this class.

Example: Finding the Maximum

PROCEDURE findMax(list)
{
    max <- list[1]
    FOR EACH item IN list
    {
        IF (item > max)
        {
            max <- item
        }
    }
    RETURN(max)
}

Proof of correctness (invariant). Invariant: “max is the largest element among all elements Examined so far.” Initially, max = list[1], the largest of the first element. When a new Item is compared, if it is larger, max is updated; otherwise, max remains the largest. By induction, After all elements are examined, max is the largest in the entire list. $\blacksquare$

Example: Finding the Second Largest

PROCEDURE findSecondLargest(list)
{
    IF (LENGTH(list) < 2)
    {
        RETURN(0)
    }
    IF (list[1] > list[2])
    {
        max <- list[1]
        second <- list[2]
    }
    ELSE
    {
        max <- list[2]
        second <- list[1]
    }
    FOR i <- 3 TO LENGTH(list)
    {
        IF (list[i] > max)
        {
            second <- max
            max <- list[i]
        }
        ELSE IF (list[i] > second)
        {
            second <- list[i]
        }
    }
    RETURN(second)
}

Time complexity: $O(n)$ — single pass through the list.

Example: Linear Search (AP CSP)

PROCEDURE linearSearch(list, target)
{
    FOR i <- 1 TO LENGTH(list)
    {
        IF (list[i] = target)
        {
            RETURN(i)
        }
    }
    RETURN(0)
}

Note: AP CSP pseudocode returns 0 (not -1) to indicate “not found”, because index 0 is not a valid Position in 1-based indexing.

Example: Binary Search (AP CSP)

PROCEDURE binarySearch(list, target)
{
    low <- 1
    high <- LENGTH(list)
    REPEAT UNTIL ((low > high) OR (list[mid] = target))
    {
        mid <- (low + high) / 2
        IF (list[mid] < target)
        {
            low <- mid + 1
        }
        ELSE
        {
            high <- mid - 1
        }
    }
    IF (list[mid] = target)
    {
        RETURN(mid)
    }
    ELSE
    {
        RETURN(0)
    }
}

Complexity analysis. Each iteration halves the search space, so the maximum number of iterations Is $\lceil \log_2 n \rceil$. Time complexity: $O(\log n)$.

Example: Counting Occurrences

PROCEDURE countOccurrences(list, value)
{
    count <- 0
    FOR EACH item IN list
    {
        IF (item = value)
        {
            count <- count + 1
        }
    }
    RETURN(count)
}

Time complexity: $O(n)$ — examines each element once.

Example: Reversing a List

PROCEDURE reverseList(list)
{
    reversed <- []
    FOR i <- LENGTH(list) DOWNTO 1
    {
        APPEND(reversed, list[i])
    }
    RETURN(reversed)
}

Time complexity: $O(n)$ — copies each element once.

Proof of termination. The loop variable i starts at LENGTH(list) and decreases by 1 each Iteration until it reaches 1. Since LENGTH(list) is a finite positive integer, the loop terminates After LENGTH(list) iterations. $\blacksquare$

Problem Solving Strategies

Top-Down Design

Start with the main problem, then decompose into subproblems. Each subproblem is further decomposed Until the tasks are simple enough to implement directly.

Example: “Build a student management system.”

Level 1: Student records, course enrolment, grading, reporting.

Level 2 (under Student records): Add student, edit student, delete student, search student.

Level 3 (under Add student): Validate name, validate ID, check for duplicates, save to database.

Stepwise Refinement

Gradually add detail to a high-level design. Start with pseudocode, then refine each step into more Specific instructions.

Example:

Level 1: Calculate the average exam score for a class.

Level 2: Read all scores. Sum them. Divide by the number of scores.

Level 3: Open the file. For each line, parse the score. Add to running total. Increment counter. After all lines, divide total by counter. Display result.

Heuristics

General problem-solving strategies that are not guaranteed to work but are often effective:

• Trial and error: Try different approaches.
• Working backward: Start from the desired outcome.
• Divide and conquer: Split the problem into independent parts.
• Draw diagrams: Visualize the problem.

Worked Example. Solve the following problem using working backward: “A number is doubled, then 5 is added, then the result is squared, giving 144. What was the original number?”

Working backward: $\sqrt{144} = 12$. $12 - 5 = 7$. $7 / 2 = 3.5$. The original number is 3.5.

Algorithms as Abstraction

An algorithm is a finite set of unambiguous instructions that solves a problem or performs a task.

Properties of a Good Algorithm

1. Input: Zero or more inputs.
2. Output: At least one output.
3. Definiteness: Each step is precisely defined.
4. Finiteness: The algorithm terminates after a finite number of steps.
5. Effectiveness: Each step is basic enough to be carried out.

Representing Algorithms

• Natural language (informal)
• Pseudocode (semi-formal)
• Flowcharts (graphical)
• Programming language (formal, executable)

Deciding Between Representations

Pseudocode is the best compromise for communicating algorithms between humans. It is precise enough To unambiguously describe the logic, but does not require knowledge of a specific language’s syntax.

Proving Termination

An algorithm terminates if every loop has a well-defined condition that is eventually satisfied, and Every recursive call makes progress toward a base case.

Example. The following algorithm always terminates:

PROCEDURE countdown(n)
{
    REPEAT UNTIL (n = 0)
    {
        DISPLAY(n)
        n <- n - 1
    }
}

Proof. The variable n decreases by 1 each iteration. Since n is a non-negative integer, it Will eventually reach 0, satisfying the loop condition. $\blacksquare$

Proving Correctness by Induction

Example. Prove that factorial(n) returns $n!$.

Base case: factorial(0) = 1 = 0!. True.

Inductive step: assume factorial(k) = k! for all $k \lt n$. Then factorial(n) = n * Factorial(n-1) = n * (n-1)! = n!. True by the inductive hypothesis.

By induction, factorial(n) = n! for all $n \ge 0$. $\blacksquare$

Abstraction in Practice

Abstract Data Types

An Abstract Data Type (ADT) defines a data type by its behavior (operations) rather than its Implementation. The user interacts with the ADT through a well-defined interface.

Stack ADT:

• push(item): Add an item to the top.
• pop(): Remove and return the top item.
• peek(): Return the top item without removing it.
• isEmpty(): Return true if the stack is empty.

The user does not need to know whether the stack is implemented using an array, a linked list, or Something else.

Queue ADT:

• enqueue(item): Add an item to the back.
• dequeue(): Remove and return the front item.
• peek(): Return the front item without removing it.
• isEmpty(): Return true if the queue is empty.

Stack implementation in Java (AP CS A):

public class ArrayStack {
    private int[] stack;
    private int top;

    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }

    public void push(int item) {
        if (top == stack.length - 1) {
            throw new RuntimeException("Stack overflow");
        }
        stack[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

Time complexity of stack operations:

Using Stacks: Balanced Parentheses

A classic application of stacks is checking for balanced parentheses.

public static boolean isBalanced(String expr) {
    java.util.Stack<Character> stack = new java.util.Stack<>();
    for (char c : expr.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (!matches(top, c)) return false;
        }
    }
    return stack.isEmpty();
}

private static boolean matches(char open, char close) {
    return (open == '(' && close == ')') ||
           (open == '{' && close == '}') ||
           (open == '[' && close == ']');
}

Time complexity: $O(n)$ — each character is pushed and popped at most once.

Using Queues: BFS (Breadth-First Search)

A queue is essential for breadth-first search, which explores nodes level by level.

public static void bfs(int[][] graph, int start) {
    boolean[] visited = new boolean[graph.length];
    java.util.Queue<Integer> queue = new java.util.LinkedList<>();
    visited[start] = true;
    queue.add(start);
    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.add(neighbor);
            }
        }
    }
}

Top-Down Design Example: Contact Management System

Level 1: Contact storage, search, display, import/export.

Level 2 (under Contact storage): Add contact, edit contact, delete contact.

Level 3 (under Add contact): Validate name, validate phone number, check for duplicates, save.

Level 3 (under Search): Search by name, search by phone, search by email.

Each leaf node in the decomposition is a simple, implementable task.

Stepwise Refinement Example: Calculating GPA

Level 1: Calculate GPA from a list of grades.

Level 2: Map each grade to points, sum the points, divide by the number of grades.

Level 3:

PROCEDURE calculateGPA(grades)
{
    totalPoints <- 0
    FOR EACH grade IN grades
    {
        points <- gradeToPoints(grade)
        totalPoints <- totalPoints + points
    }
    RETURN(totalPoints / LENGTH(grades))
}

PROCEDURE gradeToPoints(grade)
{
    IF (grade = "A") { RETURN(4.0) }
    ELSE IF (grade = "B") { RETURN(3.0) }
    ELSE IF (grade = "C") { RETURN(2.0) }
    ELSE IF (grade = "D") { RETURN(1.0) }
    ELSE { RETURN(0.0) }
}

Trace Tables

A trace table records the values of variables as an algorithm executes.

Example: Trace findMax on the list [3, 7, 2, 9, 5].

Final result: 9. Correct.

Example: Trace binarySearch on [2, 5, 8, 12, 16, 23, 38] searching for 16.

Result: index 5. Correct.

Common Pitfalls

1. Confusing abstraction with simplification. Abstraction hides irrelevant details while preserving essential behavior; simplification may lose important information.
2. Not identifying the right level of abstraction. Too high-level: the solution is vague. Too low-level: the solution is cluttered with irrelevant details.
3. Ignoring edge cases in pseudocode. Always consider empty inputs, single-element inputs, and boundary conditions.
4. Confusing procedure parameters with procedure calls. A parameter is a variable in the procedure definition; an argument is the actual value passed when calling the procedure.
5. Using programming-language-specific syntax in pseudocode. AP CSP pseudocode is language-agnostic.
6. Forgetting that lists in AP CSP pseudocode are 1-indexed, not 0-indexed like in Java.
7. Not decomposing the problem sufficiently. If a procedure is too complex, it should be decomposed further.
8. Writing pseudocode that is too vague. “Sort the list” is not an acceptable step — you must describe how to sort it, unless you are calling a named procedure that you have already defined.
9. Forgetting the RETURN statement. A procedure that computes a result must use RETURN to pass the result back to the caller. Without RETURN, the computed value is lost.
10. Confusing REPEAT UNTIL with WHILE. REPEAT UNTIL checks the condition after the body executes (post-test loop). WHILE checks the condition before the body executes (pre-test loop).

Practice Questions

1. Decompose the problem “sort a list of student records by grade point average” into subproblems. Write pseudocode for each subproblem.

2. Write pseudocode for a procedure countOccurrences(list, value) that returns the number of times value appears in list.

3. Explain the difference between procedural abstraction and data abstraction, and give an example of each.

4. Write pseudocode for a procedure isPalindrome(word) that returns true if word reads the same forwards and backwards.

5. A programmer is designing a program to manage a library. Identify three levels of abstraction and describe what details are hidden at each level.

6. Write pseudocode for a procedure that finds the second-largest value in a list of numbers.

7. Explain why abstraction is important in software development. How does it contribute to code maintainability?

8. Write pseudocode for a procedure mergeLists(list1, list2) that combines two sorted lists into one sorted list.

9. Write AP CSP pseudocode for a procedure removeDuplicates(list) that returns a new list with all duplicate values removed.

10. Explain the difference between top-down design and stepwise refinement. How do they complement each other?

11. Write AP CSP pseudocode for a procedure binarySearch(list, target) that returns the index of target in a sorted listOr 0 if not found.

12. Explain what is meant by the “contract” of a procedure. Why are preconditions and postconditions important?

13. Write pseudocode for a procedure reverseList(list) that returns a new list with the elements in reverse order. Prove that your algorithm terminates.

14. Write pseudocode for a procedure isSorted(list) that returns true if the list is sorted in non-decreasing order. What is the time complexity?

15. Explain the difference between REPEAT UNTIL (condition) and WHILE (condition) loops. Give an example where each would be more appropriate than the other.

16. Write pseudocode for a procedure findRange(list) that returns both the minimum and maximum values in a list in a single pass. What is the time complexity compared to calling findMin and findMax separately?

17. (AP CS A) Write a Java method that implements removeDuplicates using an ArrayList. What is the time complexity of your solution?

18. (AP CS A) Write a recursive Java method gcd(int a, int b) that computes the greatest common divisor using Euclid’s algorithm. Prove that it terminates by showing that the arguments decrease at each recursive call.

19. Prove by induction that the procedure sumFirstN(n) which computes $1 + 2 + \cdots + n$ returns $n(n+1)/2$.

20. Write pseudocode for a procedure isAnagram(word1, word2) that returns true if the two words are anagrams of each other. What is the time complexity?

21. Explain how information hiding reduces coupling between modules. Give a concrete example from Java programming.

22. Write pseudocode for a procedure that determines whether a list contains any duplicate values. What is the most efficient approach?

23. Design a procedure mode(list) that returns the most frequently occurring value in a list. What is the time complexity?

24. (AP CS A) Explain the difference between a class and an interface in Java. How does each support abstraction?

25. Write a detailed trace table for the binary search algorithm when searching for 23 in the list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Show the values of low, high, mid, and list[mid] at each step.

Practice Problems

PROCEDURE mystery(n)
{
    result <- 1
    i <- 1
    REPEAT UNTIL (i > n)
    {
        result <- result * i
        i <- i + 1
    }
    RETURN(result)
}

list <- [3, 1, 4, 1, 5]

PROCEDURE calculate(lst)
{
    total <- 0
    FOR EACH item IN lst
    {
        total <- total + item
        REMOVE(lst, 1)
    }
    RETURN(total)
}

result <- calculate(list)

PROCEDURE binarySearch(list, target)
{
    low <- 1
    high <- LENGTH(list)

    REPEAT UNTIL (low > high)
    {
        mid <- (low + high) / 2
        IF (list[mid] = target)
        {
            RETURN(mid)
        }
        ELSE IF (list[mid] < target)
        {
            low <- mid + 1
        }
        ELSE
        {
            high <- mid - 1
        }
    }

    RETURN(0)
}

PROCEDURE findMostCommonWord(filename)
{
    text <- readFile(filename)
    words <- split(text, " ")
    cleanedWords <- []

    FOR EACH word IN words
    {
        cleaned <- toLowerCase(removePunctuation(word))
        IF (LENGTH(cleaned) > 0)
        {
            APPEND(cleanedWords, cleaned)
        }
    }

    counts <- countFrequencies(cleanedWords)
    RETURN(findMaxKey(counts)
}

Summary

This topic covers the core concepts of computational thinking, including underlying theory, practical implementation, and key applications.

Key concepts include:

• Big O notation and complexity analysis
• searching algorithms (binary, linear)
• sorting algorithms (bubble, merge, quick)
• graph algorithms (Dijkstra, BFS, DFS)
• dynamic programming

Understanding these concepts thoroughly is essential for both examinations and practical programming, and requires both theoretical knowledge and hands-on practice.

Worked Examples

Worked examples demonstrating the application of key concepts are covered in the detailed sub-pages linked above.