forked from gcallah/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
TheRoleOfAlgorithms.html
261 lines (234 loc) · 8.37 KB
/
TheRoleOfAlgorithms.html
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
<html>
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms, Introduction
</title>
</head>
<body>
<div id="header">
<div id="logo">
<img src="graphics/Julia.png">
</div>
<div id="user-tools">
<a href="index.html">Home</a>
<a href="about.html">About</a>
<a href="feedback.html">Feedback</a>
</div>
</div>
<h1>
Design and Analysis of Algorithms: The Role of Algorithms
<a href="#note1">*</a>
</h1>
<details>
<summary class="sum1">
Introduction
</summary>
<p>
Syllabus: Logistics, grading, exams, homeworks, cheating.
</p>
</details>
<details>
<summary class="sum1">
We will study algorithms.
</summary>
<p>
<b>What's an algorithm?</b>
A carefully written recipe.<br>
We need to agree what steps are allowed in a recipe.<br>
We need to agree what problem the recipe is solving, ahead of time.<br>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Euclid_flowchart.svg/220px-Euclid_flowchart.svg.png">
</p>
</details>
<details>
<summary class="sum1">
Important considerations
</summary>
<p>
Things to keep in mind about algorithms (when analyzing and/or designing them):
</p>
<details>
<summary class="sum2">
Termination
</summary>
<p>
On any legal (meaning, consistent with algorithm specification) input,
the procedure you are describing should always eventually stop, or <i>terminate</i>.
(In this course we will not talk about algorithms that are intended to run "forever,"
such as the scheduler in an operating system.)
</p>
</details>
<details>
<summary class="sum2">
Correctness
</summary>
<p>
On any legal input, provided the procedure has terminated,
the result that it produces has to be correct. Not <em>sometimes</em> correct,
not <em>mostly</em> correct, but <em>always</em> correct.
</p>
</details>
<details>
<summary class="sum2">
Performance
</summary>
<p>
You can measure performance in many different ways.
The course will focus on the running time,
but there are many others: space (memory use),
disk use, amount of disk-memory communication,
number of processors in a parallel program,
total amount of work in a parallel program,
number of cores in a multi-core program,
total amount of communication in a distributed program,
power consumed in an algorithm tuned to low-power devices and many many others.
So in short, when you describe a recipe for doing something, make sure it always stops,
make sure it always produces correct answers, and only after that worry about how
efficient it is. (Depending on the algorithm, some or all of these are very
easy, and some may not be obvious at all. We will see examples later.)
</p>
</details>
</details>
<details>
<summary class="sum1">
Characteristics of our analysis
</summary>
<details>
<summary class="sum2">
Running time
</summary>
<p>
We surely do not want to talk about actual time
in nanoseconds, as that depends on too many external things: what other
processes are running, details of the hardware, compiler switches, etc, etc.
So instead we come up with a very primitive <em>abstract machine</em> (RAM=the
Random Access Machine: CPU + directly addressable memory) which we analyze instead
of a real computer. Then primitive operations are memory reads/writes and operations
in the CPU, such as address arithmetic, additions, multiplications, divisions,
etc. Our idea of "running time" is then simply the number of operations
performed when the program runs.
</p>
</details>
<details>
<summary class="sum2">
More trouble
</summary>
<p>
Even for inputs of a fixed size (saying, your favorite program
sorting 10 numbers), different specific inputs will produce different performance.
For example, a clever algorithm may notice that the input is already sorted
and not try sorting it again. So, we distinguish between best- and worst-case
performance (minimum and maximum number of operations performed by the algorithm,
over all possible legal inputs of a given size). (There is also the concept of
"average-case," but it is tricky, as it requires a definition of what average
means: technically, you need to specify a <i>distribution</i> of the inputs.
We will mostly stay away from average-case analysis and focus on the worst case;
we will occasionally look at the best case too.)
</p>
</details>
<details>
<summary class="sum2">
Generalized statement of running time
</summary>
<br>
<p>
What we really want, is not the running time (as the number of operations,
say, in the worst case), for a specific input size, but as a function of the
input size, over all sizes. For example, it may be that a given sorting
algorithm requires <em>4n<sup>2</sup> + 4n + 24</em> operations to sort <em>n</em> items.
</p>
</details>
<details>
<summary class="sum2">
Asymptotic behavior
</summary>
<p>
In order to make life easier, we will not be focusing on the exact value of
such function, but on its <i>asymptotic</i> behavior.
<br>
<br>
<center>
<img
src="https://upload.wikimedia.org/wikipedia/commons/thumb/7/7e/Comparison_computational_complexity.svg/250px-Comparison_computational_complexity.svg.png">
</center>
</p>
</details>
<details>
<summary class="sum2">
Highest power of n
</summary>
<p>
In particular, we want to focus on the highest power of n in any
function expressing the run time of an algorithm. That is because, as
input size grows, that power will dwarf all others in significance.
Consider the contribution of <em>n<sup>2</sup></em>
and <em>n</em> in the runtime of the
sorting algorithm mentioned above for various values of <em>n</em>:
</p>
<table>
<tr>
<th>
n
</th>
<th>
n<sup>2</sup>
</th>
</tr>
<tr>
<td>10</td>
<td>100</td>
</tr>
<tr>
<td>100</td>
<td>10,000</td>
</tr>
<tr>
<td>1000</td>
<td>1,000,000</td>
</tr>
<tr>
<td>10,000</td>
<td>100,000,000</td>
</tr>
<tr>
<td>100,000</td>
<td>10,000,000,000</td>
</tr>
</table>
<p>
Now consider that Amazon is processing tens of millions of transactions
per day: of what significance is the <em>n</em> factor in the performance
of their servers, if they are using an algorithm with an
<em>n<sup>2</sup></em> factor involved to sort them?
</p>
</details>
<details>
<summary class="sum2">
An example
</summary>
<p>
An example of a toy algorithmic problem and how to solve it, analyze it etc etc.
<br>
Who has the same birthday in class?
</p>
</details>
</details>
<p>
<a name="note1">* Based on Prof. Boris Aronov's lecture notes. </a>
<br>
<a name="note2">** Material drawn from Khan Academy and
https://en.wikipedia.org/wiki/Big_O_notation.</a>
</p>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-97026578-2', 'auto');
ga('send', 'pageview');
</script>
</html>