Created by Yunhao Cao (Github@ToiletCommander) in Fall 2022 for UC Berkeley CS170.

Reference Notice: Material highly and mostly derived from the DPV textbook

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

Big-O Notation (DPV 0)

Sloppiness in the analysis of running times can lead to unacceptable level of inaccuracy in the result

Also possible to be too precise - the time taken by one such step depends crucially on the particular processor and details such as caching strategy.

Let $f(n)$ and $g(n)$ be functions from positive integers to positive reals. We say $f = O(g)$ - f grows no faster than g - if there is a constant $c>0$ such that $f(n) \le c \cdot g(n)$

Just as $O(\cdot)$ is an analog of $\le$, we can also define the analog of $\ge$ and $=$ as follows:

Reduction (DPV 7.1)

If any subroutine for task $Q$ can also be used to solve $P$ , we say $P$ reduces to $Q$. Often, $P$ is solvable by a single call to $Q$’s subroutine, which means any instance $x$ of $P$ can be transformed into an instance $y$ of $Q$ such that $P (x)$ can be deduced from $Q(y)$

Reductions enhance the power of algorithms: Once we have an algorithm for problem Q (which could be shortest path, for example) we can use it to solve other problems.

Graphs

How is a graph represented?

Adjacency matrix

We represent a graph by an adjacency matrix, let there be $n = |V|$ vertices $v_1, \dots, v_n$

For an undirected graph the matrix is symmetric since an edge $\{u, v\}$ can be taken in either direction

The presence of a particular edge can be cheked in constant time, but it takes $O(n^2)$ space.

Adjacency List

With size proportional to the number of edges, consists of $|V|$ linked lists, one per vertex. The linked list for vertex $u$ holds the names of vertices to which $u$ has an outgoing edge.

Total size of the data structure is $O(|E|)$ but checking for an edge is no longer constant time(requires sifting through $u$’s adjacency list)

Algorithms

Fibonacci(DPV 0)

Basic Arithmetic (DPV 1.1)

Incidentally, this function $\log N$ appears repatedly in our subject, in many guises. Here’s a sampling:

1. $\log N$ is the power to which you need to raise $2$ in order to obtain $N$.

2. Going backward, it, $\lceil \log N \rceil$, can also be seen as the number of times you must halve $N$ to get down to 1. This is useful when a number is halved at each iteration of an algorithm

3. It, $\lceil \log (N+1) \rceil$ , is the number of bits in the binary representation of $N$.

4. It, $\lfloor \log N \rfloor$ , is also the depth of a complete binary tree with $N$ nodes

5. It is even the sum $1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{N}$, to within a constant factor.

Addition

Basic property of numbers: The sum of any three single-digit numbers is at most two digits long (holds for any base b ≥ 2).

This simple rule gives us a way to add two numbers in any base: align their right-hand ends, and then perform a single right-to-left pass in which the sum is computed digit by digit, maintaining the overflow as a carry. Since we know each individual sum is a two-digit number, the carry is always a single digit, and so at any given step, three single-digit numbers are added.

We will not spell out the pseudocode because we are so familiar with it. We will go ahead and anlyze its efficiency: We want the answer expressed as a function of the size of the input: the number of bits of x and y, the number of keystrokes needed to type them in.

Suppose x and y are each n bits long; in this chapter we will consistently use the letter $n$ for the sizes of numbers. Then the sum of $x$ and $y$ is $n + 1$ bits at most, and each individual bit of this sum gets computed in a fixed amount of time. The total running time for the addition algorithm is therefore of the form $c_0 + c_1n$, where $c_0$ and $c_1$ are some constants; in other words, it is linear. Instead of worrying about the precise values of $c_0$ and $c_1$, we will focus on the big picture and denote the running time as $O(n)$.

Some readers may be confused at this point: Why $O(n)$ operations? Isn’t binary addition something that computers today perform by just one instruction? There are two answers.

