Purpose and Overview

Learning Objectives

1. 1Explain what computational thinking means and why it matters before writing code.
2. 2Apply decomposition to break a large problem into smaller, manageable sub-problems.
3. 3Recognize patterns in data and in the structure of computing problems.
4. 4Apply abstraction to identify what details matter and what can be safely left out.
5. 5Define the three essential properties of a correct algorithm.
6. 6Trace an algorithm step by step with a given input and record each variable's value.
7. 7Write a simple procedure using pseudocode and represent a decision using a flowchart.
8. 8Describe the purpose of a model and explain the tradeoff between accuracy and simplicity.
9. 9Design a test plan that includes typical cases, boundary cases, and edge cases.
10. 10Explain what debugging and iteration mean in problem solving.
11. 11Identify computational thinking habits in everyday situations outside of programming.

Sections at a Glance

• 3.1What Computational Thinking MeansThe four core ideas; thinking before coding; Wing's framework; computational thinking is not only for computers
• 3.2DecompositionBreaking problems apart; levels of decomposition; why it enables collaboration and reuse; common mistakes
• 3.3Pattern RecognitionPatterns in data, problems, and structure; common computational patterns; design patterns; connection to machine learning
• 3.4AbstractionMaps as abstraction; black boxes; levels of abstraction; abstraction hierarchy; generalization; risks of too much or too little
• 3.5Algorithmic ThinkingPrecision, finiteness, correctness; algorithms are not programs; tracing; efficiency; the dictionary example
• 3.6Modeling ProblemsWhat a model is; models in computing; mental vs. formal models; simulation as a special kind of model
• 3.7Step-by-Step ProceduresPrecision is kindness; the sandwich example; pseudocode conventions; flowchart symbols and structure
• 3.8Testing and Improving SolutionsWhy first solutions fail; test case categories; debugging strategies; iteration; "make it work, make it right, make it fast"
• 3.9Computational Thinking Beyond ProgrammingEveryday life; science and engineering; connection to AI; becoming a computational thinker

What Computational Thinking Means

The Four Core Ideas

Decomposition

Decomposition in Computing

1. Decompose the following task into at least five sub-tasks, written as an indented list: Plan and run a one-week summer computer science camp for 30 middle school students.
2. A ride-share app must match a passenger's request with an available driver. Decompose this matching problem. What information does each party provide? What conditions must be satisfied? What must the system do at each stage?
3. The following decomposition has a structural problem. Identify it and explain how to fix it.
   
   TASK: Build a social media posting feature
├── Build the entire user interface
├── Write all the backend code
└── Launch the feature
4. Choose a sport you know well. Identify at least four sub-problems that a computer system tracking scores, statistics, and standings for that sport would need to handle. What data does each sub-problem use? What output does each produce?

Pattern Recognition

Patterns in Data

Patterns in Problems

1. Identify the pattern in each sequence and predict the next two values.
   a. 3, 6, 9, 12, 15, __, __
   b. 1, 2, 4, 8, 16, __, __
   c. 100, 90, 81, 73, 66, __, __ (Hint: differences are decreasing.)
   d. A, B, D, G, K, __, __ (Hint: think about letter positions in the alphabet.)
2. The three problems below look different on the surface. Identify the single underlying computational pattern they share.
   
   — Find the student who has the most absences this semester.
   — Find the product with the highest average customer rating.
   — Find the city with the largest population in a dataset.
3. A programmer has already written a function find_minimum(list) that finds the smallest number in a list. A new problem requires finding the student with the lowest test score from a list of student records. How does pattern recognition help? What would you need to do to adapt the existing solution?
4. Identify two real-world applications of machine learning you encounter in daily life. For each one, describe: (a) what data the system recognizes patterns in, and (b) what the system does once it recognizes a pattern.

Abstraction

A Map as Abstraction

Black Boxes in Programming

Levels of Abstraction

1. A database stores information about books in a library. List five details about a physical book the database should include, and five it can safely leave out. Explain your reasoning for each decision.
2. The following description is poorly abstracted — it includes too many irrelevant implementation details. Rewrite it as a clean, appropriately abstracted description.
   
   "The program should accept a text file. The file will be named report.txt and stored in the C:\Users\Documents folder on a Windows 10 computer. It will have between 100 and 500 lines. Each line will end with a carriage return followed by a newline character..."
3. Describe the layers of abstraction involved when a user in Brazil sends an instant message to a friend in Japan. Identify at least three distinct layers and explain what each one hides from the layer above it.

Algorithmic Thinking

Example Algorithm: Finding the Largest Number

ALGORITHM: Find the Largest Number

INPUT:  A list of numbers with at least one element

STEP 1: Set current_largest = first number in the list
STEP 2: FOR EACH remaining number in the list:
    STEP 2a:  IF this number > current_largest
                  set current_largest = this number
STEP 3: Report current_largest as the answer

OUTPUT: The largest number in the list

