Computer Science
Grade 9
20 min
1. Introduction to Computational Thinking
Define computational thinking and its four key components: decomposition, pattern recognition, abstraction, and algorithms.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Analyze the efficiency of a simple algorithm using Big O notation.
Define and identify the base case and recursive case in a recursive function.
Trace the execution of a simple recursive algorithm.
Compare and contrast an iterative solution with a recursive solution for the same problem.
Explain the concept of parallel processing and identify tasks that can be parallelized.
Apply recursive thinking to decompose a problem into smaller, self-similar sub-problems.
Ever wonder how a GPS finds the fastest route out of millions of possibilities in just a few seconds? 🗺️ It's not magic, it's about making computers think smarter, not just harder!
In this lesson, we'll move beyond the basics of computational thinking to explore powerful, advanced t...
2
Key Concepts & Vocabulary
TermDefinitionExample
Algorithm EfficiencyA measure of how many resources (like time or memory) an algorithm uses in relation to the size of its input. A more efficient algorithm solves a problem faster or with less memory.Searching for a name in a phone book by checking every page one-by-one is less efficient than opening to the middle and narrowing it down (Binary Search).
Big O NotationA simplified, standardized way to describe an algorithm's efficiency in the worst-case scenario as the input size grows. It focuses on the overall growth rate.A loop that goes through an entire list of 'n' items has a Big O of O(n), read as 'Order n'. If you have two nested loops, it's often O(n^2).
RecursionA problem-solving technique where a function calls itself to solve...
3
Core Syntax & Patterns
The Structure of a Recursive Function
A recursive function must have at least two parts: 1. A Base Case that terminates the recursion. 2. A Recursive Case that calls the function again with an input that moves closer to the base case.
Use this pattern whenever you design a recursive solution. Always define the base case first to ensure the function will eventually stop.
Hierarchy of Common Big O Complexities
O(1) < O(log n) < O(n) < O(n log n) < O(n^2)
This rule helps you quickly compare the efficiency of different algorithms. An algorithm with a lower complexity is generally faster for large inputs. For example, an O(n) algorithm is much better than an O(n^2) algorithm.
Identifying Parallelizable Tasks
A problem can be parallelized if it can be broken down...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
The function `fib(n)` calculates the nth Fibonacci number recursively: `if n <= 1: return n; else: return fib(n-1) + fib(n-2);`. If you call `fib(4)`, how many times will the base case, `fib(1)`, be executed?
A.2 times
B.1 time
C.3 times
D.4 times
Challenging
A highly efficient search algorithm on a SORTED list works by repeatedly dividing the search interval in half. If the item is not the middle element, it continues the search in the half where the item could be. This is a recursive process. What is the Big O complexity of this algorithm (Binary Search)?
A.O(n)
B.O(log n)
C.O(1)
D.O(n^2)
Challenging
A student is trying to write a recursive factorial function. Which of the following snippets best demonstrates the 'Solving the Wrong Sub-problem' pitfall?
A.`def factorial(n): if n <= 1: return 1; else: return n * factorial(n-1);`
B.`def factorial(n): if n <= 1: return 1; else: return n + factorial(n-1);`
C.`def factorial(n): if n <= 1: return 1; else: return n * factorial(n);`
D.`def factorial(n): if n == 99: return 99; else: return n * factorial(n-1);`
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free