First, it is certainly true that in a single instruction we can add integers whose size in bits is within the word length of today’s computers—32 perhaps. But, as will become apparent later in this chapter, it is often useful and necessary to handle numbers much larger than this, perhaps several thousand bits long. Adding and multiplying such large numbers on real computers is very much like performing the operations bit by bit. Second, when we want to understand algorithms, it makes sense to study even the basic algorithms that are encoded in the hardware of today’s computers. In doing so, we shall focus on the bit complexity of the algorithm, the number of elementary operations on individual bits—because this accounting reflects the amount of hardware, transistors and wires, necessary for implementing the algorithm.

Multiplication

algorithm for multiplying two numbers $x$ and $y$ is to create an array of intermediate sums, each representing the product of $x$ by a single digit of $y$. These values are appropriately left-shifted and then added up. Suppose for instance that we want to multiply $13 \times 11$, or in binary notation, $x = 1101$ and $y = 1011$.

If $x$ and $y$ are both $n$ bits, then there are $n$ intermediate rows, with lengths of up to $2n$ bits (taking the shifting into account). The total time taken to add up these rows, doing two numbers at a time, is:

But there are better ways to do this…

Division

Modular Arithmetic (DPV 1.2, unfinished)

Just like multiplication, division works on computers with limited bits.

Modular arithmetic is a system for dealing with restricted ranges of integers. We define $x \text{ modulo } N$ to be the remainder when $x$ is divided by $N$ ; that is, if $x = qN + r$ with $0 \le r < N$ , then $x \text{ modulo } N$ is equal to $r$. This gives an enhanced notion of equivalence between numbers: $x$ and $y$ are congruent modulo $N$ if they differ by a multiple of $N$ , or in symbols

Another interpretation is that modular arithmetic deals with all the integers, but divides them into $N$ equivalence classes, each of the form ${i + kN : k \in Z}$ for some $i$ between $0$ and $N$

Hashing (DPV 1.5)

Hash Tables

We will have an array of size $n = 250$ and each key $k$ is hashed by hash function $h(k): k \rightarrow x$ where $x \in \{0, 1, \dots, n-1\}$. Each array element is a linked list

Hash Functions

• We want to make sure that hash collision is unlikely
  • Otherwise we are wasting space

• We need randomization
  • Pick a hash function randomly from some class of functions!

Let the number of buckets instead of $n=250 \rightarrow n = 257$, note that $257$ is a prime number

Let any IP address $x$ as a quadruple $x = (x_1, \dots, x_4)$ and we will fix any four numbers $a_1, a_2, a_3, a_4 \mod n$ and map the address $x$ to $h(x) = (a_1 a_1 + a_2 x_2 + a_3 x_3 + a_4 x_4) \mod 257$.

We have defined the hash function

With this hash function,

Property: Consider any pair of distinct IP addresses $x = (x_1, \dots, x_4)$, $y = (y_1, \dots, y_4)$. If the coefficients $a = (a_1, \dots, a_4)$ are chosen uniformly at random from $\{0, 1, \dots, n-1\}$, then

This condition guarantees that the expected lookup time for any item is small.

Proof:

Since $x = (x_1, \dots , x_4)$ and $y = (y_1, \dots , y_4)$ are distinct, these quadruples must differ in some component; without loss of generality let us assume that $x_4 \ne y_4$. We wish to compute the probability

that is, the probability that

This last equation can be rewritten as

Suppose that we draw a random hash function ha by picking $a = (a_1, a_2, a_3, a_4)$ at random. We start by drawing $a_1$, $a_2$, and $a_3$, and then we pause and think:

What is the probability that the last drawn number $a_4$ is such that equation above holds?

We know

• So far the LHS evaluates to $c$

• Since $n$ is prime and $x_4 \ne y_4$, $(y_4 - x_4)$ has a unique inverse mod $n$

Thus for previous equation to hold,

The probability of this happening is $1/n$

Universal Hash Functions

Family of hash functions that satisfy the following property:

For any two distinct data items $x$ and $y$, exactly $|H|/n$ of all the hash functions in $H$ map $x$ and $y$ to the same bucket, where $n$ is the number of buckets

In our example, we used the family

Which is an group of universal hash functions

In other words, for any two data items, the probability these items collide is 1/n if the hash function is randomly drawn from a universal family.

Divide and Conquer (DPV 2)

Recurrence Relationships (DPV 2.2)

Divide and conquer often follow a generic pattern of runtime:

To prove master theorem,

