t.js

</code ></pre ><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129220744.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129220744.png" alt="Pasted image 20240129220744" loading="lazy"></a></p><h3 id="master-theorem"><span class="me-2">Master Theorem</span><a href="#master-theorem" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><p>The Master Theorem provides a way to solve recurrence relations in which recursive calls decrease problem size by a constant factor. Given a recurrence relation of the form $T(n) = aT(n/b)+ f(n)$ and $T(1) = Θ(1)$, with branching factor $a ≥ 1$, problem size reduction factor $b &gt; 1$, and asymptotically non-negative function $f(n)$, the Master Theorem gives the solution to the recurrence by comparing $f(n)$ to $a^{log_bn} = n^{log_b a}$, the number of leaves at the bottom of the recursion tree. When $f(n)$ grows asymptotically faster than $n^{log_b a}$, the work done at each level decreases geometrically so the work at the root dominates; alternatively, when $f(n)$ grows slower, the work done at each level increases geometrically and the work at the leaves dominates. When their growth rates are comparable, the work is evenly spread over the tree’s $O(log\;n)$ levels.</p><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230025.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230025.png" alt="Pasted image 20240129230025" loading="lazy"></a></p><p>The Master Theorem takes on a simpler form when $f(n)$ is a polynomial, such that the recurrence has the from $T(n) = aT(n/b) + Θ(n^c)$ for some constant c ≥ 0.</p><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230307.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230307.png" alt="Pasted image 20240129230307" loading="lazy"></a></p><p>This special case is straight-forward to prove by substitution (this can be done in recitation). To apply the Master Theorem (or this simpler special case), you should state which case applies, and show that your recurrence relation satisfies all conditions required by the relevant case. There are even stronger (more general) formulas1 to solve recurrences, but we will not use them in this class.</p><h2 id="lecture-4-hashing"><span class="me-2">Lecture 4: Hashing</span><a href="#lecture-4-hashing" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h2><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230539.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129230539.png" alt="Pasted image 20240129230539" loading="lazy"></a></p><h3 id="comparison-model"><span class="me-2">Comparison Model</span><a href="#comparison-model" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>In this model, assume algorithm can only differentiate items via comparisons<li><strong>Comparable items</strong>: black boxes only supporting comparisons between pairs<li>Comparisons are $&lt;, ≤, &gt;, ≥, \neq, =$, outputs are binary: True or False<li><strong>Goal</strong>: Store a set of n comparable items, support find(k) operation<li>Running time is <strong>lower bounded</strong> by # comparisons performed, so count comparisons!</ul><h3 id="decision-tree"><span class="me-2">Decision Tree</span><a href="#decision-tree" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>Any algorithm can be viewed as a <strong>decision tree</strong> of operations performed<li>An internal node represents a <strong>binary comparison</strong>, branching either True or False<li>For a comparison algorithm, the decision tree is binary (draw example)<li>A leaf represents algorithm termination, resulting in an algorithm <strong>output</strong><li>A <strong>root-to-leaf path</strong> represents an <strong>execution of the algorithm</strong> on some input<li>Need at least one leaf for each <strong>algorithm output</strong>, so search requires ≥ n + 1 leaves</ul><h3 id="comparison-search-lower-bound"><span class="me-2">Comparison Search Lower Bound</span><a href="#comparison-search-lower-bound" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>What is worst-case running time of a comparison search algorithm?<li>running time ≥ # comparisons ≥ max length of any root-to-leaf path ≥ height of tree<li>What is minimum height of any binary tree on ≥ n nodes?<li>Minimum height when binary tree is complete (all rows full except last)<li>Height $\geq\lceil lg(n + 1)\rceil − 1 = Ω(log\;n)$, so running time of any comparison sort is $Ω(log\;n)$<li>Sorted arrays achieve this bound! Yay!<li>More generally, height of tree with $Θ(n)$ leaves and max branching factor b is $Ω(log_b n)$<li>To get faster, need an operation that allows super-constant $ω(1)$ branching factor. How??</ul><h3 id="direct-access-array"><span class="me-2">Direct Access Array</span><a href="#direct-access-array" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>Exploit Word-RAM $O(1)$ time random access indexing! Linear branching factor!<li><strong>Idea</strong>! Give item <strong>unique</strong> integer key $k$ in ${0, . . . , u − 1}$, store item in an array at index $k$<li>Associate a meaning with each index of array<li>If keys fit in a machine word, i.e. $u ≤ 2^w$, worst-case $O(1)$ find/dynamic operations! Yay!<li>Anything in computer memory is a binary integer, or use (static) 64-bit address in memory<li>But space $O(u)$, so really bad if $n \ll u$… :(<li><strong>Example</strong>: if keys are ten-letter names, for one bit per name, requires $26^{10} ≈ 17.6 TB$ space<li>How can we use less space?</ul><h3 id="hashing"><span class="me-2">Hashing</span><a href="#hashing" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>Idea! If $n \ll u$, map keys to a smaller range $m = Θ(n)$ and use smaller direct access array<li><strong>Hash function</strong>: $h(k) : {0, . . . , u - 1} → {0, . . . , m - 1}$ (also hash map)<li>Direct access array called <strong>hash table</strong>, h(k) called the <strong>hash</strong> of key k<li>If $m \ll u$, no hash function is injective by pigeonhole principle<li>Always exists keys a, b such that h(a) = h(b) → <strong>Collision</strong>! :(<li>Can’t store both items at same index, so where to store? Either: - store somewhere else in the array (<strong>open addressing</strong>) - complicated analysis, but common and practical - store in another data structure supporting dynamic set interface (<strong>chaining</strong>)</ul><h3 id="chaining"><span class="me-2">Chaining</span><a href="#chaining" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li><strong>Idea</strong>! Store collisions in another data structure (a chain)<li>If keys roughly evenly distributed over indices, chain size is $n/m = n/Ω(n) = O(1)$ - If chain has $O(1)$ size, all operations take $O(1)$ time! Yay!<li>If not, many items may map to same location, e.g. $h(k)$ = constant, chain size is $Θ(n)$ :(<li>Need good hash function! So what’s a good hash function?</ul><h3 id="hash-functions"><span class="me-2">Hash Functions</span><a href="#hash-functions" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><p><strong>Division</strong> (bad): $h(k) = k\;mod\;m$</p><ul><li>Heuristic, good when keys are uniformly distributed!<li>$m$ should avoid symmetries of the stored keys<li>Large primes far from powers of 2 and 10 can be reasonable<li>Python uses a version of this with some additional mixing<li>If $u \gg n$, every hash function will have some input set that will a create $O(n)$ size chain<li><strong>Idea</strong>! Don’t use a fixed hash function! Choose one randomly (but carefully)!</ul><p><strong>Universal</strong> (good, theoretically): $h_{ab}(k) = (((ak + b)\;mod\;p)\;mod\;m)$</p><ul><li><div class="table-wrapper"><table><tbody><tr><td>Hash Family $\mathcal{H}(p, m) = {h_{ab}<td>a, b \in {0, . . . , p -1}\;and\;a \neq 0}$</table></div><li>Parameterized by a fixed prime $p &gt; u$, with a and b chosen from range ${0, . . . , p - 1}$<li>$\mathcal{H}$ is a <strong>Universal</strong> family: $Pr_{h\in H} {h(k_i) = h(k_j)} \leq 1/m\;\;\;\;\forall k_i \neq k_j \in {0, … , u -1}$<li>Why is universality useful? Implies short chain lengths! (in expectation)<li>$X_{ij}$ indicator random variable over $h \in \mathcal{H}: X_{ij} = 1\;\;if\;h(k_i) = h(k_j ), X_{ij} = 0$ otherwise<li>Size of chain at index $h(k_i)$ is random variable $X_i = \sum_j X_{ij}$<li>Expected size of chain at index $h(k_i)$</ul><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129232955.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129232955.png" alt="Pasted image 20240129232955" loading="lazy"></a></p><ul><li>Since $m = \Omega(n)$, load factor $\alpha = n/m = O(1)$, so $O(1)$ in expectation!</ul><h3 id="dynamic"><span class="me-2">Dynamic</span><a href="#dynamic" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>If $n/m$ far from 1, rebuild with new randomly chosen hash function for new size m<li>Same analysis as dynamic arrays, cost can be <strong>amortized</strong> over many dynamic operations<li>So a hash table can implement dynamic set operations in expected amortized $O(1)$ time! :)</ul><p><a href="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129233223.png" class="popup img-link shimmer"><img src="https://breath203.oss-cn-hangzhou.aliyuncs.com/img/Pasted%20image%2020240129233223.png" alt="Pasted image 20240129233223" loading="lazy"></a></p><h2 id="lecture-5-linear-sorting"><span class="me-2">Lecture 5: Linear Sorting</span><a href="#lecture-5-linear-sorting" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h2><h3 id="direct-access-array-sort"><span class="me-2">Direct Access Array Sort</span><a href="#direct-access-array-sort" class="anchor text-muted"><i class="fas fa-hashtag"></i></a></h3><ul><li>Example: [5, 2, 7, 0, 4]<li>Suppose all keys are <strong>unique</strong> non-negative integers in range {0, . . . , u − 1}, so n ≤ u<li>Insert each item into a direct access array with size u in $Θ(n)$<li>Return items in order they appear in direct access array in $Θ(u)$<li>Running time is $Θ(u)$, which is $Θ(n)$ if $u = Θ(n)$. Yay!</ul><pre><code class="language-Python">def direct_access_sort(A):