Algorithms & Data Structures

Problem: Explain what the spacetime complexity of an algorithm on a problem of characteristic input size \(n\) is.

Solution: Time complexity \(T(n)\), is the number of \(\Theta(1)\)-operations that an algorithm requires to produce a solution to a problem of input size \(n\), while space complexity \(S(n)\) is the same but for memory. More precisely, just as the Wigner-Eckart theorem factorizes angular momentum matrix elements of spherical components of tensor operators as a product of purely geometric Clebsch-Gordan coefficients with an operator-specific “reduced matrix element”, the total runtime can be thought of as factorizing into a purely algorithm-dependent factor \(T(n)\) and some hardware-specific factor, and similarly the memory is proportional to \(S(n)\) with hardware-dependent proportionality constant.

Problem: Explain how the \(3\) time complexities \(T_{b}(n),T(n),T_w(n)\) are defined (similar definitions apply to their spatial counterparts \(S_{b}(n),S(n),S_w(n)\)).

Solution: Letting \(\mathcal I_n\) be the set of all valid inputs of size \(n\), one can define a random function \(T(I)\) returning some algorithm’s time complexity on a specific length-\(n\) input \(I\in\mathcal I_n\) (which itself can be thought of as a random variable with some not-necessarily-uniform probability distribution \(p(I)\), e.g. Zipf’s law in word queries). Then the best-case and worst-case time complexities are simply:

\[T_{b}(n):=\min_{I\in\mathcal I_n}T(I)\]

\[T_{w}(n):=\max_{I\in\mathcal I_n}T(I)\]

whereas the average-case time complexity is:

\[T(n):=\langle T(I)\rangle=\sum_{I\in\mathcal I_n}p(I)T(I)\]

Problem: Describe several classic comparison-based sorting algorithms (think of ordering a bunch of people by height), and justify their (asymptotic) best/average/worst-case time complexities and auxiliary space complexities (i.e. space complexities but ignoring the \(\Theta(n)\) memory occupied by the input length-\(n\) array itself).

Solution: First, there are a few sorting algorithms which are inefficient and thus not actually implemented in production:

• Bogosort works like tossing a deck of cards on the floor and picking them up in a random order. If the result is not sorted, then repeat. Of course, this is not a comparison-based, or even deterministic sorting algorithm. It is just bad, don’t use it. \(T_b(n)\in\Theta(n),T_w(n)\in\Theta(\infty),T(n)\in\Theta(n\times n!)\) while \(S_b(n),S_w(n),S(n)\in\Theta(1)\).
• Bubble sort works by comparing elements pairwise and swapping if necessary, moving through the array and repeating until there’s no elements left to swap. It has time complexities \(T_b(n)\in\Theta(n)\) (if the array is already sorted) and \(T_w(n),T(n)\in\Theta(n^2)\) (since one may have to compare all \(n(n-1)/2\in\Theta(n^2)\) pairs of elements). Like bogosort, it is an in-place algorithm, so \(S_b(n),S_w(n),S(n)\in\Theta(1)\)).
• Insertion sort is like sorting cards. It has time complexities \(T_b(n)\in\Theta(n)\) and \(T_w(n),T(n)\in\Theta(n^2)\). It is also an in-place algorithm \(S_b(n),S_w(n),S(n)\in\Theta(1)\).
• Selection sort divides the array into sorted and unsorted regions, repeatedly finding the min from the unsorted region and swapping it with the first element of the unsorted region. It has time complexities \(T_b(n),T_w(n),T(n)\in\Theta(n^2)\), and operates strictly in-place \(S_b(n),S_w(n),S(n)\in\Theta(1)\).

The sorting algorithms below are characterized by log-linear \(T(n)\in\Omega(n\ln n)\) average-case time complexities and thus are considered to be efficient and commonly used in production:

• Merge sort uses a divide-and-conquer strategy, recursively halving the array into single-element subarrays and then merging the sorted subarrays back together in order. One can thus write down a recurrence relation \(T(n)=2T(n/2)+\Theta(n)\), and hence apply the master theorem to obtain \(T_b(n),T_w(n),T(n)\in\Theta(n\ln n)\). Because it requires an auxiliary array to hold elements during the merge, merge sort has auxiliary space complexities \(S_b(n),S_w(n),S(n)\in\Theta(n)\).
• Quick sort works by randomly choosing a pivot, comparing all other elements to the pivot and swapping them left/right of the pivot accordingly, then recursively repeating this on the subarrays split by the pivot (now in the correct position). It has time complexities \(T_w(n)\in\Theta(n^2)\) and \(T_b(n),T(n)\in\Theta(n\ln n)\) (in all \(3\) cases, a factor of \(n\) is due to the \(\Theta(n)\) time required to scan an array of length \(n\) at each level of the recursion tree, while the remaining factor is the recursion tree depth for that particular case). Meanwhile, quick sort has auxiliary space complexities \(S_w(n)\in\Theta(n)\) and \(S_b(n),S(n)\in\Theta(\ln n)\) which are simply the recursion tree depths used to build up a call stack in the respective cases (there seems to be debate about whether quick sort is considered “in-place” or not…)
• Shell sort works as a generalized and optimized version of insertion sort. It allows the exchange of far-apart elements by sorting pairs of elements separated by a gap that progressively decreases down to \(1\). It has a best-case time complexity of \(T_b(n)\in\Theta(n\ln n)\) (or \(\Theta(n)\) depending on the gap sequence) and a worst-case of \(T_w(n)\in\Theta(n^2)\) using Shell’s original gaps, though modern gap sequences can reduce this to \(\Theta(n^{3/2})\) or \(\Theta(n\ln^2 n)\). Its average-case time complexity \(T(n)\) depends heavily on the chosen gap sequence but typically scales better than quadratic time. Because it modifies the array via localized insertion passes, it is an in-place algorithm with space complexities \(S_b(n),S_w(n),S(n)\in\Theta(1)\).
• Heap sort works by visualizing the array as a complete binary tree and rearranging it into a max-heap structure. It then repeatedly extracts the maximum element from the root, moves it to the end of the array, and runs a heapify procedure to restore the heap property for the remaining elements. It has time complexities \(T_b(n),T_w(n),T(n)\in\Theta(n\ln n)\) because constructing the initial heap takes \(\Theta(n)\) time, and each of the \(n\) extractions requires a heapify step that takes logarithmic time proportional to the height of the tree. Since it manipulates the array directly by swapping elements, its space complexities are \(S_b(n),S_w(n),S(n)\in\Theta(1)\).
• Timsort works as a hybrid, stable sorting algorithm that intelligently combines the strengths of merge sort and insertion sort. It operates by scanning the array to find naturally ordered segments called “runs,” extending short runs using insertion sort, and then combining those runs using an optimized merging routine. It achieves a best-case time complexity of \(T_b(n)\in\Theta(n)\) when the data is already sorted or reverse-sorted. Its worst and average-case time complexities are \(T_w(n),T(n)\in\Theta(n\ln n)\) as it scales up to a merge-like structural tree for random data. It requires auxiliary space to execute its merge operations, yielding space complexities of \(S_w(n),S(n)\in\Theta(n)\) and \(S_b(n)\in\Theta(1)\).
  
  The sorting algorithms below are non-comparison-based sorting algorithms, allowing them to bypass the lower bound of \(\Omega(n\ln n)\) by leveraging specific assumptions about the properties of the input data:
  