we will assume that n is a power of b (this will not influence the final bound because n is at most a multiplicative factor of b away from some power of b)

Notice that the size of the subproblems decrease by a factor of b with each level of recursion, and therefore reaches the base case after $\log_b n$ levels. Its branching factor is $a$, so the k-th level of the tree is made up of $a^k$ subproblems, each of size $n/b^k$. The total work done at this level is

As $k$ goes from 0 to $\log_b n$, these numbers form a geometric series with ratio $a/b^d$. Therefore we can find the sum by three cases:

1. $a/b^d < 1$
   1. The series is decreasing, and its sum is just given by the first term $O(n^d)$

2. $a/b^d = 1$
   1. We will have $O(\log n)$ counts of the first term
   2. $O(n^d \log n)$

3. $a/b^d > 1$
   1. The series is increasing, and its sum is given by its last term
   2. $n^d (\frac{a}{b^d})^{\log_b n} = n^d (\frac{a^{\log_b n}}{(b^{\log_b n})^d}) = a^{\log_b n} = a^{(\log_a n)(\log_b a)} = n^{\log_b a}$
   3. $O(n^{\log_b a})$

Multiplication (DPV 2.1)

Gauss’s trick:

Product of two complex numbers:

Can in fact be done with just three terms $ac, bd, (a+b)(c+d)$ because:

Using the same idea, if $x$ and $y$ are two n-bit integers, we can represent them as left and right halves of bits

We have recursion expression of

for this multiplication relationship

But we can use Guss’s trick, we only need $x_L y_L, x_R y_R, (x_L+x_R)(y_L+y_R)$ to compute the multiplication since $x_Ly_R+x_Ry_L = (x_L+x_R)(y_L+y_R)-x_Ly_L-x_Ry_R$

(Karatsuba Algorithm)

MergeSort

“Split the list into two halves, recursively sort each half, and merge the two sorted sublists”

The merge procedure does a constant amount of work per recursive call, thus $\text{merge}(\cdot) \in O(n)$ and the overall time taken by mergesort:

We will also define an iterative version of mergesort, where $\text{inject}(array,element)$ means to append an element to the end of an array and $\text{eject}(array)$ means to remove an element at the front of the array and return it.

Reason of why sorting using comparison must be at least $\Omega(n \log n)$ is because every permutation of the elements must be present in the leaves of the sorting algorithm and therefore the complexity of the tree representing the sorting algorithm must have $\text{depth} \propto n\log n$

Median

When looking for a recursive solution, it is paradoxically often easier to work with a more general version of the problem—for the simple reason that this gives a more powerful step to recurse upon. In our case, the generalization we will consider is selection

Divide and Conquer for selection:

For any number $v$, imagine splitting list $S$ into three categories: elements smaller than $v$, those equal to $v$ (there might be duplicates), and those greater than $v$.

For instance, if the array $S$:

is put to split on $v=5$, then

We can check $k$ is in which sub-array by using length of each array

Worst case:

1. We select $v$ to be the smallest/largest element of the array each time, causing array to only shrink by 1.

We will define a good selection of $v$ to at least strip away 25% of the original array.

Therefore

Matrix Multiplication (DPV 2.5)

Matrix Multiplication can be viewed as blocks

But it is still $O(n^3)$, by:

Turns out $XY$ can be computed from just seven $n/2 \times n/2$ subproblems

where

The new runtime is

Fast Fourier Transform (DPV 2.6)

e^(iπ) in 3.14 minutes, using dynamics | DE5

https://youtu.be/v0YEaeIClKY

But what is the Fourier Transform? A visual introduction.

https://youtu.be/spUNpyF58BY

The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?

https://youtu.be/h7apO7q16V0

Product of two degree-d polynomials is a polynomial of degree 2d:

Then

and $C(x)$ will have coefficients

Where $\forall i > d, a_i = 0 \wedge b_i = 0$

Computing each $c_k$ takes $O(k)$ and results to an overall $\Theta(d^2)$ steps since we have $2d+1$ coefficients

So therefore do we have a faster algorithm for solving this problem?

Here $A$ are coefficients of the functions (describing the function), and $\omega$ are point to be evaluated at the function.