Tracing the Algorithm

Trace with input list: 7, 3, 12, 5, 9

Algorithms Have Efficiency

1. Trace the Find-the-Largest algorithm with the input list: 15, 8, 23, 4, 19, 11. Show your work in a table with columns for Step, Current Number, Current Largest, and Action.
2. Trace the following algorithm with name = "AHMED". How many vowels does it count? Show each step.
   
   STEP 1: Set vowel_count = 0
STEP 2: FOR EACH letter in name:
   STEP 2a: IF letter is A, E, I, O, or U:
      increase vowel_count by 1
STEP 3: Report vowel_count
3. The algorithm below is supposed to sum all numbers from 1 to n. Trace it with n = 5. Identify whether it is correct or contains a bug. (Hint: what is 1+2+3+4+5?)
   
   STEP 1: Set total = 0, counter = 1
STEP 2: WHILE counter < n:
   add counter to total
   add 1 to counter
STEP 3: Report total

Modeling Problems

1. Design a data model for a simple school attendance system. Describe what objects the system needs to track, what data fields each object needs, and what the model can safely leave out.
2. You are designing a simulation of cars approaching a traffic light. What information would your simulation need to track? What simplifications would you make? What would make it more realistic, and is that additional complexity worth it for studying traffic flow?

Step-by-Step Procedures

Writing Pseudocode

PROCEDURE: Assign Letter Grade

INPUT: numeric_score  (a number between 0 and 100)

IF numeric_score >= 90  THEN
    letter_grade = "A"
ELSE IF numeric_score >= 80  THEN
    letter_grade = "B"
ELSE IF numeric_score >= 70  THEN
    letter_grade = "C"
ELSE IF numeric_score >= 60  THEN
    letter_grade = "D"
ELSE
    letter_grade = "F"
END IF

OUTPUT: letter_grade

Flowcharts

1. Write pseudocode for the following procedure: Given a list of numbers, compute the average (mean). The average is the sum of all numbers divided by the count of numbers. Make sure your pseudocode handles at least one edge case.
2. Draw a flowchart for a procedure that decides whether a customer is eligible for a discount. The rule is: customers who have spent more than $100 total OR who have placed more than 5 orders receive a 10% discount. Use proper flowchart symbols.
3. The following pseudocode is meant to print all even numbers from 2 to 20. Find and explain the error, then write the corrected version.
   
   STEP 1: Set n = 0
STEP 2: WHILE n <= 20:
   print n
   add 2 to n

Testing and Improving Solutions

Categories of Test Cases

Debugging: Finding and Fixing Mistakes

Iteration: Improving the Solution

1. Design a test plan for an algorithm that takes a positive integer n and returns the sum of all odd numbers from 1 to n. Your plan must include at least one typical case, one boundary case, one edge case, and one invalid-input case. For each test, state the input, expected output, and what aspect of correctness it checks.
2. A student's grade-assignment algorithm produces "B" for a score of 90 when it should produce "A". Using the trace strategy, identify the most likely location of the bug. What question would you ask when checking assumptions?
3. Explain the difference between debugging and iteration. Could you have a program that needs iteration but not debugging? Could you have one that needs debugging but not iteration? Give a brief example for each case.
4. The following algorithm is supposed to count down from 10 to 1 and then print "Done." Identify the bug, explain what will happen when it runs, and write the corrected version.
   
   STEP 1: Set counter = 10
STEP 2: WHILE counter > 0:
   print counter
STEP 3: print "Done"

Computational Thinking Beyond Programming

1. Describe a specific real-world problem from your own daily life. Apply all four pillars of computational thinking to it: How would you decompose it? What patterns can you recognize? What abstraction would you apply? What algorithm would you design?
2. A city wants to design a better system for tracking and filling potholes in its roads. Apply computational thinking to this problem: What data should the system collect? What patterns in that data would be useful? What information can be abstracted away? Design a simple algorithm for prioritizing which potholes to fix first.
3. Choose any three of the following areas and explain specifically how each pillar of computational thinking applies: sports coaching · emergency medicine · urban planning · journalism · teaching · cooking.

Chapter Summary