• Counting sort works by mapping the frequency of each distinct key value into an auxiliary counting array, then calculating the precise starting index of each element in the final sorted array via a prefix sum. It requires the input keys to be integers falling within a known, finite range \([0, k]\). It features time complexities of \(T_b(n),T_w(n),T(n)\in\Theta(n+k)\) because it requires a constant number of linear scans over both the input data and the counting bucket array. Its auxiliary space complexities are \(S_b(n),S_w(n),S(n)\in\Theta(n+k)\) due to the necessity of maintaining the counting array of size \(k\) and a separate output buffer array of size \(n\).
• Radix sort works by exploiting the fact that numbers can be written in some base (aka radix)-\(b\in\mathbf Z^+\) number system (e.g. \(b=10\)). One simply defines \(b\) buckets for each of the digits \(0,1,..,b-1\) in that number system, then stably (i.e. in an order-preserving way) group numbers into buckets (think “histogram”) starting from their least significant (the “ones”) digit, and moving progressively more significant (there exists a version of radix sort that starts from the most significant digit and moves the other way, but it’s less parallelizable on GPU). Radix sort requires \(T_b(n),T_w(n),T(n)\in\Theta(d(n+b))\) elementary operations, where \(d\) is the number of base-\(b\) digits in the largest number among the \(n\), and requires \(S_b(n),S_w(n),S(n)\in\Theta(n+b)\) units of space.
• Bucket sort works by distributing elements across a fixed number of buckets that segment a known interval. Each bucket is then sorted individually using a secondary sorting algorithm (like insertion sort) or by recursively applying bucket sort, before the sorted buckets are concatenated sequentially. It has a best and average-case time complexity of \(T_b(n),T(n)\in\Theta(n+k)\) when elements are uniformly distributed across \(k\) buckets, making the individual bucket sizes small and constant. However, if the data heavily clusters into a single bucket, the worst-case time complexity defaults to the secondary sorting algorithm, yielding \(T_w(n)\in\Theta(n^2)\) if insertion sort is utilized. Its space complexities are \(S_b(n),S_w(n),S(n)\in\Theta(n+k)\) to maintain the collection of bucket structures.

Problem: Distinguish between the concepts of abstract data types, data types, and data structures.

Solution: At the highest level, it’s abstract data types (e.g. the Platonic mathematical idea of the real numbers \(\mathbf R\) and the axiomatic operations one can perform with them). Below that, it’s the data type itself (e.g. the messy, IEEE \(754\) double-precision standard concrete implementation of the ADT such as a Python float), and at the lowest level of the hardware/RAM, it’s the data structure describing the geometric arrangement of bits/bytes to implement objects of a data type.

Problem: List several standard data structures, pros and cons, and example applications.

Solution:

• Static arrays: contiguous block of memory with fixed size \(n\). Access takes \(\Theta(1)\) time but insertion takes \(\Theta(n)\) to shift bits around to make room. Python tuples (an immutable data type) are stored using static array data structures.
• Dynamic arrays: like static arrays except \(n\) is not fixed. In practice, are implemented via static arrays (i.e. if capacity \(n\) of a static array is exceeded, duplicate to a new static array with \(n\mapsto\lambda n\) for some fixed multiplier \(\lambda\sim 2\)). Python lists (a mutable data type) are stored using dynamic array data structures (not linked lists! unfortunate nomenclature…)
• Linked lists: unlike in (static/dynamic) arrays where bits are arranged contiguously (and thus the contiguity implicitly determines which bit comes after which), linked lists abandon contiguity in favor of a linear graph-like structure consisting of nodes that store not only the value of the data (as was the case with arrays) but also a pointer (memory address of the next node). Insertion/deletion are \(\Theta(1)\) but access and search are both \(\Theta(n)\) (cannot make use of caching, unlike arrays). In a singly-linked list, each node can be thought of as a pair \((v,x)\) where \(v\) is the value of the node and \(x\) is a pointer to the next node (if the linked list is moreover circular then \(x_{\text{tail}}\) would act as the head, otherwise \(x_{\text{tail}}\) is null). A doubly-linked list consists of nodes of the form \((v,x,x’)\) with \(x’\) being a pointer to the previous node (rather than next node).
• Hash tables: essentially a data structure implementation of a dictionary data type. For each key \(k\), one associates some value \(v(k)\) where the function \(v\) is called the hash function and should be chosen to be simultaneously as simple and injective as possible (will need some system for handling inevitable non-injective mappings though, aka collisions). Useful for memoization of recursive function computations (e.g. Fibonacci).
• Stacks: (strictly an abstract data type, can be implemented using either array or linked list data structures) LIFO (last-in first-out) like a stack of plates, a ctrl\(+z\) undo stack, or a call stack. Push or pop.
• Queues: (strictly an abstract data type, can be implemented using either array of linked list data structures) FIFO (first-in-first-out) like a queue of people or a print spooler. Enqueue or dequeue.
• Binary search trees: binary trees obeying the BST invariant \(v_{\text{left child}}\leq v_{\text{parent}}\leq v_{\text{right child}}\) (aka purely horizontal stratification)! As their name suggests, in a (balanced, aka not-just-a-linked-list) BST (in practice implemented via AVL/red-black) search (and hence insertion/deletion) over \(n\) elements is \(\Theta(\ln n)\).
• (Binary) Heaps: complete binary trees obeying the max heap property \(v_{\text{parent}}\geq v_{\text{left child}},v_{\text{right child}}\) or min heap property \(v_{\text{parent}}\leq v_{\text{left child}},v_{\text{right child}}\) (aka purely vertical stratification). The point of the heap property is that accessing the max (resp. min) values in an arbitrarily large max (resp. min) heap takes \(O(1)\) time which for some applications (e.g. emergency room priorities) may be desirable. Being complete, heaps are always automatically balanced (unlike BSTs).
• Tries: (also called prefix/digital trees) are tree-like data structures designed for efficient (i.e. \(O(L)\) search & insertion on input length \(L\), irrespective of total number of entries in the trie) retrieval such as in autocomplete, spellcheck, etc. Each node can be thought of as a character, so traversing through a trie either spells out a prefix or an actual word.
• Graphs: collection of vertices/nodes and (directed or undirected, possibly with weights) edges. BFS uses a queue, DFS uses a stack, Dijikstra, topological sort, etc.
• Union-Finds: (also called disjoint-sets) are tree-like structures admitting \(2\) fundamental operations: find and union (as their name suggests). The former is unary, mapping a value in some disjoint set to that set’s parent, while the latter is binary, mapping a pair of values to their respective parents (i.e. applying find to each of them) and then linking one parent to the other (loosely like taking the disjoint union \((A,B)\mapsto A\sqcup B\) of \(2\) sets). Find can be optimized using path compression, union can be optimized using union by rank, and together they entail that an arbitrary sequence of find and union operations on \(n\) elements has amortized time complexity \(O(\alpha(n))\) per operation, where \(\alpha(n)\) is the inverse Ackermann function which for all practical purposes obeys \(\alpha(n)\leq 4\) for \(n\leq\) number of atoms in the universe, hence \(O(\alpha(n))\approx O(1)\).

Problem: What is the worst-case time complexity to insert an element into a heap of size \(n\)? What is the (optimal) time complexity to heapify a binary tree of \(n\) elements?

Solution: To insert an element, one first attaches it as a new node in whatever place ensures the binary tree remains complete. Then, one bubbles the element up through the heap via comparisons with the parent node. Since the tree depth is \(\sim\log_2(n)\), the worst-case time complexity is thus \(\Theta(\ln n)\). Naturally, to heapify a binary tree of \(n\) elements, because each one individually takes \(\Theta(\ln n)\) time, the naive guess is that heapification requires \(\Theta(n\ln n)\) operations since there are \(n\) elements. However, it actually only requires \(\Theta(n)\) operations via a bottom-up approach. Specifically, at the \(h=0\) leaf node layer containing \(\sim n/2\) of all the nodes, nothing has to happen. At the \(h=1\) layer containing \(\sim n/4\) of all the nodes, each of these \(n/4\) nodes may be bubbled down by \(1\) layer, etc. more generally, at layer \(h\leq\log_2(n)\) containing \(\sim n/2^h\) nodes, the worst case requires \(h\) bubble down operations, meaning that the time complexity class is:

\[\Theta\left(\sum_{h=0}^{\log_2(n)}\frac{n}{2^h}\times h\right)=\Theta\left(n\sum_{h=0}^{\infty}\frac{h}{2^h}\right)=\Theta(2n)=\Theta(n)\]

Problem: When one hears the adjective “amortized” in a CS context, what can one synonymously replace that with?

Solution: Amortized \(=\) Worst-case per operation

Problem: Consider \(2\) distinct approaches for building dynamic arrays out of static arrays:

• Approach #\(1\): begin with a static array of fixed capacity \(k\), and when the number of insertions \(N\) exceeds \(k\), copy all \(k\) elements into a new static array of size \(2k\). Once \(N\) exceeds \(2k\), copy all \(2k\) elements into a new static array of size \(3k\), etc. incrementing \(+k\) each time.
• Approach #\(2\): begin with a static array of fixed capacity \(k\), and when the number of insertions \(N\) exceeds \(k\), copy all \(k\) elements into a new static array of size \(2k\). Once \(N\) exceeds \(2k\), copy all \(2k\) elements into a new static array of size \(4k\), etc. doubling \(\times 2\) each time.

Compute the amortized cost per insertion \(T_{\text{amort}}(N)\) of each approach, and hence state which one is more optimal.

Solution: In both cases, the total time may be decomposed as \(T(N)=T_{\text{insert}}(N)+T_{\text{copy}}(N)\), where \(T_{\text{insert}}(N)=N\) is true for both. Their difference lies in the copying cost:

• Approach #\(1\): \(T_{\text{copy}}(N)\approx k+2k+3k+…+\frac{N}{k}k=\frac{N^2}{2k}+\frac{N}{2}\)
• Approach #\(2\): \(T_{\text{copy}}(N)\approx k+2k+4k+…+2^{\log_2(N/k)}k=2N-2k\)

In the aggregate method of amortized analysis, one has \(T_{\text{amort}}(N):=T(N)/N\), so:

• Approach #\(1\): \(T_{\text{amort}}(N)=\frac{N}{2k}+\frac{3}{2}\in\Theta(N)\)
• Approach #\(2\): \(T_{\text{amort}}(N)=3-\frac{2k}{N}\in\Theta(1)\)

So the second approach is clearly favorable.

Problem: Define the \(T_1\) and \(T_{\infty}\) time complexities. State Brent’s theorem, Amdahl’s law, and Gustafson’s law.

Solution: In the work-depth model, \(T_1\) (“work”) can be thought of as the serial time while \(T_{\infty}\) (“depth”/”span”) can be thought of as the number of unavoidable operations in the limit of infinite parallelization. For instance, the following elementary parallel primitives have:

• Map: applying a function \(f\) in parallel to each of \(n\) elements requires linear work \(T_1(n)\in \Theta(n)\) and constant depth \(T_{\infty}(n)\in \Theta(1)\).
• Reduction: simplifying the sum/product/(some associative operation) of \(n\) elements in parallel requires linear work \(T_1(n)\in \Theta(n)\) and logarithmic depth \(T_{\infty}(n)\in \Theta(\ln n)\).
• Prefix sum (aka scan): running sums in parallel over \(n\) elements requires linear work \(T_1(n)\in \Theta(n)\) and logarithmic depth \(T_{\infty}(n)\in \Theta(\ln n)\) (basically just \(n\) reductions with shared structure).
• Gather: reading from \(n\) memory addresses in parallel requires linear work \(T_1(n)\in \Theta(n)\) and constant depth \(T_{\infty}(n)\in \Theta(1)\).
• Scatter: writing to \(n\) memory addresses in parallel requires linear work \(T_1(n)\in \Theta(n)\) and constant depth \(T_{\infty}(n)\in \Theta(1)\).

whereas the derived parallel primitive (using the word “primitive” and “derived” is deeply oxymoronic to me) stream compaction/parallel filtering requires linear work \(T_1(n)\in \Theta(n)\) and logarithmic depth \(T_{\infty}(n)\in \Theta(\ln n)\), being the composition of a flag map, exclusive prefix sum, and scatter.

More generally, \(p\in\{0,1,…,\infty\}\) can be any number of processors (not just \(p=1\) or \(p=\infty\)), with Brent’s theorem asserting the obvious upper bound \(T_p\leq T_{\infty}+T_1/p\).

In the strong scaling regime where the problem is fixed and the number of processors \(p\) increases, leading to an increasing serial fraction \(s\in[0,1]\) on each processor and Amdahl’s law for the maximal theoretical speedup \(\frac{T_1}{T_p}=\frac{1}{s+(1-s)/p}\) applies.