So now we have evaluted the polynomial at those representation points, we have multiplied the values to obtain $(2n+1)$ values, how do we interpolate back?

The definitive FFT Algorithm:

The FFT takes as input a vector $a = (a_0, \dots, a_{n-1})$ and a complex number $\omega$ whose powers $1, \omega, \dots, \omega^{n-1}$ are complex n-th roots of unity.

We can apply divide and conquer to the matrix multiplication steps

The final product is the vector

Summary:

The divide-and-conquer step of the FFT can be drawn as a very simple circuit. Here is how a problem of size $n$ is reduced to two subproblems of size $n/2$ (for clarity, one pair of outputs $(j, j + n/2)$ is singled out):

the edges are wires carrying complex numbers from left to right. A weight of $j$ means “multiply the number on this wire by $\omega^j$ .

1. For $n$ inputs there are $\log_2 n$ levels, each with $n$ nodes, for a total of $O(n \log n)$ operations

2. the inputs are arranged by increasing last bit of the binary representation of their index, resolving ties by looking at the next more significant bit(s).
   1. For $n=8$, The resulting order in binary, 000, 100, 010, 110, 001, 101, 011, 111

3. There is a unique path between each input $a_j$ and each output $A(\omega^k)$
   1. This path is most easily described using the binary representations of j and k (shown in Figure 10.4 for convenience). There are two edges out of each node, one going up (the 0-edge) and one going down (the 1-edge).
   2. To get to A(ωk) from any input node, simply follow the edges specified in the bit representation of k, starting from the rightmost bit

4. On the path between $a_j$ and $A(\omega^k$), the labels add up to $jk \mod 8$.
   1. Contribution of input $a_j$ to output $A(w^k)$ is $a_jw^{jk}$

5. Notice that the FFT circuit is a natural for parallel computation and direct implementation in hardware.

Graphs (DPV 3 + 4)

DFS (Depth-first Search) in undirected graphs (DPV 3.2)

Surprisingly versatile linear-time procedure that reveals a wealth of information about a graph

Explore

$explore(G,v) \in O(|E|)$

Depth-First Search Algorithm (DFS)

First step:

Marking visited to false, $O(|V|)$

Second step:

Every edge examined exactly twice (for an edge $\{x,y\} \in E$, we visit from $explore(x)$ and $explore(y)$) ⇒ $O(|E|)$

Connected Components

We can also check what connected components exist in the graph by simply modifying a bit in the DFS algorithm

Where here $ccnum$ identifies the connect component to which $v$ belongs

$cc$ is initialized to zero and incremented each time $DFS$ calls $explore$

Previsit and postvisit ordering

We will also note down the times of two important events, the moemnt of first discovery and of final departure.

Directed Acyclic graphs (DAGs) (DPV 3.3.2)

Good for modeling relationships like causalities, hierarchies, and temporal dependencies.

All DAGs can be linearized. ⇒ perform tasks in decreasing order of their post numbers

only edges $(u,v)$ in a graph for which $post(u)< post(v)$ are back edges ⇒ and dag cannot have back edges ⇒ In a DAG, every edge leads to a vertex with a lower $post$ number

So therefore

Also, since every DAG has at least one source and one sink…We can do this linearization

1. Find a source, output it, and delete it from graph

2. Repeat until the graph is empty

Strongly Connected Components

Two nodes $u$ and $v$ of a directed graph are connected if there is a path from $u$ to $v$ and a path from $v$ to $u$.

And… turns out the meta-graph can be found in linear time by making further use of DFS.

Property 1: If the $explore$ subroutine is started at node $u$, then it will terminate precisely when all nodes reachable from $u$ have been visited.

So if we call $explore$ on a node that lies somewhere in a $sink$ strongly connected component, then we will retrieve exactly that component.

Property 2: The node that receives the highest $post$ number in a DFS must lie in a source strongly connected component.

Property 3: If $C$ and $C’$ are strongly connected components, and there is an edge from a node in $C$ to a node in $C’$, then the highest $post$ number in $C$ is bigger than the highest $post$ number in $C’$.

Proof of property 3:

