— notes — 8 min read
Pet Peeve: The author sometimes skips steps without an explaination (like the integer truncation in "stop and think: incremental correctness"). Some examples are hard to follow for an international student (like understanding the lottery system in "war story: pschic modeling").
An algorithmic problem
is specified by describing the complete set of instances it must work on and of its output after running on one of these instances.
An algorithm
is a procedure that takes any of the possible input instances and transforms it to the desired output.
There is a distinction between a general problem and an instance of a problem. E.g:
Problem: Sorting
Input: A sequence ofn
keys a1,...,an.
Output: The permutation (reordering) of the input sequence such that: a′1 ≤ a′2 ≤ ··· ≤ a′n−1 ≤ a′n.
Instance of sorting problem: { Mike, Bob, Sally}; { 154, 245 }
Insertion sort is an algorithm to the sorting problem: English description:
Start with a single element (thus forming a trivially sorted list) and then incrementally inserts the remaining elements so that the list stays sorted.
Pseudocode:
1array = input sequence2n = array size3i = 045while i < n6 j = i7 while j > 0 AND array[j] < array[j - 1]8 swap element at `j` with element at `j - 1` in array9 decrement j by 110 increment i by 1
Code:
1insertion_sort(item s[], int n)2 {3 int i,j; /* counters */4 for (i=0; i<n; i++) {5 j=i;6 7 while ((j>0) && (s[j] < s[j-1])) {8 swap(&s[j],&s[j-1]);9 j = j-1;10 }11 }12 }
An animation of the logical flow of this algorithm on a particular instance (the letters in the word “INSERTIONSORT”
)
There is a fundamental difference between algorithms, which always produce a correct result, and heuristics, which may usually do a good job but without providing any guarantee.
Three desirable properties for a good algorithm:
Correct algorithms usually come with a proof of correctness, which is an explanation of why we know that the algorithm must take every instance of the problem to the desired result.
Problem: Robot Tour Optimization (aka: Traveling Salesman Problem [TSP]).
Input: A setS
ofn
points in the plane.
Output: What is the shortest cycle tour that visits each point in the setS
?
Starting from some point
p0
, we walk first to its nearest neighborp1
Fromp1
, we walk to its nearest unvisited neighbor. Repeat this process until we run out of unvisited points After which we return top0
to close off the tour.
1NearestNeighbor(P)2 Pick and visit an initial point p₀ from P3 p = p₀4 i = 05 6 While there are still unvisited points7 i = i + 18 Select pᵢ to be the closest unvisited point to pᵢ₋₁9 Visit pᵢ10 Return to p₀ from pₙ₋₁
Repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge.
proof
.QED
at the bottom to denote that you have finished, representing the Latin phrase for "thus it is demonstrated."1* The set of allowed input instances.2* The required properties of the algorithm's
1* Asking an ill-defined question. E.g: Asking for the best route between two places on a map is a silly question, unless you define what best means.2* Creating compound goals. E.g: A goal like find the shortest route from **a** to **b** that doesn't use more than twice as many turns as necessary is perfectly well defined, but complicated to reason about and solve.
n
(that is, an integer n ≥ 0
) holds for all values of n
. The proof consists of two steps:n = k
, and prove that the statement holds for n = k + 1
.n = k
, is called the induction/inductive hypothesis. You're doing a thought experiment of what would happen if it was true for n = k
. It might be clearer to use the phrase "suppose true when n = k
" rather than "assume true when n = k
" to emphasise this.n = k
and then uses this assumption to prove that the statement holds for n = k + 1
. We try to manipulate the statement for n = k + 1
so that it involves the case for n = k
(which we assumed to be true).n - 1
elements of array A
are completely sorted after n - 1
iterations of insertion sort.x
to A
, we find where it goes, namely the unique
spot between the biggest element less than or equal to x
and the smallest element greater than x
. This is done by moving all the greater elements
back by one position, creating room for x
in the desired location. ■{1,4,3,2}
and {4,3,2,1}
are two distinct permutations of the same set of four integers.{1,3,4}
and {2}
are two distinct subsets of the first four integers. Order does not matter in subsets the way it does with permutations.Learning to think recursively is learning to look for big things that are made from smaller things of exactly the same type as the big thing.
If you think of houses as sets of rooms, then adding or deleting a room still leaves a house behind.
n
things {1, ..., n}
and you get a permutation of the remaining n-1
things. Basis case: {}{1, ..., n}
contains a subset of (1, ..., n - 1)
obtained by deleting element n
. Basis case: {}Recursive decompositions of combinatorial objects. (left column) Permutations, subsets, trees, and graphs. (right column) Point sets, polygons, and stringsRecursive descriptions of objects require both decomposition rules and basis cases, namely the specification of the smallest and simplest objects where the decomposition stops.
m
, which can be listed as p₁,..., pₘ
. So let's assume this is the case and work with it.N
has the property that it is divisible by each and every one of the known primes, because of how it was built.N + 1
. It can't be divisible by p₁ = 2
, because N
is.p₂ = 3
and every other listed prime. Since a +1 can’t be evenly split by any of the prime numbers because they are bigger.N + 1
doesn't have any non-trivial factor, this means it must be prime.m
prime numbers, none of which are N + 1
, because N + 1 > m
.Show that a + b
can be less than min(a, b)
.
When:
a and b < 0
(i.e: negative)
a <= b
Then:
min(a, b) = a
a + b < a
Example:
min(-6, -5) = -6
-6 + -5 = -6 -5 = -11
-11 < -6
Show that a × b
can be less than min(a, b)
.
When:
a < 0
(i.e: negative)
b > 0
(i.e: positive)
Then:
min(a, b) = a
a * b < a
Example:
min(-3, 4) = -3
-3 * 4 = -12
-12 < -3
Design/draw a road network with two points a and b such that the fastest route between a and b is not the shortest route.
1a──────c──────b2│ │3│ │4└────d────────┘56Route `acb` have a toll gate, is in development and have a speed limit.7Route `adb` is longer, but has none of these impediment.89Route `adb` will be faster than the shorter `acb` route.
Design/draw a road network with two points a and b such that the shortest route between a and b is not the route with the fewest turns.
1a────┐ ┌────b2│ └─c─┘ │3│ │4└──────d──────┘56Route `acb` is the shortest but has 4 turns.7Route `adb` is the longest and has only 2 turns.