Developing Algorithms - AP Computer Science Principles Study Guide

Getting Started

Complex problems are rarely solved in one single step. To build sophisticated software, from a mobile app to a scientific simulation, programmers combine smaller, well-defined solutions into a larger, more powerful whole. This chapter explores how algorithms—the core recipes of computing—are developed, combined, and reused to solve new and challenging problems efficiently.

What You Should Be Able to Do

• Express a solution to a problem using an algorithm.

• Explain how existing, correct algorithms can be used as building blocks to create new algorithms.

• Describe how procedures and libraries contribute to code reusability and problem-solving.

• Develop algorithms that are clear and readable for other programmers.

Key Concepts & Application

The Core Idea

Think of developing an algorithm like creating a complex meal. You don't just start mixing ingredients randomly. Instead, you follow a main recipe that relies on several smaller, self-contained recipes. For example, to bake a decorated cake, you might follow three distinct procedures: one for baking the sponge, one for making the frosting, and a final one for assembling and decorating. Each of these is a complete algorithm in itself.

In programming, we do the same thing. We create a main algorithm that calls upon other, smaller algorithms to handle specific tasks. We might even use a "store-bought" ingredient, like a pre-made frosting. This is analogous to using a library—a collection of pre-written and tested algorithms that we can use without needing to know their internal details. This process of using a tool without understanding its inner workings is a powerful form of abstraction. It allows us to focus on solving our main problem rather than re-solving problems that others have already solved.

An algorithm is a finite set of instructions that accomplishes a specific task. The development of a complex algorithm is often done by combining existing algorithms that use sequencing, selection, and iteration.

Logic & Application

Algorithms are combined using the same three control structures you already know:

• Sequencing: Executing steps in a specific order. For example, you must calculate a discount before you calculate the final tax.

• Selection: Using conditional logic (e.g., IF / ELSE) to decide which algorithm or step to execute next. For example, IF a user is a premium member, apply a special discount algorithm.

• Iteration: Repeating a set of steps. For example, you might process a list of items by applying the same price-calculation algorithm to each one in a loop.

A procedure is a named group of instructions that implements an algorithm, making it reusable. Procedures can accept inputs, called parameters, to customize their behavior.

Annotated Pseudocode Example

Imagine we are writing an algorithm to calculate the total cost for a list of items in a shopping cart. This main algorithm will rely on two smaller, pre-existing procedures: calculateSubtotal and calculateFinalTotal.

// PROCEDURE: calculateSubtotal

// Purpose: Calculates the sum of prices for a list of items.

// Parameter: itemList - A list of item prices.

// Returns: The sum of all prices in the list.

PROCEDURE calculateSubtotal (itemList)

{

  subtotal <- 0

  FOR EACH price IN itemList

  {

    subtotal <- subtotal + price

  }

  RETURN subtotal // Return the calculated sum

}


// PROCEDURE: calculateFinalTotal

// Purpose: Calculates the final price including tax.

// Parameters: amount - The subtotal before tax.

//             taxRate - The tax rate as a decimal (e.g., 0.08).

// Returns: The final total including tax.

PROCEDURE calculateFinalTotal (amount, taxRate)

{

  tax <- amount * taxRate

  total <- amount + tax

  RETURN total // Return the final calculated total

}


// --- Main Program Logic ---

// This is where we combine our existing algorithms.

shoppingCart <- [20.00, 50.00, 10.00] // A list of item prices

SALES_TAX_RATE <- 0.08


// 1. Call the first procedure (sequencing)

cartSubtotal <- calculateSubtotal(shoppingCart)


// 2. Call the second procedure using the result of the first (sequencing)

finalPrice <- calculateFinalTotal(cartSubtotal, SALES_TAX_RATE)


DISPLAY("Subtotal: $")DISPLAY(cartSubtotal)DISPLAY("FinalPrice:$")

DISPLAY(finalPrice)

In this example, the main program logic doesn't need to know how the subtotal or final total are calculated. It simply trusts that the calculateSubtotal and calculateFinalTotal procedures work correctly. This use of procedures makes the main program easier to read and manage.

Tracing & Analysis

Let's trace the execution of the main program logic from the example above.

• Logic Trace

This trace shows how the program's flow of control moves between the main logic and the procedures, using the output of one procedure as the input for another.

Key Terminology & Logic

• PROCEDURE name (parameter1, parameter2): Defines a named block of code that can be called elsewhere in the program. It can accept zero or more parameters (inputs).

• RETURN (value): Used inside a procedure to send a value back to the part of the program that called it.

• Library: A collection of pre-written, tested procedures that can be imported and used in a program, promoting code reuse.

Core Concepts & Terminology

• Algorithm: A finite, step-by-step set of instructions designed to perform a specific task or solve a particular problem.

• Abstraction: The process of simplifying a complex system by hiding unnecessary details. Using a procedure without knowing its internal code is a form of abstraction.

• Procedure: A reusable, named section of an algorithm that performs a specific task. It can be called from other parts of the algorithm.

• Library: A collection of pre-written procedures and algorithms that a programmer can use to avoid rewriting common code, such as for math operations or graphics.

• Core Logic: Defining a Procedure: A procedure encapsulates an algorithm so it can be easily reused.

  
  PROCEDURE drawSquare (sideLength)
  
  {
  
    REPEAT 4 TIMES
  
    {
  
      MOVE_FORWARD(sideLength)
  
      TURN_RIGHT(90)
  
    }
  
  }
  

  This procedure groups the steps for drawing a square into a single, callable command: drawSquare().

Core Skill Check

• Logic Tracing: What is displayed after this pseudocode runs?

  
  PROCEDURE triple(x) { RETURN (x * 3) }
  
  a <- 4
  
  b <- triple(a)
  
  DISPLAY(b)
  

• Debugging: Identify the logic error in this pseudocode that attempts to find the average of two numbers.

  
  PROCEDURE findAvg (num1, num2)
  
  {
  
    sum <- num1 + num2
  
    avg <- sum / 2
  
  }
  
  result <- findAvg(10, 20)
  
  DISPLAY(result)
  

• Application: Describe how a video streaming service might combine different algorithms to recommend a new movie to a user.

Common Misconceptions & Clarifications

• Misconception: An algorithm must be written in a programming language.

  • Clarification: An algorithm is a sequence of steps. It can be expressed in natural language, a flowchart, or pseudocode. The code is just the final implementation of the algorithm.

• Misconception: You should always write your own code for every part of your program.

  • Clarification: Effective programmers frequently use libraries of existing, tested algorithms. This saves time, reduces errors, and allows them to focus on the unique aspects of the problem they are trying to solve.

• Misconception: A procedure and an algorithm are the exact same thing.

  • Clarification: They are closely related. An algorithm is the abstract sequence of steps, while a procedure is the concrete implementation of that algorithm in a way that can be named and called within a program.

Summary

Developing algorithms is a foundational skill in computer science that involves both creating new logic and, just as importantly, combining existing, proven algorithms. By using control structures like sequencing, selection, and iteration, we can orchestrate how different algorithms work together. Procedures and libraries are essential tools of abstraction that allow us to package and reuse solutions, making our code more organized, readable, and efficient. This modular approach—building large systems from smaller, reliable parts—is how virtually all complex software is created.