In proving Property 3, there are two cases to consider. If the depth-first search visits component $C$ before component $C’$, then clearly all of $C$ and $C′$ will be traversed before the procedure gets stuck (see Property 1). Therefore the first node visited in $C$ will have a higher post number than any node of $C′$. On the other hand, if $C′$ gets visited first, then the depth-first search will get stuck after seeing all of $C′$ but before seeing any of C, in which case the property follows immediately.

We can use the reverse graph $G^{R}$ and property 2 to find a node from the $sink$ component of graph $G$

Once we have found the first strongly connected component and deleted it from the graph, the node with the highest post number among those remaining will belong to a sink strongly connected component of whatever remains of $G$. Therefore we can keep using the post numbering from our initial depth-first search on $G^R$ to successively output the second strongly connected component, the third strongly connected component, and so on. The resulting algorithm is this.

1. Run DFS on $G^R$

2. Run the undirected connected components algorithm on $G$, and during the DFS, process the vertices in decreasing order of their $post$ numbers from step 1.

This is linear time, only the constant is about twice of normal DFS search

Paths in Graphs: Distances (DPV 4.1)

The distance between two nodes is the length of the shortest path between them.

To get a concrete feel for this notion, consider a physical realization of a graph that has a ball for each vertex and a piece of string for each edge. If you lift the ball for vertex s high enough, the other balls that get pulled up along with it are precisely the vertices reachable from s. And to find their distances from s, you need only measure how far below s they hang.

Breadth-First Search (BFS) (DPV 4.2)

Initially the queue $Q$ consists only of the root, $s$, the one node at distance $0$. And for each subsequent distance $d = 1, 2, 3, \dots$, there is a point in time at which $Q$ contains all the nodes at distance $d$ and nothing else. As these nodes are processed (ejected off the front of the queue), their as-yet-unseen neighbors are injected into the end of the queue.

Lengths on Edges (DPV 4.3)

We will annotate every edge $e \in E$ with $l_e$.

Dijkstra’s Algorithm (DPV 4.4)

we can think of Dijkstra’s algorithm as just BFS, except it uses a priority queue instead of a regular queue, so as to prioritize nodes in a way that takes edge lengths into account.

Runtime Analysis:

Dijkstra’s algorithm is structurally identical to breadth-first search. However, it is slower because the priority queue primitives are computationally more demanding than the constant-time $eject$’s and $inject$’s of BFS. Since makequeue takes at most as long as $|V|$ insert operations, we get a total of $|V|$ $deletemin$ and $|V | + |E|$ $insert$/$decreasekey$ operations. The time needed for these varies by implementation; for instance, a binary heap gives an overall running time of $O((|V | + |E|) log |V |)$.

Priority Queue Implemention in Dijkstra (DPV 4.5)

Array

The simplest implementation of a priority queue is as an unordered array of key values for all potential elements (the vertices of the graph, in the case of Dijkstra’s algorithm).

Initially, these values are set to $\infin$. An insert or decreasekey is fast, because it just involves adjusting a key value, an $O(1)$ operation. To $deletemin$, on the other hand, requires a linear-time scan of the list.

Binary Heap

Elements are stored in a complete binary tree, in which each level is filled in from left to right, and must be full before the next level is started.

And special ordering constraint: the key value of any node of the tree is less than or equal to that of its children.

To $insert$, place the new element at the bottom of the tree (in the first available position), and let it “bubble up.” That is, if it is smaller than its parent, swap the two and repeat (Figure 4.11(b)–(d)). The number of swaps is at most the height of the tree, which is $\lfloor \log_2 n \rfloor$ when there are $n$ elements.

A $decreasekey$ is similar, except that the element is already in the tree, so we let it bubble up from its current position.

To $deletemin$, return the root value. To then remove this element from the heap, take the last node in the tree (in the rightmost position in the bottom row) and place it at the root. Let it “sift down”: if it is bigger than either child, swap it with the smaller child and repeat (Figure 4.11(e)–(g)). Again this takes O(log n) time.

The regularity of a complete binary tree makes it easy to represent using an array. The tree nodes have a natural ordering: row by row, starting at the root and moving left to right within each row. If there are n nodes, this ordering specifies their positions $1, 2, \dots , n$ within the array. Moving up and down the tree is easily simulated on the array, using the fact that node number $j$ has parent $\lfloor j/2 \rfloor$ and children $2j$ and $2j + 1$

