Computer Science notes ⇒ Algorithms and Data Structures

You can be formal about correctness using predicates and set theory, but in ADS, we shall be semi-formal and informal.

An invariant is a property of a data structure that is true at every stable point (e.g., immediately before and after the body of a loop (for loop invariant), the procedues and functions of an ADT (for data invariant)).

The first suggested solution has invariant and terminates when i = n. The other two algorithms are correct by the laws of arithmetic. Although all 3 algorithms are correct, none can be correctly implemented due to finite limitations. The way to find out which algorithm is better than others is by measuring resource usage. For our solution: T1 = λn · (2i + a + t)n + (2a + t) and T2 = T3 = λn · m + i + d. i is the time to increment by 1, a is the time to assign a value, t is the time to perform the loop test, m is the time to multiply two numbers and d is the time to divide by 2.

Therefore, we can see that the time resource usage for the second and third algorithms is constant and for the first algorithm it is linear. If we plotted a graph of T1 against T2 (and T3) we see that for a finite value of n then T1 has less usage, but for an infinite value of n T1 has greater usage. From this, we can assume that either T2 or T3 are the better algorithms.

∃n₀, c . n₀ ∈ N ^ c ∈ R⁺ ^ ∀n . n₀ ≤ n ⇒ fn ≤ c.(gn)

This can also be written as f = Ο(g). However, this means there is an ordering between f and g (not an equality).

f = Ο(g) means that f grows no faster than g. From this, we can create the related definitions:

• f = Ω(g) - f grows no slower than g. g = Ο(f)
• f = Θ(g) - f grows at the same rate as g. f = Ο(g) ^ f = Ω(g)
• f = ο(g) - f grows slower than g. f = Ο(g) ^ f ≠ Θ(g).
• f = ω(g) - f grows faster than g. f = Ω(g) ^ f ≠ Θ(g).

For asymptotic complexity, given functions f, g and h, we can say they have the properties of being reflexive and transitive, therefore the relation _ = Ο(_) is a preorder.

Another property we can consider is symmetry.

λn · 1 = Ο(λn · 2) (take n₀ = 0 and c = 1). Also, λn · 2 = Ο(λn · 1) (take n₀ = 0 and c = 2). This proves that Ο(_) is not antisymmetric.

To shorten down these expressions, it is traditional to drop the λn, so λn · 1 becomes just 1.

We can also combine functions, so:

• f = Ο(g) => g + f = Θ(g)
  This allows us to drop low-order terms, e.g., 7n = Ο(3n²) => 3n² + 7n = Θ(3n²)
• f = Ο(g) ^ h = Ο(k) => f × h = Ο(g × k)
  This allows us to drop constants, e.g., 3 = Θ(1), so 3n² = Θ(1n²)

We can also combine these laws to get such things as 3n² + 7n = Θ(n²).

There are also two special laws for dealing with logarithms:

• 1 = n⁰ = ο(log n)
• ∀r, r ∈ R⁺ ⇒ log n = ο(n^r)

From these rules, we derive most of what we need to know about _ = Ο(_) and its relatives.

In general, we can simplify a polynomial to be an ordering between the polynomial and it's largest term, also, we can treat log n as lying between n⁰ and n^r for every positive r.

We can class functions according to their complexity into various classes:

The f(kn) column shows how multiplying the input size by k affects the amount of resource, t, used.

For our example problem 1, how many times is fp = x executed with input size of n = (z - a) + 1? In the best case, this is 1 (x is found immediately), however in the worst case, this is n. Thus we can say that the complexity class is linear.

The average case time depends on assumptions about probability distribution of inputs. In practice, the worst case is more useful.

This is an concrete data structure, where each item in an array directly follows another. The advantage of this method is that the component address can be calculated in constant time, but it is inflexible (you need to find a whole block of spare storage that can hold all you want to store in one long row)