By contrast, in the weak scaling regime where the problem grows with the number of processors \(p\) causing the serial fraction \(s\) (as measured on the scaled problem in the parallel run) to shrink, leading to a linear-in-\(p\) speedup \(\frac{T_1}{T_p}=s+p(1-s)\).

Problem: Describe the following graph representations, commenting on the pros vs. cons of each:

• Adjacency matrices: given a graph \((V,E)\), the adjacency matrix \(A\in\{0,1\}^{|V|\times |V|}\) is defined by the existence of an edge between two vertices \(v,v’\in V\) i.e. \(A_{vv’}:=[(v,v’)\in E]\). Thus, \(A\) contains \(|V|^2\) elements and querying whether an edge exists between two vertices is \(O(1)\).
• Adjacency lists: ignore all the non-existent edges (i.e. null entries of the adjacency matrix) by instead just directly storing a list of each vertex’s neighbouring vertices. That is, arbitrarily index the vertices \(1,…,|V|\), then for-loop through them and just append the indices of their neighbouring vertices into one “master list” which in the end is the adjacency list containing only \(O(|V|+|E|)\) elements instead of the quadratic space complexity \(O(|V|^2)\) of an adjacency matrix.
• Compressed sparse row (CSR): adjacency lists are slow for CPU cache or GPU parallelization due to pointer-chasing the non-contiguous memory addresses of each of the \(|V|\) “neighbour sublists”. CSR solves this by forcing everything to live in contiguous memory as a static array, and introducing an offsets list to keep track of the \(|V|\) partitions in the adjacency list. This can be explicitly constructed solely using parallel primitives as follows: start from a list of the degrees (i.e. number of neighbouring vertices) of each of the \(|V|\) vertices. Do a parallel exclusive scan over these degrees to obtain another list of length \(|V|\). After appending \(|E|\) to the end of that list, thereby obtaining a list of length \(|V|+1\), that is the offsets array! Finally, do a scatter
• Coordinate list (COO):

Solution:

Fundamental Theorem of Classical Computing: The vector space \(\textbf N\) over the binary Galois field \(\textbf Z/2\textbf Z\) admits the countably infinite basis \(\textbf N=\text{span}_{\textbf Z/2\textbf Z}\{2^n:n\textbf N\}\) so that \(\text{dim}_{_{\textbf Z/2\textbf Z}}(\textbf N)=\aleph_0\). Put differently, the binary representation map \(n\in\textbf N\mapsto [n]^{(1,2,4,8,…)}\in \) is

From a physics perspective, one can loosely think of \(\textbf N\cong(\textbf Z/2\textbf Z)^{\oplus\infty}\) as the direct sum of infinitely many copies of the binary “vector space” \(\textbf Z/2\textbf Z\). By contrast, in the field of quantum computing, one instead has a vector space of the form \((\textbf C^2)^{\otimes N}\) for \(N\) qubits…and the multiplicative structure of the tensor product is much richer than the additive structure of the direct sum, hence the interest in quantum computing.

Knowing all this, it follows that any data \(X\) (e.g. an image file, an audio file, etc.) which can simply be “reduced to numbers” by some injection \(f:X\to\textbf N\) is also in principle just reduced to some bit string \((b_k)_{k=0}^\infty\) simply by taking each \(f(x)\in\textbf N\) for \(x\in X\) and writing out the binary representation of \(f(x)\). For instance, when \(X=\{a,b,c,…,x,y,z\}\) is the alphabet, then one possible injection (or encoding) is called the American Standard Code for Information Interchange \(\text{ASCII}:\{a,b,c,…,x,y,z\}\to\textbf N\) which maps for instance \(\text{ASCII}(a):=97\), \(\text{ASCII}(b):=98\), and so forth (strictly speaking, ASCII uses \(7\) bits to represent \(2^7=128\) characters of which \(26\) are the usual English alphabet letters in lower case while another \(26\) are uppercase English letters. There was even an extended ASCII which used \(8\) bits to represent \(2^8=256\) characters, but ultimately that was clearly insufficient for things like the Chinese language and so nowadays Unicode (with UTF-8 encoding, which stands for Unicode Transformation Format – 8 bit, or UTF-16, UTF-32, etc.) tends to be used in lieu of ASCII).