d-ary Heap

A d-ary heap is identical to a binary heap, except that nodes have d children instead of just two. This reduces the height of a tree with $n$ elements to $\Theta(\log_d n) = \Theta((\log n)/(\log d))$.

Inserts are therefore speeded up by a factor of $\Theta(log d)$. $Deletemin$ operations, however, take a little longer, namely $O(d \log_d n)$

Negative-value edges? (DPV 4.6.1)

Dijkstra’s method can be thought as a sequence of “Update” operations

But Dijkstra’s method will mark off vertices that have been used to calculate shorter distances, this usually cannot be the case with negative-value edges because now updated vertices might receive an update from a negative edge.

Detecting Negative Cycles (DPV 4.6.2)

In such situations, it doesn’t make sense to even ask about shortest paths. There is a path of length 2 from A to E. But going round the cycle, there’s also a path of length 1, and going round multiple times, we find paths of lengths 0, −1, −2, and so on.

Fortunately, it is easy to automatically detect negative cycles and issue a warning. Such a cycle would allow us to endlessly apply rounds of update operations, reducing dist estimates every time.

Shortest Paths in DAGs that doesn’t have negative cycles (DPV 4.7)

There are two subclasses of graphs that automatically exclude the possibility of negative cycles:

1. graphs without negative edges
   1. Dijkstra

2. graphs without cycles
   1. Can be solved in linear time!

Linearize (that is, topologically sort) the dag by depth-first search, and then visit the vertices in sorted order, updating the edges out of each.

Greedy Algorithms (DPV 5)

A player who is focused entirely on immediate advantage is easy to defeat. But in many other games such as Scrabble, it is possible to do quite well by simply making whichever move seems best at the moment

Minimum Spanning Trees

Suppose you are asked to network a collection of computers by linking selected pairs of them. Each link also has a maintenance cost, reflected in that edge’s weight. What is the cheapest possible network?

Trees

A tree is an undirected graph that is connected and acyclic

Property:

1. A tree on $n$ nodes has $n-1$ edges

2. Any connected, undirected graph $G=(V,E)$ with $|E| = |V|-1$ is a tree

3. An undirected graph is a tree if and only if there is a unique path between any pair of nodes

The cut property:

Suppose edges $X$ are part of a minimum spanning tree of $G = (V, E)$. Pick any subset of nodes $S$ for which $X$ does not cross between $S$ and $V − S$, and let $e$ be the lightest edge across this partition. Then $X \cup \{e\}$ is part of some MST.

最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩_bilibili

最小生成树是一副连通加权无向图中一棵权值最小的生成树,本视频用动画的方式生动形象的演示构建最小生成树的kruskal（克鲁斯卡尔）算法或prim（普里姆）算法, 视频播放量 176820、弹幕量 1168、点赞数 8032、投硬币枚数 6321、收藏人数 7367、转发人数 2434, 视频作者 WAY_zhong, 作者简介 @kvisual ...

https://www.bilibili.com/video/BV1Eb41177d1/

Data structure for disjoint sets - Union by rank

Faster find:

When we want to merge sets, if the representatives (roots) of the sets are $r_x$ and $r_y$ , do we make $r_x$ point to $r_y$ or the other way around? Since tree height is the main impediment to computational efficiency, a good strategy is to make the root of the shorter tree point to the root of the taller tree.

Properties:

1. $\forall x, \text{rank}(x) < \text{rank}(\pi(x))$

2. Any node of rank k has at least $2^k$ nodes in its tree

3. If there are $n$ elements overall, there can be at most $n/2^k$ nodes of rank $k$

Kruskal’s Method

Sort the edges by their weights, everytime check if the smallest edge would add a cycle to the graph. If it doesn't then it gets added to the graph.

$O(|E| \log |E|) \approx O(|E| \log |V|)$ for sorting edges and $O(|E| \log |V|)$ for unino and find operations

But if the weights are small so that sorting can be done in linear time? Can we perform $union$ and $find$ faster than $\log n$?

during each $find$, when a series of parent pointers is followed up to the root of a tree, we will change all these pointers so that they point directly to the root ⇒ use the faster $find$

Now the amortized cost of $find$ and $union$ is $O(1)$

