Algorithms and Computational Thinking

Thinking like a computer scientist

Before you write a single line of code, you have to work out a clear plan for solving the problem. That planning is what computational thinking is all about. This module works through the whole picture: - Computational thinking: decomposition and abstraction.\n- Designing algorithms: pseudocode and flowcharts.\n- Standard algorithms: searching and sorting.\n- Efficiency: why some algorithms are far faster than others. Writing actual programs in a language is covered in another module. Here the focus is the thinking and the algorithms behind the code.

Words for algorithms

Five terms you need before you use them. Learn what each one means.

Match each idea to what it does

Linear search against binary search

Both search algorithms find an item in a list, but they work in very different ways, and each suits a different situation.

Which search needs a sorted list?

A programmer wants to use binary search on a list. What must be true of the list first?

• The list must already be sorted into order
• The list must be completely empty
• The list must be in a random order
• The list must contain only one item

Tap the two computational thinking skills

Tap the TWO skills that are part of computational thinking.

• Decomposition
• Abstraction
• Guessing the answer at random
• Copying another program without thinking

Comparing how fast algorithms run

Two algorithms can solve the very same problem, yet one takes far fewer steps than the other. That difference is what we mean by efficiency. A more efficient algorithm reaches the answer in fewer steps and often uses less memory. Binary search, for example, halves the list each time, so on a long list it needs far fewer checks than checking every item in turn. Efficiency matters most as the amount of data grows. On a handful of items the difference is tiny, but on millions of items a wasteful method can be hopelessly slow while a clever one stays quick.

Pick the true facts about algorithms

Select the TWO statements that are true.

• Decomposition breaks a problem into smaller parts
• Binary search needs the list to be sorted
• Linear search is always faster than binary search
• Abstraction means adding as much detail as possible

Order the steps of a binary search

Put the steps of a binary search on a sorted list in a sensible order.

• Look at the middle item of the sorted list
• Compare the target with the middle item
• If the target is smaller, keep the lower half
• If the target is larger, keep the upper half
• Repeat until the target is found or none remain

Sorting a hand of cards

Follow how bubble sort puts a row of numbered cards into order, the same way you might tidy a hand of cards. The idea: compare the first two cards. If the left one is bigger, swap them so the smaller comes first. Moving along: step one place to the right and compare the next pair, swapping if needed, all the way to the end. After one pass, the biggest card has bubbled to the far right. Again and again: repeat the passes. Each pass settles one more card into place, and the row gets closer to being in order. Knowing when to stop: when a full pass makes no swaps at all, the cards are in order and the job is done.

Complete the algorithm facts

A precise sequence of steps that solves a problem is an _____. Breaking a problem into smaller parts is _____. Removing unnecessary detail to focus on what matters is _____. A search that repeatedly halves a sorted list is a _____ search.

Trace the algorithm

An algorithm starts with total set to 0. It adds 4, then adds 6, then multiplies the total by 3. Work out the final value of total.

Build an algorithm point

Choose the words that complete this statement about algorithms.

Choose the right approach

Read each situation and choose the best computational approach, then think about why.

• You must search an unsorted list of names for one particular name. Which search works?
• A problem is large and complicated. What is a good first step?
• While designing an algorithm you want to ignore details that do not matter yet. What is this called?

Explain algorithms and computational thinking

A classmate is new to computer science. Explain algorithms and computational thinking using what this module has covered.

• Explain what an algorithm is
• Explain decomposition and abstraction with an example
• Explain the difference between linear search and binary search
• Explain one way to make an algorithm more efficient
• Finish by explaining why sorted data helps searching