Programming Lab

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

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

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

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

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