forked from gcallah/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathMidTerm.html
353 lines (326 loc) · 14.3 KB
/
MidTerm.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
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
<html>
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Design and Analysis of Algorithms Midterm
</title>
</head>
<body>
<h1>
Design and Analysis of Algorithms Midterm
</h1>
<h2>
Problems
</h2>
<ol>
<li>Write pseudo-code for a double hasing scheme. You may simply
call your hashing functions h1() and h2(). (In other words, you
needn't actually write the hashing functions.)
<br> <br> <br> <br> <br> <br> <br>
<a
href="https://github.com/gcallah/algorithms/blob/master/python/hash.py">
Example code here.
</a>
<br> <br> <br> <br> <br> <br> <br>
<li>What operations do we want in the ADT <em>iterator</em>?
Consider including rewind() in the ADT: is it always going to
be possible to implement it? If "no," in which situations
would it not be possible?
<br> <br> <br> <br> <br>
<ul>
<li>Get iterator.
<li>Get next value.
<li>Detect end of iterables.
</ul>
<br>
Can't rewind if data is gone, e.g., live stock feed.
<br> <br> <br> <br> <br> <br>
<li>Let us say we have an algorithm that runs in 8(lg n) + 10 time.
We want to show its order of complexity is θ(lg n). Give
an example of a set of k<sub>1</sub>, k<sub>2</sub>,
and n<sub>0</sub> that would do this, so that k<sub>1</sub>
* lg n < 8(lg n) + 10 < k<sub>2</sub> * lg n.
<br> <br> <br> <br>
Example values:
<br>
k<sub>1</sub> = 9
<br>
k<sub>2</sub> = 7
<br>
n<sub>0</sub> = 2048
<br> <br> <br> <br> <br>
<li>Imagine you have an 8-sided die, numbered 1 through 8. Use an
indicator random variable to show how many 8s we expect to get
in 100 rolls.
<br> <br> <br> <br>
<a href="Probability.html#dice">See here for example</a>.
<br> <br> <br> <br> <br>
<li>Draw the binary search tree that arises from inserting, in
order:
24, 32, 10, 6, 88, 20, 28, 22, 1, 99
<br> <br> <br> <br> <br> <br> <br> <br> <br> <br> <br>
<li>In the above tree, describe the process by which we find the
successor of 22.
<br> <br> <br> <br> <br> <br> <br> <br> <br>
<li>Use an indicator random variable to show how many numbers we
have to pick from a set of <em>n</em> numbers before we are
more likely than not to have drawn the same number twice.
<br> <br> <br> <br>
<a href="Rand.html#birthday">See here for example</a>.
<br> <br> <br> <br> <br>
<li>Write pseudo-code for a hash table (you can just assume a hash
function of h) that resolves collisions by chaining, and that
looks up (possibly chained) key value and returns the
associated data.
<br> <br> <br> <br> <br> <br> <br> <br>
<a
href="https://github.com/gcallah/algorithms/blob/master/python/hash.py">
Example code here.
</a>
<br> <br> <br> <br> <br> <br> <br> <br>
<li>Write pseudo-code to search a BST for a particular key.
<br> <br> <br> <br> <br> <br> <br>
<br> <br> <br> <br> <br> <br> <br>
<li>The logistic equation is
x<sub>n</sub> = rx<sub>(n-1)</sub>(1 - x<sub>(n-1)</sub>).
Write memoized pseudo-code that uses recursion, but also
uses a direct addressing to store results.
<br> <br> <br> <br> <br> <br> <br>
Remember to both store value <i>and</i> retrieve the value!
<br> <br> <br> <br> <br> <br> <br>
</ol>
<hr>
<h3>
Multiple Choice
</h3>
<ol>
<br>
<li>Compared to chaining, open addressing has the downside that:
<ol type="a">
<li>It is very slow.
<li>The hash table can fill up. *
<li>It can't resolve collisions.
<li>The hash table takes a huge amount of space.
</ol>
<br>
<li>We have one algorithm for processing customer records
with run time of O(n), and another with
run time of O(lg n) + 1000. In what circumstances might we want
to choose the O(n) algorithm?
<ol type="a">
<li>No circumstances.
<li>If our programmers are really bad.
<li>We believe our program will always be dealing with a
number of records less than one thousand. *
<li>If <em>n</em> is very large.
</ol>
<br>
<li>Under what circumstances might we most reasonably expect to
receive worst-case input to our binary search tree?
<ol type="a">
<li>We are loading the tree from an existing data store
which is sorted. *
<li>We insert data into the tree as it comes along to us.
<li>The data has been randomly shuffled.
<li>All of the above.
</ol>
<br>
<li>When we randomize an algorithm, we then speak of its
<ol type="a">
<li>necessary running time.
<li>best-case running time.
<li>expected running time. *
<li>unbounded running time.
</ol>
<br>
<li>The linearity of expectations means that, for two events X
and Y, the expectation that either event will occur equals
<ol type="a">
<li>the product of the expectation that X will occur
and the expectation that Y will occur
<li>the difference of the expectation that X will occur
and the expectation that Y will occur
<li>the square of the expectation that X will occur
and the expectation that Y will occur
<li>the sum of the expectation that X will occur and
the expectation that Y will occur *
</ol>
<br>
<li>The worst-case running time of a search on a binary search
tree is
<ol type="a">
<li>θ(n<sup>2</sup>)
<li>θ(n) *
<li>θ(lg n)
<li>θ(1)
</ol>
<br>
<li>If we have a binary search tree of height <em>h</em>, then
all searching functions such as min, max, and successor
will run in
<ol type="a">
<li>O(h) time. *
<li>O(h<sup>2</sup>) time.
<li>O(ln h) time.
<li>O(lg h) time.
</ol>
<br>
<li>According to the binary search tree property
<ol type="a">
<li>for all nodes higher in the tree than x,
x.key ≤ y.key.
<li>for all nodes in the right subtree of x,
x.key ≤ y.key. *
<li>for all nodes lower in the tree than x,
x.key ≤ y.key.
<li>all nodes in the right subtree of x will
be the successors of x.
</ol>
<br>
<li>The expected value of a real variable X is:
<ol type="a">
<li>is the weighted sum of all its values, weighted
according to the probability that they happen. *
<li>the single value that occurs most often.
<li>the value in the middle of its probability
distribution.
<li>all of the above, as they are equivalent.
</ol>
<br>
<li>Θ-notation applied to a function implies
it is
<ol type="a">
<li>a function we know little about.
<li>asymptotically bound from above and below. *
<li>asymptotically bound from below only.
<li>asymptotically bound from above only.
</ol>
<br>
<li>For large n, an algorithm will run the <em>slowest</em>
if it time complexity is:
<ol type="a">
<li>O(20n lg n)
<li>O(n!) *
<li>O(n<sup>3</sup>)
<li>O(2<sup>n</sup>)
</ol>
<br>
<li>An algorithm is most like:
<ol type="a">
<li>a carefully designed recipe. *
<li>a car engine.
<li>an organic molecule.
<li>a literary work.
</ol>
<br>
<li>O-notation applied to a function implies
<ol type="a">
<li>it is a function we know little about.
<li>it is asymptotically bound from above and below.
<li>only that it is asymptotically bound from below.
<li>only that it is asymptotically bound from above. *
</ol>
<br>
<li>For large n, an algorithm will run the <em>fastest</em>
if it time complexity is:
<ol type="a">
<li>O((1.1)<sup>n</sup>)
<li>O(n!)
<li>O(n<sup>2</sup>) *
<li>O(n<sup>3</sup>)
</ol>
<br>
<li>Besides running time, we can also measure algorithm performance
by:
<ol type="a">
<li>disk usage
<li>memory usage
<li>power consumed
<li>all of the above *
</ol>
<br>
<li>If f(n) = ω(g(n)), that means
<ol type="a">
<li>g dominates f asymptotically
<li>f is bounded below by g asymptotically
<li>f is bounded above by g asymptotically
<li>f dominates g asymptotically *
</ol>
<br>
<li>Which of these functions grows most <em>slowly</em>?
<ol type="a">
<li>lg n
<li>lg* n *
<li>ln n
<li>log<sub>10</sub> n
</ol>
<br>
<li>Ω-notation applied to a function implies
<ol type="a">
<li>it is a function we know little about.
<li>it is asymptotically bound from above and below.
<li>only that it is asymptotically bound from below. *
<li>only that it is asymptotically bound from above.
</ol>
<br>
<li>In algorithm analysis, we usually analyze algorithms
in terms of
<ol type="a">
<li>actual running time in nanoseconds.
<li>the number of disk operations.
<li>the number of basic operations. *
<li>CPU time used.
</ol>
<br>
<li>In algorithm analysis, we usually look at
<ol type="a">
<li>worst-case performance. *
<li>average-case performance.
<li>best-case performance.
<li>median-case performance.
</ol>
<br>
<li>The chief advantage of a doubly-linked list over a linked list is
<ol type="a">
<li>we can walk the list in either direction. *
<li>inserts are faster.
<li>deletes are faster.
<li>less memory is used.
</ol>
<br>
<li>A good use of direct dictionaries would be
<ol type="a">
<li>memoization of a numeric algorithm.
<li>coding the Sieve of Eratosthenes.
<li>marking zipcodes seen in a mailing application.
<li>all of the above. *
</ol>
<br>
<li>The worst case of hashing with chaining occurs when
<ol type="a">
<li>the input comes in sorted already.
<li>all inputs hash to different values.
<li>the input is purely random.
<li>all inputs hash to the same value. *
</ol>
<br>
<li>The "clustering" problem with open addressing with linear
probing means that
<ol type="a">
<li>"clusters" of keys will all hash to the same value.
<li>"clusters" of keys will build up in a linked list.
<li>the hash table clusters around its central value.
<li>once inputs start to cluster in one area of the
hash table, they will become more likely to do so. *
</ol>
<br>
<li>A random variable is actually
<ol type="a">
<li>the mean of all possible values.
<li>an algorithm.
<li>a precise real number value.
<li>a function. *
</ol>
</ol>
</body>
</html>