Programming Lab

Variables are labelled boxes

A variable is a named box that holds one value; an assignment works out the right-hand side and puts the answer in the box, replacing what was there, and the program uses the latest value

From decimal to binary

Repeatedly dividing a number by 2 gives its binary digits as the remainders, from the last bit to the first; each remainder is placed one place further left

Words backwards: palindromes

A string is a list of characters with indexes from 0; a loop can visit each one in turn, and two pointers moving in from both ends test a palindrome with only half as many comparisons

Can we play outside? AND, OR and NOT

NOT turns true into false; AND is true only when both parts are true; OR is true when at least one part is true, so a long condition can be worked out one part at a time

If it rains, take an umbrella

An if / else statement checks a condition: when it is true the program runs the then part, otherwise the else part, never both

Is it a leap year?

A year is a leap year when it divides by 4 and not by 100, or when it divides by 400; the remainder % tests divisibility and AND / OR join the rules into one condition

Three tries for a PIN

A loop condition joined with AND stops as soon as either part is false: here when the PIN is right or when three tries are used up

Did the student pass?

Conditions can be joined with AND (all must be true) and OR (one is enough), and an if / else can sit inside another, so the program checks one question after another until one is true

Adding the digits of a number

n % 10 is the last digit of n and floor(n / 10) is n without it, so a while loop that repeats both until n is 0 visits every digit once

FizzBuzz: loops, % and decisions

A loop can make a decision on every repeat: i % 3 == 0 is true when 3 divides i exactly, and in a chain of ELSE IFs the first true check wins, so the most special case must come first

Repeat with a loop

A loop repeats the same lines: a for loop runs once for each value of its counter, an accumulator adds something on every repeat, and a while loop repeats until its condition becomes false

Saving up with a while loop

A while loop repeats its body as long as its condition is true, so the body must change something that makes the condition false in the end, or the loop never stops

A times table with nested loops

In nested loops the inner loop runs all the way through for every turn of the outer loop, so a table of r rows and c columns has r × c products

Star patterns with nested loops

In nested loops the inner loop runs completely for every turn of the outer loop; when the inner loop goes from 1 to row, row r prints r stars and n rows print n(n + 1)/2 stars

Lists and their positions

A list (array) keeps items in order; each item has an index, counted from 0, so a list of n items has indexes 0 to n − 1

A linked list is a train

A linked list stores each item in a node with a link to the next node; adding at the front is instant, but reaching node i means following i links from the head

A stack of plates (last in, first out)

A stack keeps items in a pile: push puts an item on the top, pop takes the top item off and peek only looks at it, so the last item in is the first one out (LIFO)

A ticket queue (first in, first out)

A queue keeps items in a line: enqueue adds an item at the rear, dequeue takes the item at the front and front only looks at it, so the first item in is the first one out (FIFO)

Rows and columns: 2-D arrays

A two-dimensional array is a list of rows, each a list of values; grid[row][col] picks one value, a loop along a row or down a column adds them up, and two nested loops visit every cell

Binary search trees

In a binary search tree every number on a node's left is smaller and every number on its right is bigger, so a search throws away half the tree at each step, but only while the tree stays bushy and short

Do the brackets match?

To check brackets, push each opening bracket on a stack; a closing bracket must match the bracket on top, which is popped; at the end the stack must be empty

Hash tables: finding a name at once

A hash table turns each key into a bucket number with a hash function; adding and finding a key look in that one bucket, so they stay fast however many keys there are, as long as collisions are few

Visiting a tree: pre, in and post order

A traversal visits every node of a tree once; pre-order visits a node before its children, in-order between its left and right children, post-order after them, and level order row by row with a queue

Find it one by one

Linear search compares the target with each item in order; it needs 1 comparison at best and as many as there are items at worst, or when the target is missing

Bubble sort, swap by swap

Bubble sort compares each pair of neighbours and swaps them when they are in the wrong order; each pass carries the largest number left to the end, and a pass with no swaps means the list is sorted

Degrees of separation

A network of friends is a graph; when every link counts as 1, the shortest path is the fewest links, found by settling people in order of how many links away they are, nearest first

