Exercises: Algorithms and computational thinking

Write the algorithm, as a numbered list of steps, to make a cheese sandwich, so that a person who has never made one can follow it without doubt. Review your list and check that no steps you took for granted are missing.

These steps of the "going to school" algorithm are out of order: (a) enter the classroom, (b) get up, (c) have breakfast, (d) leave the house, (e) get dressed, (f) walk to school. Put them in the correct order and add a decision to the algorithm: what to do if it is raining when leaving the house.

The figure shows, using interlocking blocks, the algorithm for an automatic reading lamp that should turn on only when light is low, but one block is missing.

Indicate which block you would place in the gap and explain in your own words how the complete algorithm works, step by step.

Many everyday appliances follow algorithms. Choose two from this list — washing machine, microwave, traffic lights — and describe for each what data it receives (input), what it decides or repeats (process), and what it does at the end (output).

Write the algorithm for preparing a glass of chocolate milk in six to eight steps, so precise that a robot could follow them: quantities, order of steps, and how to check that the cocoa has dissolved before finishing.

Read this algorithm: (1) pick up the deck of cards, (2) while cards remain in your hand, deal one to each player starting on your left, (3) when no cards remain, announce "dealt". Explain in one sentence what the algorithm does and point out which part is the loop and when it terminates.

In the "frying an egg" recipe, identify the input (ingredients and utensils), the process (steps involving heat and the frying pan), and the output (the result). Explain why thinking in this way helps to write clear algorithms.

A recipe says "stir the sauce until it thickens". Explain why an algorithm must always terminate and what could happen if the sauce never thickens. Rewrite that step so that the cook does not end up stirring forever.

Decompose the problem "organizing the end-of-year party" into four smaller sub-problems and write two concrete steps to solve each one. Explain the advantage of breaking down a large problem in this way.

To sort a deck of cards there are several different algorithms, and some are faster than others. Explain with an everyday example how the same problem can be solved by multiple algorithms and what it means for one to be "better" than another.

A recipe says: "add salt and simmer for a while on medium heat". Explain why a computer could not follow that instruction and rewrite it as a precise algorithm step, stating quantities, timings, and how to check that the step is complete.

Recognizing patterns means finding the repeating rule. Find the pattern in these three sequences and express it as a clear rule: (a) 5, 10, 15, 20, ..., (b) 100, 90, 80, 70, ..., (c) Monday: 1 push-up, Tuesday: 2, Wednesday: 4, Thursday: 8, ... State what value would come next in each one.

A subway map does not draw the real city: it removes distances, curves, and streets, keeping only stations and connections. Explain what abstraction is using this example and then apply it to the floor plan of your school: which three features would you include and which three would you remove?

You can do it on paper and send a photo with your answer.

Trace this algorithm with $n = 7$: (1) start with the value of $n$, (2) repeat three times: add 2, (3) subtract 5, (4) write the result. Write down the value after each step, give the final result, and explain what a trace is and why performing it by hand is useful.

This "doing the laundry" algorithm contains a bug: (1) put all clothes into the washing machine, white and colored together, (2) add detergent, (3) choose the long hot-water program, (4) hang out to dry. Find two problematic steps, explain what could go wrong in each, and rewrite the corrected algorithm including a prior sorting step.

Write the algorithm to count how many people enter through the classroom door using only a "counter" variable starting at 0: what you do each time someone enters, how you know when to stop counting, and what value the counter will have at the end.

Design the complete algorithm, with numbered steps that include decisions and loops, for a crosswalk with a button: what happens from when someone presses the button until the lights return to their initial state, including the timings for each light.

Think of a program that plays tic-tac-toe. Describe the strategy it would follow on each turn: what board data it must inspect, in what order, and what rules you would use to decide where to place the mark. There is no need to write code: state the rules in natural language.

The algorithm for a cafeteria hands out a sandwich to each attendee, but fails when there are more attendees than sandwiches. Explain what an "edge case" is in an algorithm, propose how distribution should behave in that situation, and rewrite the problematic step so that the algorithm does not fail.

The figure shows, using interlocking blocks, the skeleton of a secret number guessing game, but inside the loop a piece is missing so that the game can give clues to the player.

Describe which block (or blocks) you would place in the gap so that the game tells the player whether their number is greater or smaller than the secret number, and explain the complete operation of the algorithm: what is repeated, when it terminates, and what happens if the player gets it right on the first try.

You are looking for a word in a 500-page dictionary. Compare these two algorithms: opening at the first page and advancing one page at a time, or opening in the middle and discarding the unneeded half. Explain which is more efficient, why it only works if the pages are sorted, and estimate how many "page openings" each method requires.

Two people prepare breakfast together for four guests: coffee needs to be made, bread toasted, juice squeezed, and the table set. Divide the tasks between the two while respecting dependencies (you cannot serve coffee before making it) and explain which tasks can be done simultaneously and which cannot, giving their order.

An ATM only contains $\$20$ bills and its algorithm dispenses the requested amount in bills. Explain what happens when someone requests $\$75$, why this is an edge case, and rewrite the ATM rules so that it always provides a sensible response.

Two algorithms are proposed for classroom recycling: (a) each day, the person responsible sorts all the day's trash into three bins, and (b) each week, in turns, a pair sorts everything accumulated. Evaluate both against criteria of total time, sorting errors, and distribution of effort, and choose one with justification.