Programming Lab

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

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

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

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

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

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

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