Prim’s Method

Start from an arbitraty node, at each step we added the shortest edge connecting some node already in the tree to one that isn't yet.

So obtain a subgroup and another subgroup that contains vertices not selected in the first subgroup. Whatever edges that hasn't been selected yet that connects the first group with the second and has the smallest weight will be selected.

Huffman Encoding $O(n \log n)$

What is the most economic way of writing strings consisting of letters A,B,C,D?

The obvious choice is to use $2$ bits per symbol—say codeword $00$ for $A$, $01$ for $B$, $10$ for $C$, and $11$ for $D$ - in which case $260$ megabits are needed in total. Can there possibly be a better encoding than this?

In search of inspiration, we take a closer look at our particular sequence and find that the four symbols are not equally abundant.

Is there some sort of variable-length encoding, in which just one bit is used for the frequently occurring symbol A, possibly at the expense of needing three or more bits for less common symbols?

A danger with having codewords of different lengths is that the resulting encoding may not be uniquely decipherable. For instance, if the codewords are $\{0, 01, 11, 001\}$, the decoding of strings like $001$ is ambiguous. We will avoid this problem by insisting on the prefix-free property: no codeword can be a prefix of another codeword.

To measure how “good” a coding tree is, we want a tree whose leaves each correspond to a symbol and minimizes the overall length of the encoding

Tells us that the two symbols with the smallest frequencies MUST be at the bottom of the optimal tree, as children of lowest internal node. ⇒ because otherwise swapping whatever node with either of those two would increase performance.

This suggests that we start constructing the tree greedily: find the two symbols with the smallest frequencies, say $i$ and $j$, and make them children of a new node, which then has frequency $f_i + f_j$

There is another way to write this cost function that is very helpful. Although we are only given frequencies for the leaves, we can define the frequency of any internal node to be the sum of the frequencies of its descendant leaves; this is, after all, the number of times the internal node is visited during encoding or decoding. During the encoding process, each time we move down the tree, one bit gets output for every nonroot node through which we pass.

And therefore

The cost of a tree is the sum of the frequencies of all leaaves and internal nodes, except the root

Entropy

Average number of bits needed to encode a single draw from the distribution

Measures the randomness of a set of mixed elements

Horn Formula

A framework for doing computer doing logical reasoning!

A literal is either: a variable or a variable’s negation

Then we have two kinds of caluses:

1. Implications, left hand side is and AND of any number of positive literals and right hand is a single positive iteral $a \implies b$

2. Pure negative clauses, consisting of an OR of any number of negative literals $(\bar{u} \vee \bar{v} \vee \bar{y})$

Given a set of clauses, the goal is to do satisfying assignment - determine whether there is a consistent explanation: an assignment of $true / false$ values to the variables that satisfies all the clauses.

Our approach:

1. Start with all variables $false$

2. and proceed to set some of them to $true$
   1. one by one and only if we absolutely have to because an implication would be violated

Horn formulas lie at the heart of Prolog (“programming by logic”), a language in which you program by specifying desired properties of the output, using simple logical expressions

To see why the algorithm is correct, notice that if it returns an assignment, this assignment satisfies both the implications and the negative clauses, and so it is indeed a satisfying truth assignment of the input Horn formula. So we only have to convince ourselves that if the algorithm finds no satisfying assignment, then there really is none. This is so because our “stingy” rule maintains the following invariant:

If a certain set of variables is set to true, then they must be true in any satisfying assignment.

Set cover

County is in its early stages of planning and is deciding where to put schools. There are only two constraints: each school should be in a town, and no one should have to travel more than 30 miles to reach one of them.

What is the minimum number of schools needed?

Let $S_x$ be the set of towns within 30 miles of town $x$, a school at $x$ will esentially “cover”these other towns. Then how many sets $S_x$ must be picked in order to cover all the towns in the country?

Greedy solution:

1. Repeat until all elements of $B$ are covered
   1. Pick the set $S_i$ with the largest number of uncovered elements

But we will see that this is not optimal, but it’s not too far off, so let’s modify this.

Suppose $B$ contains $n$ elements and that the optimal cover consists of $k$ sets, then the greedy algorithm will use at most $k \ln n$ sets.