-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcs341.html
More file actions
111 lines (111 loc) · 8.93 KB
/
cs341.html
File metadata and controls
111 lines (111 loc) · 8.93 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
<head>
<meta charset="utf-8" />
<meta name="generator" content="pandoc" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
<title>cs341</title>
<style type="text/css">
code{white-space: pre-wrap;}
span.smallcaps{font-variant: small-caps;}
span.underline{text-decoration: underline;}
div.column{display: inline-block; vertical-align: top; width: 50%;}
</style>
<link rel="stylesheet" href="../pandoc.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.js"></script>
<script>document.addEventListener("DOMContentLoaded", function () {
var mathElements = document.getElementsByClassName("math");
for (var i = 0; i < mathElements.length; i++) {
var texText = mathElements[i].firstChild;
if (mathElements[i].tagName == "SPAN") { katex.render(texText.data, mathElements[i], { displayMode: mathElements[i].classList.contains("display"), throwOnError: false } );
}}});</script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.9.0/katex.min.css" />
<!--[if lt IE 9]>
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
<![endif]-->
</head>
<body>
<h1 id="cs-341">CS 341</h1>
<p>An <strong>algorithm</strong> is a well-defined procedure to solve a computational problem.</p>
<h2 id="review-of-asymptotic-notation">Review of Asymptotic Notation</h2>
<p><span class="math inline">T(n) \in O(f(n))</span> if and only if <span class="math inline">\exists</span> two positive constants <span class="math inline">c, n_0</span> such that <span class="math inline">\forall n \ge n_0</span>, <span class="math inline">T(n) \le c\cdot f(n)</span>.</p>
<p>Example: <span class="math inline">T(n) = \sum_{i=0}^k a_i n^i \in O(n^k)</span>, <span class="math inline">a_k > 0</span>.</p>
<blockquote>
<p><span class="math display">\begin{aligned}T(n) &\le \sum_{i=0}^k|a_i|n^i \\ &= n^k\sum_{i=0}^k|a_i|\end{aligned}</span> So for <span class="math inline">c = \sum_{i=0}^k|a_i|, n_0 = 1</span>, <span class="math inline">T(n) \in O(n^k)</span>.</p>
</blockquote>
<p><span class="math inline">T(n) \in \Omega(f(n))</span> if and only if <span class="math inline">\exists c, n_0 > 0</span> such that <span class="math inline">\forall n \ge n_0, T(n) \ge c\cdot f(n)</span>.</p>
<p>Example: <span class="math inline">T(n) = \sum_{i=0}^k a_i n^i \in \Omega(n^k)</span>.</p>
<blockquote>
<p>Let us guess <span class="math inline">c = \frac{a_k}{2}</span>. <span class="math display">\begin{aligned}\sum_{i=0}^ka_in^i &\ge \frac{a_k}{2}n^k \\ n &\ge \sum_{i=0}^{k-1} \frac{-2a_in^i}{a_k n^{k-1}}\end{aligned}</span> The problem is that the sum is not a constant so it cannot be <span class="math inline">n_0</span>. <span class="math display">n = \sum_{i=0}^k\left|\frac{2a_i}{a_k}\right|</span></p>
</blockquote>
<p><span class="math inline">T(n) \in \Theta(f(n))</span> if and only if <span class="math inline">T(n) \in O(f(n))</span> and <span class="math inline">T(n) \in \Omega(f(n))</span>.</p>
<p><span class="math inline">T(n) \in o(f(n))</span> if and only if <span class="math inline">\forall c > 0, \exists n_0</span> such that <span class="math inline">\forall n \ge n_0 T(n) \le c \cdot f(n)</span>.</p>
<p><span class="math inline">T(n) \in \omega(f(n))</span> if and only if <span class="math inline">\forall c > 0, \exists n_0</span> such that <span class="math inline">\forall n \ge n_0, T(n) \ge c\cdot f(n)</span>.</p>
<h3 id="limits">Limits</h3>
<p><span class="math inline">T(n) \in o(f(n))</span> iff <span class="math inline">\lim_{n\to \infty}\frac{T(n)}{f(n)} = 0</span>.</p>
<p><span class="math inline">T(n) \in \omega(f(n))</span> iff <span class="math inline">\lim_{n\to \infty}\frac{T(n)}{f(n)} = \infty</span>.</p>
<p><span class="math inline">T(n) \in \Theta(f(n))</span> iff <span class="math inline">\lim_{n\to\infty}\frac{T(n)}{f(n)} = c > 0</span>.</p>
<h2 id="important-summations">Important Summations</h2>
<ol type="1">
<li><span class="math inline">\sum_{i=1}^n i = \frac{n}{n-1}{2} \in \Theta(n^2)</span>.</li>
<li><span class="math inline">\sum_{i=1}^n i^2 = \frac{n}{n+1}{2n + 1}{6} \in \Theta(n^3)</span>.</li>
<li><span class="math inline">\sum_{i=1}^ni^d \in \Theta(n^{d + 1})</span>.</li>
<li><span class="math inline">\sum_{i=1}^nc^i = \frac{c^{k-1} -1}{c-1} \in \begin{cases}\Theta(c^k), c > 1\\ \Theta(1), c < 1\\ \Theta(k), c = 1\end{cases}</span></li>
<li><span class="math inline">\sum_{i=1}^n \frac{1}{i} \in \Theta(\log n)</span>.</li>
<li><span class="math inline">\log(n!) = n\log n - \Theta(n)</span>, by Stirling’s formula.</li>
</ol>
<h1 id="reductions">Reductions</h1>
<blockquote>
<p>Solving a computational problem <span class="math inline">C_1</span> by using an algorithm that solves a problem <span class="math inline">C_2</span>.</p>
</blockquote>
<p>An equation or an inequality that describes a function <span class="math inline">T(n)</span> in terms of <span class="math inline">T</span>’s value on inputs smaller than <span class="math inline">n</span> and a base case.</p>
<p>Example: MergeSort.</p>
<blockquote>
<p><span class="math inline">T(n) \le 2T(\frac{n}{2}) + 7n</span>, <span class="math inline">T(2) = 2</span>.</p>
</blockquote>
<h2 id="solving-reccurences">Solving Reccurences</h2>
<ol type="1">
<li>Proof by induction.</li>
<li>Recursion tree method.</li>
<li>Master theorem.
<ul>
<li>If the input is of the form <span class="math inline">T(n) \le aT(\frac{n}{b}) + f(n)</span>.</li>
</ul></li>
</ol>
<h3 id="induction">Induction</h3>
<p>Exampe: Median-of-Medians.</p>
<p><span class="math display">T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + n, T(1) = 1</span></p>
<blockquote>
<p><strong>Claim</strong>: <span class="math inline">T(n) \le 10n</span>.</p>
<p><strong>Base Case</strong>: <span class="math inline">T(1) = 1 < 10</span>.</p>
<p><strong>Induction Hypothesis</strong>: <span class="math inline">\forall k < n, T(k) \le 10k</span>.</p>
<p><span class="math display">\begin{aligned}T(n) &\le \frac{10n}{5} + \frac{70n}{10} + n\\ &= 2n + 7n + n\\ &= 10\end{aligned}</span></p>
</blockquote>
<h3 id="master-theorem">Master Theorem</h3>
<p>We observed using the recursion tree method, that there are three possibilities in the overall runtime analysis.</p>
<ol type="1">
<li>Work at each level stays the same.</li>
<li>Work increases per level and work at the leaves dominate.</li>
<li>Work keeps decreasing per level and the work at the root dominates.</li>
</ol>
<p>Assume all subproblems are of equal size.</p>
<p><span class="math inline">T(n) \le aT(\frac{n}{b}) + O(n^d), T(1) \le 1</span>, where <span class="math inline">a</span> is the number of recursive calls, <span class="math inline">b</span> is the input size shrinkage order, and <span class="math inline">d</span> is the exponent in the work done at the combine step.</p>
<p><span class="math display">T(n) \in \begin{cases}
O(n^d \log(n)),\ &a = b^d \\
O(n^{\log_b(a)}),\ &a > b^d \\
O(n^d),\ &a < b^d \\
\end{cases}</span></p>
<p><strong>Proof</strong>. Assume for simplicity that <span class="math inline">n</span> is a power of <span class="math inline">b</span>. We have <span class="math inline">\log_b(n)</span> levels, with <span class="math inline">a^{\log_b(n)}</span> leaves. The total work done at each level <span class="math inline">j</span> is <span class="math inline">a^j(\frac{n}{b})^d</span> so the total work is.</p>
<p><span class="math display">\begin{aligned}\sum_{j=0}^{\log_b(n)}a^j\frac{n^d}{b^{jd}} &= cn^d\sum_{j=0}^{\log_b(n)} \left(\frac{a}{b^d}\right)^j\end{aligned}</span></p>
<p>We can obtain the runtimes by checking the convergence of the above sum.</p>
<h2 id="d-maxima">2D Maxima</h2>
<p><strong>Input</strong>: Set <span class="math inline">P</span> of <span class="math inline">n</span> 2D points.</p>
<p><strong>Output</strong>: All maximal points. <span class="math inline">p</span> is maximal if there is no such <span class="math inline">p^\prime</span> that dominates <span class="math inline">p</span> (<span class="math inline">p^\prime.x > p.x \cap p^\prime.y > p.y)</span>.</p>
<h2 id="integer-multiplication">Integer Multiplication</h2>
<p><strong>Input</strong>: 2 <span class="math inline">n</span>-digit integers <span class="math inline">X, Y</span>.</p>
<p><strong>Output</strong>: <span class="math inline">Z = XY</span>.</p>
<p>Let <span class="math inline">X = a10^{\frac{n}{2}} + b</span>, <span class="math inline">Y = c10^\frac{n}{2} + d</span>. So <span class="math inline">XY = ac10^n + (ad + bc)10^\frac{n}{2} + bd</span>. We have a divide and conquer algorithm.</p>
<p><span class="math display">T(n) \le 4T\left(\frac{n}{2}\right) + O(n)</span></p>
<p><span class="math inline">a = 4, b = 2, d = 1</span>, so <span class="math inline">O(n^{\log_2(4)}) = O(n^2)</span> by Master Theorem. Which is not faster than the naive approach.</p>
</body>
</html>