Giving change with the fewest notes

A greedy algorithm makes the best-looking choice at each step: for change, it gives the largest note that still fits, again and again, until nothing is left

Insertion sort: like sorting playing cards

Insertion sort keeps a sorted part on the left and inserts the next number into it by sliding it past every bigger number; on a list that is nearly sorted it does very little work

Is it a prime number?

A number is prime when only 1 and itself divide it; a program tests divisors with %, stops at the first one that divides, and only needs to try divisors up to the square root, because any bigger factor comes with a smaller partner

Selection sort: find the smallest

Selection sort looks through the unsorted part for the smallest number and swaps it into the next place at the front; it always makes the same number of comparisons, but at most one swap per pass

BFS and DFS: searching a maze

Breadth-first search (BFS) visits cells in order of distance using a queue, so its path is always a shortest one; depth-first search (DFS) follows one way as far as it can using a stack, so its path can be longer

Linear or binary search?

Binary search compares the target with the middle of a sorted list and throws away the half it cannot be in, so 16 items need at most 5 comparisons instead of 16; it only works on sorted input

Merge sort: divide and conquer

Merge sort divides the list into halves until each part has one number, then merges sorted parts by always taking the smaller front number; its comparisons grow like n log n, far slower than the n² of bubble sort

The shortest road between towns

Dijkstra's algorithm settles towns in order of their distance from the start; each settled town's distance is final, and trying the roads out of it can only make the other towns' distances shorter

A function that converts temperatures

A function keeps a rule in one place: to_fahrenheit(c) returns c × 9 ÷ 5 + 32, and every call gives it a new argument for its parameter c

Euclid's GCD with recursion

Euclid's rule gcd(a, b) = gcd(b, a % b) makes the numbers smaller at every call, so a recursive function reaches its base case, b = 0, where the answer is a

Functions: a machine for areas

A function is a named set of steps written once and used many times: its parameters receive the arguments of each call, and return sends its answer back to where it was called

Fibonacci: when recursion repeats itself

fib(n) = fib(n − 1) + fib(n − 2) with fib(0) = 0 and fib(1) = 1; because each call makes two more, the number of calls grows very fast, and the same answers are worked out many times

Recursion: a function that calls itself

A recursive function solves a problem by calling itself on a smaller version of it; a base case answers the smallest version directly, so the calls stop and the answers come back up the call stack

The Tower of Hanoi

To move n disks, move the top n − 1 out of the way, move the biggest, then move the n − 1 back on top; the same plan solves the smaller towers, so the moves double and add one each time: 2ⁿ − 1

A traffic light is a state machine

A state machine is always in one of a few states and moves to the next state by a rule; a traffic light keeps its state in a variable and goes round red, green, yellow with (state + 1) % 3

Help the robot reach the battery

An algorithm is a list of exact steps done in order; changing the order or one step changes the result, and debugging means finding the step where the plan breaks

A secret code: the Caesar cipher

A Caesar cipher replaces each letter with the letter a fixed number of places (the shift) further along the alphabet, going round from Z back to A; shifting back by the same number decodes it

Plan a route through a maze

A big problem is easier when it is broken into small parts (decomposition); each part becomes a few steps, and a mistake in one part, such as one move too many, breaks the whole plan

Guess my number in seven tries

Halving the range each time finds any number from 1 to 100 in at most 7 guesses, because 7 halvings are enough to shrink 100 numbers to 1 (2⁷ = 128): the idea behind binary search

Climbing stairs: remember, don't repeat

Dynamic programming solves a big problem from the answers to smaller ones and remembers them: the ways to climb n stairs are the ways for n − 1 plus the ways for n − 2

How fast does the work grow?

The work a program does grows with its input: one loop over n items takes about n steps, a loop inside a loop takes n × n, and halving n each time takes only about log₂ n; Big O names this growth

The Big O race

Big O describes how an algorithm's steps grow with the size of its input n: O(1) stays the same, O(log n) grows by one when n doubles, O(n) doubles, O(n log n) a little more than doubles, and O(n²) quadruples