-
Notifications
You must be signed in to change notification settings - Fork 54
/
TheRoleOfAlgorithms.html
153 lines (138 loc) · 4.43 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
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
<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:
</p>
<ul>
<li>
space (memory use)
</li>
<li>
disk use, amount of disk-memory communication
</li>
<li>
number of processors in a parallel program
</li>
<li>
total amount of work in a parallel program
</li>
<li>
number of cores in a multi-core program
</li>
<li>
total amount of communication in a distributed program
</li>
<li>
power consumed in an algorithm tuned to low-power devices
</li>
<li>
many others
</li>
</ul>
<p>
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>
<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>