Algorithms are step-by-step plans to solve problems. This topic will help you understand computatinal thinking by learning how to break problems into smaller parts (decomposition) and design clear solutions using flowcharts and pseudocode.
Terminology List
Terminology Flashcards
Abstraction is a fundamental concept in computer science and computational thinking. It involves simplifying complex systems by focusing on the most important details and ignoring unnecessary ones. This approach allows programmers and system designers to manage complexity, solve problems efficiently, and communicate ideas more effectively. From the user interfaces of everyday devices to the design of algorithms and data structures, abstraction plays a crucial role in making technology accessible and functional. In this lesson, you will explore the concept of abstraction through practical examples and learn how it is applied in various aspects of computing.
Key Terms
Abstraction: The process of removing unnecessary details to focus on the relevant ones.
Computational Thinking: A problem-solving approach that involves abstraction.
Interface Design: Designing how a user interacts with a system.
Data Structures: Ways of organizing and storing data for efficient access and modification.
Program Design: The planning stage of software development, involving tools like flowcharts.
Key Ideas
Definition of Abstraction: Focuses on important details while ignoring irrelevant ones.
Examples of Abstraction:
Saving files: Users interact with simple commands like "save" or "delete" without worrying about where or how files are stored.
Sat-Nav Interface: Shows relevant details (e.g., car location, road layout) and excludes unnecessary ones (e.g., trees, buildings).
Icons: Abstract complex functions into simple, recognizable symbols.
Abstraction in Data Structures:
Maps and relationships are simplified to the essentials for algorithm design.
Abstraction in Program Design:
Flowcharts simplify code into visual representations.
Variables in code are labels for memory locations, hiding binary storage details.
Video Summary Guide
Before watching the video, review the key terms and ideas above. Use this guide to focus your note-taking:
What is abstraction?
Why is abstraction important in computational thinking?
Identify examples of abstraction in everyday systems.
How does abstraction apply to sat-nav design?
Explain the use of abstraction in programming and data structures.
L1 Comprehension Questions
Short Answer: Define abstraction in your own words and explain why it is important in problem-solving.
Short Answer: List two examples of abstraction in user interface design and explain their significance.
Long Answer: Describe how abstraction is used in sat-navs. Include examples of what is shown and what is omitted.
Short Answer: Explain how flowcharts demonstrate abstraction in program design.
Long Answer: Discuss how abstraction simplifies the use of variables and calculations in programming. Why is this helpful for programmers?
Decomposition is a core concept in computational thinking. It involves breaking down a complex problem into smaller, more manageable parts. This makes it easier to understand and solve the problem step by step. By simplifying challenges in this way, programmers can focus on specific tasks, work more efficiently, and even collaborate with others on different parts of a project. In this lesson, you will explore how decomposition is applied in both everyday situations and programming, including designing and building games like "Breakout."
Key Terms
Decomposition: Breaking a complex problem into smaller, more manageable parts.
Sub-Problems: Smaller, individual tasks derived from a larger problem.
Collaboration: Working together to solve parts of a decomposed problem.
Key Ideas
Definition of Decomposition: Simplifies problem-solving by focusing on one smaller task at a time.
Examples of Decomposition in Daily Life:
Tasks like getting up in the morning, brushing your teeth, or crossing the road involve smaller sub-tasks.
Crossing the road: Stop, look both ways, press the button, wait for the light, cross when safe.
Decomposition in Programming:
Game design example: The game "Breakout" can be broken into smaller tasks:
Displaying the paddle.
Making the paddle move and restricting its movement.
Adding a ball, blocks, collision detection, and scoring system.
Advantages of Decomposition:
Makes problems easier to solve.
Allows team collaboration on different parts simultaneously.
Speeds up development time.
Encourages reusability of program components.
Video Summary Guide
Before watching the video, review the key terms and ideas above. Use this guide to structure your note-taking:
What is decomposition?
Why is decomposition important in computational thinking?
Identify examples of decomposition in daily life.
How can decomposition be used to create a game like "Breakout"?
What are the advantages of decomposition in software development?
L2 Comprehension Questions
Short Answer: Define decomposition and explain why it is important in computational thinking.
Short Answer: Provide two examples of decomposition in daily life and describe how they simplify tasks.
Long Answer: Explain how decomposition can be applied to designing a game like "Breakout." Include at least four sub-tasks.
Short Answer: List two advantages of decomposition in programming and explain why they are beneficial.
Long Answer: Discuss how decomposition allows teams to work more efficiently and speeds up development time. Provide an example to illustrate your answer.
Understanding inputs, processes, and outputs is fundamental in computer science. These concepts allow us to break down problems into manageable steps, which can then be implemented in programs. In this worksheet, you will explore how to identify and use these concepts in problem-solving and programming tasks.
Key Terms
Input: Data received by the program to process.
Process: Actions or calculations performed on the input.
Output: Data produced by the program after processing.
Key Ideas
Understanding Inputs, Processes, and Outputs:
Inputs provide information or data to the system.
Processes act on the inputs to perform tasks or calculations.
Outputs deliver the results of the processes to the user.
Example: Calculating the volume of a fish tank based on its dimensions.
Applications:
Writing a program to analyze scores and calculate highest, lowest, and average.
Designing systems where data flow from input to output can be clearly tracked.
Steps for Analysis:
Identify the inputs needed for the program.
Define the processes (calculations, data transformations) required.
Determine the outputs that will satisfy the program’s goal.
Lesson Activities
Activity 1: Identify Inputs, Processes, and Outputs
For each of the following scenarios, identify the inputs, processes, and outputs:
A program calculates the area of a rectangle given its length and width.
A program takes a number as input and determines whether it is even or odd.
A program collects daily temperatures for a week and calculates the average temperature.
Activity 2: Design and Analyze
Write short, logical explanations (not code) for these tasks:
Design a program that asks the user for the dimensions of a cylindrical water tank and calculates its volume.
Create a process for collecting students’ test scores and reporting the highest score.
Explain the steps involved in creating a program that converts temperature from Celsius to Fahrenheit.
Comprehension Questions
Short Answer:
Define inputs, processes, and outputs in your own words.
Why is it important to identify inputs, processes, and outputs before writing a program?
Scenario-Based Question:
Given the task of calculating the area of a circle, describe the inputs, processes, and outputs required.
Long Answer:
Discuss the importance of clearly identifying inputs, processes, and outputs in the context of exam scenarios. Provide an example to illustrate your point.
Challenge Activity
Write a structured plan (inputs, processes, outputs) for a program that:
Asks the user for three exam scores.
Calculates the average of the scores.
Outputs a message indicating if the average score is above or below a pass mark of 50%.
Reflection
Why do you think breaking a problem into inputs, processes, and outputs makes programming easier? Write 2-3 sentences summarizing your thoughts.
Extension Task for L3: Inputs, Processes & Outputs
Imagine you are designing a program for a beachside dive shop to help customers rent scuba diving equipment. The program will calculate the total cost of equipment rental based on the customer's requirements. This is a planning task not a programming task.
Using your knowledge of inputs, processes, and outputs, create a structured plan for this program.
Steps to Complete:
Identify the inputs the program will need. Think about the types of equipment, rental duration, and customer information.
Define the processes the program must perform. Include calculations for total cost based on the equipment type and rental duration.
Determine the outputs the program will produce.This might be a total cost summary and rental details.
Write Your Plan:
Inputs: List all the data the user will provide.
Processes: Explain what the program will calculate or determine.
Outputs: Describe the results the user will see.
After I have approved your plan, you can begin programming your idea.
Algorithms are a key part of computer science, helping us solve problems step by step. To make them easier to understand and share, we can represent algorithms using pseudocode and flowcharts. Pseudocode uses plain language to describe each step, while flowcharts visually map out the process using symbols. In this lesson, you will learn how to use both methods to represent algorithms clearly and effectively. By the end, you'll be able to turn a set of instructions into a visual or written format that is easy to follow.
Learning Objective: Learn to use pseudocode and flowcharts to represent algorithms effectively.
Key Terms
Algorithm: A step-by-step set of instructions to solve a problem.
Pseudocode: A simple way to describe algorithms using structured but plain language.
Flowchart: A diagram that visually represents an algorithm using standard symbols.
Oval: Represents the start or end of a process in a flowchart.
Rectangle: Represents a process or instruction in a flowchart.
Diamond: Represents a decision or choice in a flowchart.
Key Ideas
What is an Algorithm?
An algorithm is a methodical set of steps to solve a specific task or problem. Algorithms can be expressed in multiple ways, including normal English, pseudocode and flowcharts.
Pseudocode
Written in structured language that resembles programming but is easier to read.
Example:
START
INPUT number
IF number > 10 THEN
OUTPUT "Greater than 10"
ELSE
OUTPUT "10 or less"
ENDIF
STOP
Flowcharts
Flowcharts are visual tools to represent an algorithm. The direction of travel through the flowchart must be indicated with arrows. Flowcharts use the following symbols:
Oval: Start or End
Rectangle: A process (e.g., calculation, action) or variable.
Diamond: A question or decision point (e.g., Yes/No or True/False)
Parallelogram: INPUT or OUTPUT of information from the program
Note-taking Guide
Title Section
Add the title: L4 - Representing Algorithms.
Key Terms Section
Create a section titled Key Terms.
Define each of the following: Algorithm, Pseudocode, Flowchart.
Add a small example or illustration for each term.
Pseudocode Section
Title this section Pseudocode.
Write what pseudocode is and why it’s useful.
Copy a pseudocode example and break it down in your own words.
Flowchart Section
Title this section Flowchart.
Using shapes in your slide, draw flowchart symbols (oval, rectangle, parallelogram, diamond) and label their purposes.
Include an example flowchart for a simple algorithm and explain it.
Comparison Section
Create a section titled Pseudocode vs. Flowchart.
Make a table comparing the two methods (e.g., how they’re written, how they’re used).
Reflection Section
Add a section titled Reflection.
Answer these questions:
Which method do you find easier to understand?
When might you use a flowchart instead of pseudocode?
Lesson Activities
Activity 1: Explore Real-Life Algorithms
Think of a real-life process you do daily (e.g., brushing your teeth, getting dressed).
Identify the input, process, and output of that activity.
Comprehension Questions
Why is it important to represent algorithms visually or in text form?
How do flowchart symbols help make algorithms easier to understand?
Rewrite this pseudocode to include additional temperature descriptions (cool, warm, very hot):
START
INPUT temperature
IF temperature < 0 THEN
OUTPUT "Freezing"
IF temperature > 30 THEN
OUTPUT "Hot"
ELSE
OUTPUT "Moderate"
STOP
Extension Tasks
Group Challenge
Work in pairs to design an algorithm and a flowchart for a vending machine:
Input: Money and item selection.
Process: Check if enough money is inserted and dispense the item.
Output: The selected item and change (if any).
Reflection
How would you explain the steps of creating a flowchart to a younger student?
Which algorithm representation (pseudocode or flowchart) would you use if you were designing a new app? Why?
Program Design
Create an algorithm and a flowchart for a program that calculates the area of different shapes (e.g., circle, square, rectangle).
Ask the user which shape they want to calculate.
Use a decision step to choose the correct formula for the shape.
Output the calculated area.
Learning Objective: I can understand the purpose and operation of linear and binary search algorithms, including writing pseudocode and comparing their efficiency.
Searching is a fundamental operation in computer science, allowing us to quickly locate specific data within a dataset. Imagine trying to find a name in a list of contacts or a file on your computer. Searching algorithms, such as linear search and binary search, provide systematic methods to solve these problems. In this lesson, you will explore these two algorithms, understand their differences, and practice representing them in pseudocode.
Key Terms
Searching Algorithm: A systematic way to find an item in a dataset.
Linear Search: Checks each item one by one until the target is found.
Binary Search: Efficiently searches by repeatedly dividing a sorted dataset in half.
Dataset: A collection of data items, often organized in a list or array.
Efficiency: How quickly an algorithm performs a task.
Key Ideas
Why Are Searching Algorithms Important?
Searching is part of everyday tasks, like locating a file or searching the web.
Algorithms help automate and speed up the process, especially with large datasets.
How Linear Search Works
Inspects each element one by one until it finds the target.
Advantages: Works on any dataset, even unsorted.
Disadvantages: Slow for large datasets.
Example: Looking for a book by scanning every shelf in the library.
How Binary Search Works
Requires the dataset to be sorted.
Cuts the dataset in half with each comparison, quickly narrowing down the possibilities.
Advantages: Faster than linear search with large datasets.
Disadvantages: Only works on sorted data.
Example: Finding a word in a dictionary by starting in the middle.
Comparison: Linear vs. Binary Search
Linear search is simple but slow for large datasets.
Binary search is efficient but needs sorted data.
Linear Search
Binary Search
L5 Note-taking Guide
Create a clear and comprehensive set of revision notes on linear and binary search algorithms using Google Slides.
Title Section
Add the title: Lesson 5 - Searching Algorithms.
Key Terms Section
Create a section titled Key Terms.
Define the following terms in your own words: Searching Algorithm, Linear Search, Binary Search, Dataset, Efficiency.
Linear Search Section
Title this section Linear Search.
Describe how linear search works.
Include a simple example of a linear search in a list, explaining each step.
Binary Search Section
Title this section Binary Search.
Describe how binary search works.
Explain why binary search only works on sorted datasets.
Include a simple example of a binary search and show the steps to find a number.
Comparison Section
Create a section titled Linear vs. Binary Search.
Make a table comparing the two algorithms (e.g., speed, dataset type, ease of use).
Example Section
Title this section Searching Example.
Create a simple list of numbers (e.g., [3, 7, 12, 19, 23]).
Write out the steps of both a linear search and a binary search to find the number 12.
Reflection Section
Add a section titled Reflection.
Answer the following questions:
Which search algorithm do you think is better for large datasets? Why?
When might you choose linear search instead of binary search?
What is the most important thing you learned in this lesson?
L5 Activities
Comprehension Questions
Use these questions to check and reinforce understanding of linear search and binary search, as well as general algorithmic thinking.
What is the difference between linear search and binary search?
Why can binary search only be used on sorted data?
Which search algorithm is generally faster for large datasets and why?
Explain the terms input, process, and output in the context of a search algorithm.
When would you choose linear search over binary search.
Extension Activities
Each activity focuses on producing and visualizing an algorithm in different formats. The goal is to understand and communicate how searching algorithms work.
Activity 1: Text-Based Description of the Algorithm
Choose either linear search or binary search (or both).
Write a short paragraph that explains how the algorithm works step by step, in your own words (no code, just a plain English explanation).
For example, describe how you would find 12 in the list [3, 7, 12, 19, 23] using linear search.
Include what happens when the target is found (or when the list ends without finding it).
Activity 2: Pseudocode
Using standard pseudocode conventions, write the algorithm you chose in a structured, step-by-step format.
Your pseudocode should include:
Start and Stop (or Begin/End)
Inputs (target and dataset)
Loops and Conditions (e.g., IF, ELSE, WHILE, etc.)
Outputs (“Found” or “Not Found”)
Activity 3: Flowchart
Create a flowchart to represent either linear or binary search.
Use standard flowchart symbols (oval for start/end, parallelogram for input/output, rectangle for process, diamond for decisions).
Ensure your flowchart clearly shows:
The decision points (e.g., “Is dataset[mid] = target?”)
The looping (going back to keep searching)
The output (“Found” or “Not Found”)
Tip: Draw the flowchart using shapes in your Slide. Focus on making it easy to follow.
Activity 4:
Write a short program (in pseudocode or a real language like Python) that does the following:
Asks the user for a list of numbers (ensure the list is sorted).
Asks the user for a target number to search for.
Implements both linear search and binary search to find the target.
Counts how many steps each search took.
Outputs one of the following:
“Linear Search: Found in X steps”
“Binary Search: Found in Y steps”
“Not Found” (if the target doesn’t exist in the list)
Reflect on which algorithm found the target faster and why.
Here are activities to help you prepare for the summative assessment on this unit.
1. Design a Lost Item Finder
Objective: Use abstraction, decomposition, and searching algorithms to solve a real-world problem.
Scenario: You lost your favorite book in your house, and you need a way to find it quickly. Design an algorithm to locate the book.
Instructions:
Abstraction
What are the key details? (e.g., the rooms to search, the book's description)
Ignore unnecessary details like what other items are in the rooms.
Decomposition
Break the task into smaller steps (e.g., "Check one room at a time").
Algorithm Representation
Create a flowchart or write pseudocode to show the steps in your algorithm.
Searching Algorithm:
Decide if you will use a linear search (searching one room at a time) or a binary search (if rooms are numbered and sorted).
Test the Algorithm:
Use an input-process-output table to show how your algorithm works step by step.
2. Create a Grocery Shopping Helper
Objective: Represent a process with pseudocode, flowcharts, and IPO tables.
Scenario:
Your friend keeps forgetting groceries when shopping. They want a program that checks their list to see if they bought all the items.
Instructions:
Inputs:
The grocery list (input from the user).
Items purchased.
Processes:
Compare the items purchased to the grocery list.
Identify missing items.
Outputs:
List of items still needed.
Tasks:
Draw a flowchart to represent the steps.
Write pseudocode to describe the algorithm.
Use an input-process-output table to show how the algorithm will work with sample data.
3. Plan a School Timetable Generator
Objective: Apply abstraction and decomposition to design a solution.
Scenario:
The school needs a program to generate a timetable for students with no overlapping lessons.
Instructions:
Abstraction:
Focus on the key details: classes, times, and available rooms.
Decomposition:
Break the problem into smaller tasks:
Collect inputs (class names, times, rooms).
Assign classes to times and rooms.
Check for overlaps.
Algorithm Representation:
Write pseudocode to represent the solution.
Use a flowchart to visualize the steps.
Final Task:
Create a small test with two students and two overlapping lessons.
Use an IPO table to show how the algorithm resolves the conflict.
4. Emergency Call Sorting
Objective: Practice binary and linear search.
Scenario:
An emergency call center needs to quickly find a caller's location based on a sorted list of addresses.
Instructions:
Binary Search:
Write pseudocode for a binary search algorithm to find a specific address.
Draw a flowchart to illustrate the steps.
Linear Search:
Write pseudocode for a linear search to achieve the same goal.
Compare Efficiency:
Explain when each search method would be better (e.g., for small or large datasets).
Test the Algorithm:
Use an input-process-output table to test both algorithms with a sample list of addresses.
5. Solve a Travel Planner Problem
Objective: Use algorithms to plan a trip.
Scenario:
You need to visit 5 cities and want the shortest route. Plan an algorithm to calculate this.
Instructions:
Abstraction:
Focus only on cities, distances, and a starting point.
Decomposition:
Break the task into smaller steps:
Input cities and distances.
Compare routes.
Choose the shortest.
Algorithm Representation:
Write pseudocode to solve the problem.
Use a flowchart to visualize the steps.
Bonus Challenge:
How could you improve this algorithm if there were more cities?