When storing numbers in memory (e.g. RAM, HDD, SSD) a computer can experience overflow error (most computers have \(64\)-bit architecture, so can safely store up to \(2^{64}-1\)), roundoff error (this is especially relevant to floating point arithmetic), and precision errors.

An analog-to-digital converter (ADC) is just an abstraction for any function that maps an analog signal \(V(t)\), \(I(x,y)\), etc. to a digital signal \(\bar V_i,\bar I_{ij}\), etc. More precisely, one can consider an ADC to be a pair \(\text{ADC}=(f_s,\rho)\) where \(f_s\) is the sampling rate of the ADC in samples/second and \(\rho\) is the bit depth/resolution/precision at which the ADC quantizes data in bits/sample, thus the bit rate \(\dot b\) of the ADC is \(\dot b=f_s\rho\) and this is in general distinct from the baud rate \(\dot{Bd}\) of serial communication with the ADC by a factor \(\lambda:=\frac{\dot b}{\dot{Bd}}\geq 1\) which describes the number of bits per baud (see this Stack Overflow Q&A for an idea of the distinction).

For \(V(t)\) an analog signal in the time domain which is bandlimited by some bandwidth \(\Delta f\), the Nyquist-Shannon sampling theorem asserts that in order to avoid aliasing distortions when sampling \(V(t)\), one has to use \(f_s>\Delta f\). Equivalently, if \(f^*=\Delta f/2\) is the largest frequency present in \(V(t)\), then the sampling frequency needs to obey \(f_s>2f^*\). For instance, humans can hear audio up to \(f^*=20\text{ kHz}\), so audio ADCs (a fancy way of saying microphones) sample at \(f_s=48\text{ kHz}\). Cameras are just image ADCs, where now “samples” is replaced by “pixels” and so \(f_s\) might be better called “pixel frequency” (with units of pixels/meter rather than samples/second?) and the use of the RGB color space is fundamentally based on the biology of the human eye and its \(3\) types of cone cells, and conventionally each R, G, B channel has \(256\) levels (or \(1\) byte) of intensity quantization simply because that was empirically found to be sufficient (so the total bit depth of an RGB image is \(\rho=3\) bytes/pixel or \(24\) bits/px.

In practice, such data would likely be further compressed (either via lossless or lossy data compression algorithms). For instance, JPEG (lossy), PNG (lossless), run-length encoding (lossless), etc. for digital/bitmap/raster images, Lempel-Ziv-Welch (LZW) (lossless) compression, Huffman encoding (lossless), byte pair encoding, for text files, and perceptual audio encoding (lossy) which exploits the psychoacoustic quirks of the human auditory system such as auditory masking and high frequency limits.

Computers & Logic Circuits

One abstract paradigm for understanding how a computer works is: input\(\to\)storage + processing\(\to\)output. Input is typically taken from sensors (e.g. keyboards, mouses, touchscreens, microphones, cameras), memory is handled by RAM, storage is handled by HDD/SSD, processing is done by the central processing unit (CPU) (an integrated circuit (IC)) where CPU = control unit + arithmetic logic unit (ALU) (both storage and processing use logic circuits made of many logic gates combined together), and output is a monitor, a speaker, an electric motor, an LED etc. Processing + memory are heavily interdependent, connected by a memory bus.

This excellent YouTube demonstration of implementing standard logic gates (e.g. buffers, NOT gates, AND gates, OR gates, XOR gates, NAND gates, NOR gates, etc.) using standard hardware on a solderless breadboard, notably transistors. So really, when it comes to processing data, a “computer” is an abstraction over “logic circuits” which itself is an abstraction over “logic gates” which itself is an abstraction over “bits” which itself is an abstraction over transistors and physical hardware that one actually touch and feel in the real world.

Our current computer (Microsoft Surface Studio \(2\)) has \(\sigma_{\text{RAM}}=32\text{ GB}\) and \(\sigma_{\text{SSD or C-Drive}}=1\text{ TB}\) (with Microsoft OneDrive providing an additional \(\sigma_{\text{OneDrive}}=1\text{ TB}\) of storage space).

The Internet

A computer network is topologically any strongly connected undirected graph where nodes represent computing devices (e.g. computers, phones, etc.) and edges are communication channels between a pair of computers. Common network topologies include the ring, star, mesh, bus, and tree topologies. Examples of computer networks include local area networks (LAN), wide area networks (WAN), data center networks (DCN), etc. with the Internet being a distributed packet-switched WAN. When designing the architecture of a computer network, one is interested in minimizing the distance (with respect to a suitable metric) that any piece of data \(D\) must travel to get from one computer to another.

At the level of physical hardware, data can be communicated between computers via copper category 5 (CAT5) twisted pair cables adhering to Ethernet standards. Fiber optic cables can also be used with Ethernet standards. Wi-Fi or Bluetooth communicates data via radio waves which suffer attenuation. Regardless, for all \(3\) of these line coding schemes (maps from abstract bits to a digital signal in the real world) we need to thank James Clerk Maxwell.

The informal notion of the “speed” of an internet connection (i.e. one of the communication channels mentioned earlier) between two computing devices \(X, Y\) is made precise by the bit rate \(\dot b_{(X,Y)}\) between the computing devices \(X\) and \(Y\). The bandwidth of that communication channel is then just the maximum bit rate \(\dot b^*_{(X,Y)}\) between \(X\) and \(Y\) (not to be confused with the signal processing notion of the bandwidth \(\Delta f\) of an analog signal). Another important factor is the latency \(\Delta t_{(X,Y)}\) of a given communication channel (i.e. just the delay). Running an Internet speed test for my computer with the measurement lab (M-lab) yields \(\dot b^{\text{downloads}}_{\text{(computer,M-lab)}}=650.7\frac{\text{Mb}}{\text s}\) and \(\dot b^{\text{uploads}}_{\text{(computer,M-lab)}}=732.0\frac{\text{Mb}}{\text s}\) and a latency of \(\Delta t_{\text{(computer,M-lab)}}=4\text{ ms}\)

Just like every house \(H\) has a physical address \(A_H\), in the WAN that we call the Internet, every computing device \(X\) has an Internet Protocol (IP) address \(\text{IP}_X\). When a computing device \(X\) transmits data packets \(D\) across a communication channel to another computing device \(Y\), \(X\) must specify the IP address \(\text{IP}_Y\) of \(Y\) in addition to providing its own IP address \(\text{IP}_X\) so that \(Y\) can reply to it. There are actually \(2\) common IP address protocols, IPv4 (a string of \(4\) bytes, leading to \(2^{32}\) possible IPv4 addresses) and IPv6 (a string of \(8\) hexadecimal numbers each up to \(0xFFFF\) for a total of \(2^{128}\) possible IPv6 addresses). IP addresses of computing devices may also be dynamic meaning that one’s Internet service provider changes it over time \(t\). Or, if one connects to a disjoint Wi-Fi network, then this will usually also mean a different IP address as each Wi-Fi provider (internet service provider) has a range of IP addresses it is allowed to allocate. By contrast, computing devices acting as servers (e.g. Google’s computers) often have static IP addresses (e.g. \(\text{IPv4}_{\text{Google computers}}=74.125.20.113\)) to make it easier for client computing devices to communicate quickly with.

In terms of actually interpreting what the numbers in an IP address mean, it turns out that it doesn’t have to be the case that (say in an IPv4 address) each byte corresponds to some piece of information. Rather, one can decide how one wishes to impose a hierarchy of subnetworks (subnets) on the IP address, that is, how many bits to represent a given piece of information. This is sometimes known as “octet splitting” where “octet” = “byte” in an IPv4 address.

The Domain Name System (DNS) is essentially a map \(\text{DNS}:\{\text{URLs}\}\to\{\text{IP addresses}\}\) and indeed anytime one uses a browser application (e.g. Chrome) to search for a website URL (e.g. www.youtube.com), DNS servers need to first find the IP address \(\text{DNS}\)(www.youtube.com) associated with that URL.