This is also a concrete data structure. We already covered pointers in PoP. To lookup the pth item in a pointer structure requires p lookups, so this example is linear in p. Extra space is also used for pointers, however, it is flexible (can easily fit in spare space, things can be added to and from it easily using new pointers, etc...

Choose a concrete data structure to support the abstract concept, and algorithmns to support operations over this structure, such that a good balance of efficiency is acheived. It may be that we need to sacrifice the efficiency of less common operations to make the more common ones more efficient.

This is a machine-level structure with a fixed number of cells, all of the same type. Each cell can store one value and is identified by an address. The time taken to access a cell is independent of the address of the cell, the size of the array and the content of the array.

Models

Is a value present?

Value lookup

Enter

Deletion

A linked list is a machine level structure with a variable number of cells, all of the same type. Each cell stores one value, and the address of the next value, so a cell is found by following pointers.The time to access a cell is linearly dependent on the position of the cell in the list, but independent of the length of the list or its contents. We already implemented linked lists in PoP.

Is a value present?

Value lookup

Enter

Deletion

If you model the pairs so that for any array indeces i and j there is an ordering on i and j, you can use binary search, a logarithmic algorithm (an improvement over linear), for the is_present and lookup functions.

Enter

Deletion

is_present and lookup can't use binary search, as we can't find the middle of the list in constant time. We have to use linear search, but we can terminate earlier if we pass the point where it would be in the ordering, rather than going straight to the end.

Enter

Deletion

s is the number of distinct keys in the dictionary. l is the length of the list.

For the ordered list, l = s. Additionally, leading constants change between the types, so where complexities appear the same, the leading constants could be much different. The exact value of the constants depends on the details of the implementation. Additionally, the array solution can waste space, as l must be allocated, and l > s.

Bags are sometimes called multisets. They are similar to sets. Sets have members, but bags have the same member more than once (multiplicity) - however order is not important so it is not a series.

• a,b,bis a bag with 1 copy of a and 2 copies of b.
• a,b,ais a bag with 2 copies of a and 1 copy of b.
• is an empty bag.

If we had the concept of the most important element in a bag, then we might have two operations: enter(b,i) and remove_most_important(b). We will also need is_empty(b), is_full(b), size(b), etc..., for completeness.

If the highest priority is youngest first, then this is a stack (LIFO) structure. enter and remove is normally called push and pop respectively. If the oldest is the highest priority, this is called a queue (FIFO) and enter and remove are normally called enqueue and dequeue respectively.

Nodes carry data and are connected by branches. In some schemes only leaf nodes or only interior nodes (including the root) carry data. Each node has a branching degree and a height (aka depth) from the root.

Operations on a tree include:

• Get data at root n
• Get subtree t from root n
• Insert new branch b and leaf l at root n.
• Get parent node (apart from when at root) - this is not always implemented.

These operations can be combined to get any data, or insert a new branch and leaf.

A binary tree is a tree with nodes of degree at most two, and no data in the leaves. The subtrees are called the left and right subtrees (rather than 'subtree 0' and 'subtree 1'). An ordered binary tree is one which is either an empty leaf, or stores a datum at the root and:

• all the data in the left subtree are smaller than the datum at the root,
• all the data in the right tree are larger than the datum at the root, and
• any subtree is itself an ordered binary tree.

Usual implementations use pointers to model branches, and records to model nodes. Null pointers can be used to represent nodes with no data. As mentioned earlier, array implementations can be used, but they are normally messy.

An ordered dictionary can be used to implement a binary tree. Such a tree would be structured like this:

These trees combine advantages of an ordered array and a list. The complexity to traverse a complete tree is log₂ n, however this is only if the tree is perfectly balanced. A completely unbalanced tree will have the properties of an ordered list and will therefore by linear.

When we are considering trees, we should now consider three data invariants:

• order
• binary
• balance

For more info on
red-black, see CLRS
or Wikipedia

There are two common balance conditions: Adelson-Velsky & Landis (AVL) trees, which allow sibling subtrees to differ in height by at most 1 and red/black trees, which allow paths for nodes to differ a little (branches are either red or black - black branches count 1, red branches count 0 and at most 50% can be red).

In AVL trees, searching and inserts are the same as before, but in the case of inserts, if a tree is unbalanced afterwards, then the tree must be rebalanced.

Rebalancing

Deletion from a binary tree

These are sometimes called B-trees, which is technically incorrect. B⁺ trees are slightly different to binary trees in that the key and data are seperated. B⁺-trees are commonly used in disks.

The invariants for a B⁺ tree are:

• all leaves are at the same depth (highly-balanced)
• root is a leaf or has 2..M children.
• non-root non-left nodes have ⌈m/2⌉..m descendantrs
• ordered

If m = 3 (as above), this is sometimes called a 2-3 tree. If m = 4, this is called a 2-3-4 tree.

Insertion

For efficient merging, we need to use a structure called a binomial queue. A binomial queue is a forest of heap-ordered binomial trees, with at most 1 tree of each height.

Binomial Trees

To merge two queues together, we add two forests together (as in binary addition). However, as we can have at most 1 trees, some trees need to be "carried" (combined with the next tree up). This process is linear in the number of nodes.

Insertion

Removing

We have an array of small dictionaries, normally implemented using a linked list, so when a collision occurs, it is added to the dictionary.

To consider efficiency, we need to conside the loading factor (λ), which is the number of entries ÷ the number of cells. For open hashing, λ ≤ 1 (assuming a good hash function), making our average list length 1. Therefore, on average, all operations are Θ(1).

In closed hashing, a key points to a sequence of locations and there are several varients of closed hashing.

Linear Probe

Quadratic Probing

Double Hashing

The first portion of the array is sorted and the second part isn't, but is known to be all larger than the front portion.

To sort, the smaller value should be selected from the back portion, and the first element of the back portion should be swapped with it.

The figure out the efficiency of this, you need to figure out the number of comparisons to be made. This will be (n-1) + (n-2)+ ... + i, which is Σ^n-1_i=0 i, which is Θ(n²) always. In the worst case, Θ(n) swaps need to be made.

Like selection, but the back is not necessarily related to the front (it can be any size).

To sort, you take the first value of the back portion and insert it into the front portion in the correct place.

The efficiency of the comparisons in the worst case is 1 + 2 + 3 ... + n which gives us the Σ^n-1_i=0 i formula again, which is Θ(n²) . However, in the worse case, comparisons are only Θ(n). The efficiency of the swaps at best is 0, but in the worst case this is Θ(n²), however this doesn't happen often (only if the list is reverse ordered).

We could have used binary search here, which would have theoretically improved the time to find the insertion point, but due to a high leading constant this makes it poor in practice.

This sorting algorithm is good for small lists - it has a small leading constant so the Θ(n²) isn't too bad. However, it is also good for nearly ordered lists, where the efficiency is likely to be nearly linear.

The heap has already been covered when we did priority queues.

1. Every element is put in a heap priority queue (any implementation will do, but a heap is fast).
2. Remove every element and place in successive positions in a, our sorted array.

n elements are inserted in log n time and n elements are removed in log n times, so n log n + n log n = Θ(n log n).

However, heap sort is not very memory efficient due to duplicating arrays. Also, it has a very high leading constant.

This algorithm deals with sorting three sets of data. You have an array of data sorted into 4 partitions, 3 of known type and one of unknown. The partitions are ordered so the unknown type is the third one.

To sort, the first element in the unknown type is compared. If it's part of the first partition, the first element of the second partition is swapped with it, moving the second partition along one and growing the first partition. If it's part of the second partition, it's left where it is and the pointer moves on. If it's part of the last partition, it's swapped with the last member of the unknown partition, hence shrinking the unknown partition and growing the final known partition by one.

Quicksort was invented by Sir Charles Antony Richard Hoare and it consists of series of sorted areas and unsorted areas, where the unsorted areas are of a known size laying between the two sorted areas.

The starting and finishing states are special instances of the above invarient. The starting state is where the unsorted area is of size n and the sorted area is of size 0, whereas the finished state is where the unsorted area is of size n and the sorted area is of size 0.

The first step sorts to where there are three areas, of which the middle one is called the pivot. Everything before the pivot is known to smaller than the pivot, and everything after the pivot is known to be larger than the pivot - this is accomplished using the Dutch National Flag algorithm. Each unsorted section is then sorted again using this mechanism, until the array is totally sorted.

A binary tree could be used to implement Quicksort.

This is called a divide and conquery mechanism as it runs in parallel. The Quicksort gives an average time of n log n, and this is the first sorting algorithm that did this. However, in the worst case, this could be n² if a bad pivot (either the smallest or largest thing in the array) is chosen, although the worst case is pretty rare.

If we use a sensible pivot, we can improve the efficiency of Quicksort. A way to do this in constant time is to use the 'median-of-three' method. This is picking the first, middle and last values from the unsorted secitons and then using the median of these values as the pivot. We don't waste any comparisons here either, as the other 2 compared values can then be sorted based on their relationship to the median.

Older textbooks may give the advice to implement Quicksort using your own recursive methods, however in modern computing this is not a good idea, as optimising compilers are often better than humans and this improves the leading constant.

For small arrays, quicksort is not so good, so if the array is short (e.g., less than 10), then insertion sort should be used. Insertion sort could also be used as part of the Quicksort mechanism for the final steps.

Overall, Quicksort is a very good algorithm: Θ(n log n)

This is also a divide and conquer mechanism, but works in the opposite way to Quicksort. Here, an array consists of some sorted arrays with no relationship between them. The first state consists of n sorted arrays, each of length 1 and the final state consists of 1 sorted array of length n. Two sorted arrays are merged to create a larger sorted array and this is repeated until a final sorted array is reached.

This is also Θ(n log n), but it is always this complexity. Merge sort is very good for dealing with linked lists, but it does require a lot of space.

This was invented by Donald Shell, but is sometimes called just 'Shell sort'. It is a divide and conquer algorithm based on insertion sort.

Shell's sort breaks up the array into lots of little lists (e.g., each one consisting of every 4th element) and an insertion sort is done on those elements (in-place of the main list) to get a nearly ordered list which can then be efficiently sorted.

Shell used increments of 2^k, where k gives us suitably small values for the initial sort, and this gives us Θ(n²) in the worst case.

However, Hibbard noticed that you didn't need to use a divide and conquer mechanism in this case, so we could use increments of 2^k-1, which gives us Θ(n^3/2) in the worst case and Θ(n^5/4) on average.

Sedgewick recommended using overlapping for further improvements, and this gives us Θ(n^4/3) in the worst case and Θ(n^5/6) on average, which is very close to n log n.

To do bucket sort, you need to produce a bag consisting of buckets (these buckets contain either the number of elements it represents, as in the Dutch National Flag problem, or a linked list of values, as in Quicksort). Then you produce an array that is an ordered version of the bag.

This algorithm is Θ(n), which is faster than Θ(n log n), however this is not a general sorting problem, as we must know beforehand what the possible values are. Bucket sort is therefore poor for general lists, or lists where there's a large number of keys, as it requires a lot of memory.

Amortised analysis is finding the average running time per operation over a worst-case sequence of operations. Because we're considering a sequence, rather than a single operation, then optimisations from earlier path compressions can be considered.

For this structure, we have Ο(m log^*n). The definition of log^*n is log^*n = 0 if log n < 1, else log^*n = 1 + log^*(log n). This is a very, very slow growing operation that gives us a value very close to m (linear).

Each cell contains the distance between two points, e.g.,

This tells us (for example) that from A to C, this has weighting 9. This kind of structure has a space complexity of Θ(v²), where v is the number of vertices, but it does have a lookup complexity of Θ(1).

In the real world, most graphs have a large v and a small e (number of edges), so we could construct an array of linked lists and information is stored in the same way as an adjacancy matrix, except where no arc exists then this entry does not exist in the linked list. This gives us something that looks like this:

This has a space complexity of Θ(v + e), which is linear in the sum of v and e and an access complexity of Θ(e) - although this has a very small leading constant.

More about spanning
tree in CLRS.

Spanning trees can be built with either depth-first (which gives us long, thin trees which can be implemented using a stack) or breadth-first (giving us short, fat trees and implemented using a queue) searches. The components in a directed graph can be considered by their connection.

The input to this sort is a partial ordering (which is a DAG) and the output is a sequence representing the partial order.

To do a topological sort, you need to compute a depth-first search tree and then the reverse of the finished order is a suitable sequence.

To do a depth-first search, pick any node and follow the children until it finds a leaf (or a node where all children from that node have been visited) and put the leaf in the sequence. Repeat for each child to that node until all the children have been visited and continue with any other unvisited node.

This algorithm is non-deterministic.

This has the invariant that the current tree is the minimal tree for its subgraph. To implement this algorithm, you pick a node and then choose the smallest (least weighting) arc to add to the tree. You continue picking the smallest arc (that doesn't connect to an already connected node) until all arcs are picking - the chosen arc can be from anywhere in the tree.

This can be implemented using a priority queue (a heap is best) and is Θ(e log v) in the worst case.

The invariant in this algorithm is to maintain a forest of minimal trees that span the graph. The algorithm works similarly to Prim's, but you start with n trees of size 1 and then the trees are linked together using the shortest arc (where that arc doesn't link to an existing connected node) until there is only 1 tree left. This can be implemented using a priority queue and the union/find equivalence trees and is again Θ(e log v) in the worst case.

In practice, some evidence points to Kruskal's algorithm being better, but whether or not this is the case depends on the exact graph structure.

This takes inputs of a directed, positive weighted graph and a distinguished node and then outputs a tree rooted at v that is the minimal of all such trees that reaches as many nodes as possible.

The algorithm works by looking at all nodes going out of a tree and adding an arc to the tree if it's the shortest route to that node.

An articulation point is a node in a connected graph with the property of removal leaving an unconnected graph. A biconnected graph is a connected (undirected) graph with no articulation points.

To find out if a graph is biconnected:

1. Build a DFS tree and number the vertices by the order which they were visited in the DFS - this gives us N(v).
2. Calculate L(v). This is a number representing how far we can go up the three without following the tree (i.e., using arcs that are not in the tree, but are in the graph (however this could only be done once) and following the tree downwards) L(v) = min( {N(v)} ∪ {N(w) | v → w is a backedge } ∪ {L(w) | v → w is a tree edge}) - this is calculated using a post-order traversal of the DFS tree
3. The root is an articulation point if it has > 1 child, otherwise non-root node v with child w is an articulation point if L(w) ≥ N(v)

Is there a cycle that:

1. reaches all nodes
2. only visits each node once
3. has a distance of less than k

The famous travelling salesman is a form of this problem, where k is the minimal possible number of paths. There are no known good solutions to this, the only solutions that are currently known are to try every single cycle and see which one is the best, this has very low efficiency.

However, if we have a candidate cycle, how hard is it to check that the cycle does fulfill the criteria? It is only Θ(n) to check. This type of algorithm is an NP-hard algorithm - non-determinate and can be checked in polynomial time. We can use heuristics (approximate answers) to solve NP-hard equations.

Break the source into arrays of length p (containing each possible combination) and do a linear search. This gives us Θ(sp) - linear in s and p.

See book for full description

The Knuth-Morris-Pratt method uses finite state automata for string matching.

Boyer and Moore's algorithm is an improved algorithm based on Knuth-Morris-Pratt.

"A new approach to string searching"
Comm ACM vol. 35 iss. 10
pages 74-82 October 1992

1. Build a table, the columns are the pattern, the rows are indexed by letters of the alphabet
2. The table is enumerated such that cell is 1 if the row = column, otherwise it is 0
3. For each letter in the source, put the reverse of the patern from that row for that letter, offset by the letter position of the source word
4. If we get 0s in a row, we have a match

This can be implemented using shift and or at hardware level, so is very fast.

When deciding the complexity for this, we have a new variable, a, the size of the alphabet (may also be constant). This gives us Θ(s + ap), and if a and p are relatively smaller, we could consider this as just Θ(s).

The construction of the table allows a great deal of flexibility (case insensitivity, etc).

Split the problem into two, solve it and combine answers

Making locally optimal choices produces a globally optimal solution.

The opposite of this is a backtracking solution, keep making choices until you run into a dead end, then go back to the last choice and change it to produce an optimal solution.

When a sub-result is needed many times, store it the first time it is calculated (memoisation).

If we use an algorithm that gives us a false positive (such as in the case of Fermat's Lesser Theorem for discovering primes), if we repeat the algorithm many times, the probability of a false positive greatly decreases (in the case of Fermat's Lesser Theorem, by trying 100 values, the chance of error reduces from 0.25 to 2^-200, which is less than the probability of hardware error.

There are two main types of heuristic search methods, genetic algorithms and simulated annealing. These types of algorithms search all possible answers in a semi-intelligent way. f is the function giving fitness of a value and f(s) is a measure of how good s is. We find our answer when s is fit enough.