• Sec 3.1Computational thinking is the set of habits computer scientists use to approach problems before writing code. It was formalized by Jeannette Wing in 2006. Its four core ideas are decomposition, pattern recognition, abstraction, and algorithmic thinking. It applies beyond computing to any complex, information-rich problem.
• Sec 3.2Decomposition means breaking a large problem into smaller, independent sub-problems. It operates at the levels of problems, programs, algorithms, and data. It enables manageability, collaboration, and reuse. Good decomposition finds the right granularity — sub-problems small enough to work on independently but large enough to represent a meaningful piece of the whole.
• Sec 3.3Pattern recognition means noticing regularities in data and in the structure of problems. Common computational patterns include counting, accumulation, filtering, sorting, searching, transformation, and matching. Recognizing a pattern lets you reuse existing knowledge rather than solving every problem from scratch. Pattern recognition is also the foundation of machine learning.
• Sec 3.4Abstraction means deliberately leaving out irrelevant detail to focus on what is essential for solving a problem at a given level. Abstraction is how computer scientists manage complexity. Systems are built in layers of abstraction — each layer hides the complexity below and provides a clean interface to the layer above. Good abstraction is reusable and clear; it is neither too specific nor too general.
• Sec 3.5An algorithm is a precise, finite, step-by-step procedure with three essential properties: precision, finiteness, and correctness. Algorithms are not programs — they are ideas that can be expressed in any language. Tracing an algorithm means following it step by step with specific inputs to verify correctness. Two correct algorithms may differ significantly in efficiency.
• Sec 3.6A model is a simplified representation of a real system. Models include only what is relevant to the problem at hand and deliberately exclude the rest. A simulation is a model that evolves through time, used to test scenarios too costly, dangerous, or slow to test in the real world.
• Sec 3.7Computers follow instructions literally and precisely. Writing procedures for computers demands complete, unambiguous steps. Pseudocode expresses algorithms in human-readable form without the constraints of any programming language. Flowcharts represent procedures visually, using standard symbols for processes, decisions, and flow direction.
• Sec 3.8First solutions are rarely perfect. Testing means deliberately checking whether a solution produces correct output, using typical cases, boundary cases, edge cases, and invalid inputs. Debugging finds and fixes errors through tracing, observation, isolation, and assumption-checking. Iteration is the cycle of improving a solution over multiple rounds of testing and revision.
• Sec 3.9Computational thinking appears in cooking, travel, sports, science, engineering, medicine, and daily decision-making. Its four pillars — decomposition, pattern recognition, abstraction, and algorithmic thinking — are general problem-solving habits, not programming skills. Artificial intelligence is a direct large-scale application of these habits applied to data.

Key Terms Review

Concept Check

Answer each question before moving to the practice sections.

1. What are the four core ideas of computational thinking?
2. What does it mean to "decompose" a problem? Give one example from daily life.
3. Give one example of a computational pattern that appears across many different programming problems.
4. What is the difference between an algorithm and a program?
5. State the three essential properties of a correct algorithm.
6. What is a "boundary case" in testing? Why is it important to test boundary cases specifically?
7. What is iteration, and why is it a normal part of problem solving rather than a sign that something went wrong?
8. What is abstraction, and why is it useful? What is the risk of applying too much abstraction?
9. What is a model? In what sense is every model incomplete?
10. Name two everyday situations — outside of programming — where computational thinking applies.

Debugging and Error Analysis

Each example below contains at least one error. Identify the error and write the corrected version.

Review Questions

1. Define computational thinking in your own words. Why is it valuable beyond programming?
2. What is the difference between decomposition and abstraction? Can you practice one without the other? Give an example.
3. A friend says: "I don't need to learn algorithms — I can just look up how to do things online." How would you respond? What does understanding algorithms give you that copying code does not?
4. Why does precision matter so much in writing algorithms? Give an example of an instruction that a human would understand correctly but that is ambiguous enough to cause problems for a computer.
5. What does it mean to test a "boundary case"? Give a specific boundary case for an algorithm that decides whether a student has passed a course (passing = score of 60 or above).
6. What is the relationship between a model and the real system it represents? What is always true of every model? What does this mean for the limitations of simulations?
7. Why is iteration a normal and expected part of problem solving rather than evidence of failure?
8. Explain the following statement: "An algorithm is a recipe for solving a problem; a program is one way of cooking it."
9. A student writes an algorithm that calculates a restaurant bill including tax. They test it with one input — a $20 meal at 8% tax — and get the correct answer ($21.60). They conclude the algorithm is correct. Is this a sound conclusion? What additional tests should they run and why?
10. Choose any three areas from this list and explain specifically how all four pillars of computational thinking apply in each: weather forecasting · urban emergency response · athletic training · financial fraud detection · museum curation.

Chapter 3 Checkpoint

Mixed Review

These questions connect Chapter 3 to earlier chapters.

1. A smartphone takes a photograph. Using the input-process-output-storage model from Chapter 2, describe what happens. Then identify which step of the computational thinking framework is most relevant to each phase.
2. From Chapter 1, computer science is described as the study of computation, information, algorithms, programs, machines, systems, networks, data, automation, security, and responsible technology. For each of the following areas, identify the computational thinking skill that is most important for working in it, and explain why: networks · security · automation · data.
3. In Chapter 2, you learned that computers process information using input, processing, output, and storage. Explain how computational thinking helps you decide what information goes in, what processing should happen, and what information comes out. Give a specific example.
4. Explain how abstraction relates to the concept of digital representation from Chapter 2. When a computer stores an image as pixels, what details of the real scene has it abstracted away? Why is that abstraction useful and not a problem?