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
|
# Problem Set 1
* Weight: 10% of your final grade
* Due: after Unit 2
Save your answers to the exercises in Microsoft Word, plain text, or PDF files.
When you complete all the exercises of an assignment, zip them into a single file and submit it here.
Submit your solutions to the following exercises and problems:
1. Exercise 1.1-4
* How are the shortest path and traveling-salesman problems given above similar?
* How are they different?
The shortest path problem is looking for an efficient solution that routes
from point A to point B. The traveling-salesman problem is similar except
that the sales person needs to visit multiple locations then return to the
starting point in the most efficient way. These problems are similar because
the shortest path from point A to B can be used to help determine a good
enough solution for the traveling-salesman problem.
Both of these problems are considered an NP-complete problems because it
hasn't been proven if an efficient algorithm can or cannot exist.
1. Exercise 1.2-2 from the textbook (5 marks)
* Suppose we are comparing implementations of insertion sort and merge sort on
the same machine. For inputs of size n, insertion sort runs in 8n^2 steps,
while merge sort runs in 64nlg(n) steps. For which values of n does
insertion sort beat merge sort?
The following program produces a result of '44'.
```golang
func main() {
fmt.Println("n,isort,msort")
for n := 2.0; n < 1000.0; n++ {
isort := 8 * math.Pow(n, 2)
msort := 64 * (n * math.Log2(n))
fmt.Printf("%v,%v,%v\n", n, isort, msort)
if isort > msort {
break
}
}
}
```
``csv
n,isort,msort
2,32,128
3,72,304.312800138462
4,128,512
5,200,743.0169903639559
6,288,992.6256002769239
7,392,1257.6950050818066
8,512,1536
9,648,1825.876800830772
10,800,2126.033980727912
11,968,2435.439859520657
12,1152,2753.251200553848
13,1352,3078.7658454933885
14,1568,3411.390010163613
15,1800,3750.614971784178
16,2048,4096
17,2312,4447.159571280369
18,2592,4803.753601661543
19,2888,5165.4798563474
20,3200,5532.067961455824
21,3528,5903.274616214654
22,3872,6278.879719041314
23,4232,6658.683199315923
24,4608,7042.502401107696
25,5000,7430.169903639559
26,5408,7821.531690986777
27,5832,8216.445603738473
28,6272,8614.780020327225
29,6728,9016.412726956773
30,7200,9421.229943568356
31,7688,9829.12547980756
32,8192,10240
33,8712,10653.760380085054
34,9248,11070.319142560738
35,9800,11489.593957956724
36,10368,11911.507203323086
37,10952,12335.985569809354
38,11552,12762.9597126948
39,12168,13192.363938280172
40,12800,13624.135922911648
41,13448,14058.216460117852
42,14112,14494.549232429308
43,14792,14933.080604940173
44,15488,15373.759438082629
```
1. Exercise 2.1-3 from the textbook. (10 marks)
Consider the searching problem:
Input: A sequence of n numbers A = {a1, a2, ...., an} and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not
appear in A.
Write pseudocode for linear search, which scans through the sequence,
looking for v. Using a loop invariant, prove that your algorithm is correct.
Make sure that your loop invariant fulfills the three necessary properties.
```plaintext
i = 0
for i < A.length and v != A[i]
i = i + 1
if i >= A.length
return NIL
return i
```
* initialization: initialize `i` to first index of first element
* maintenance: continue looping if `i` is less than size of `A` and `A[i]` is
not equal to the target value `v`.
* termination: terminate loop when the key matches the target value.
1. Exercise 2.2-3 from the textbook (10 marks)
Consider linear search again (see Exercise 2.1-3). How many elements of the
input sequence need to be checked on the average assuming that the element
being searched for is equally likely to be any element in the array? How
about in the worst case? What are the average-case and worst-case running
times of linear search in O-notation? Justify your answers.
How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array?
Since there are `n` elements the average would be in the middle (.i.e. `𝚯(n/2)`).
When we drop the lower order terms this becomes `𝚯(n)`. Hence, the term
linear search.
How about in the worst case?
In the worst case you need to search check every element in the input.
Because of this the worst case would be equal to the size of the input.
i.e. `𝚯(n)`.
What are the average-case and worst-case running times of linear search in 𝚯-notation?
When we drop lower order terms, like constants then they are both `𝚯(n)`
1. Exercise 2.3-5 from the textbook (10 marks)
Referring back to the searching problem (see Exercise 2.1-3), observe that
if the sequence A is sorted, we can check the midpoint of the sequence
against v and eliminate half of the sequence from further consideration. The
binary search algorithm repeats this procedure, halving the size of the
remaining portion of the sequence each time. Write pseudocode, either
iterative or recursive, for binary search. Argue that the worst case running
time of binary search is O(lg(n)).
`BINARY-SEARCH(A, t, s, e)` where `A` is an array and `s`, and `r` are indices into the array such that `s < e` and `t` is the target value to find.
```plaintext
BINARY-SEARCH(A, t, s, e)
length = e - s
if length == 1
item = A[s]
else
mid = (length / 2) + s
item = A[mid]
if item == t
return mid
if item < t
return BINARY-SEARCH(A, t, s, mid-1)
else
return BINARY-SEARCH(A, t, mid+1, e)
```
1. Exercise 3.1-1 from the textbook (5 marks)
Let `f(n)` and `g(n)` be asymptotically nonnegative functions.
Using the basic definition of theta-notation,
prove that `max(f(n), g(n))` = `theta(f(n) + g(n))`.
```plaintext
max(f(n), g(n))
```
1. Problem 3-1 from the textbook (10 marks)
Asymptotic behaviour of polynomials
Let
```
d
p(n) = Σ ai n^i
i=0
```
where `ad > 0`, be a degree-d polynomial in `n`, and let `k` be a constant.
Use the definitions of the asymptotic notations to prove the following
properties.
a. If `k >= d`, then `p(n) = O(n^k)`.
b. If `k <= d`, then `p(n)` = `omega(n^k)`.
c. If `k = d`, then `p(n) = theta(n^k)`.
d. If `k > d`, then `p(n) = o(n^k)`.
e. If `k < d`, then `p(n) = w(n^k)`.
1. Exercise 4.1-2 from the textbook (10 marks)
What does `FIND-MAXIMUM-SUBARRAY` return when all elements of `A` are negative?
1. Exercise 4.2-1 from the textbook (5 marks)
Use Strassen's algorithm to compute the matrix product
```plaintext
|1 3||6 8|
|7 5||4 2|
```
Show your work.
1. Exercise 4.3-2 from the textbook (10 marks)
Show that the solution of `T(n) = T([n/2]) + 1` is `O(lg n)`
1. Exercise 4.4-7 from the textbook (10 marks)
Draw the recursion tree for `T(n) = 4T([n/2]) + cn`, where `c` is a constant,
and provide a tight asymptotic bound on its solution. Verify your bound by the
substitution method.
1. Exercise 4.5-3 from the textbook (10 marks)
Use the master method to show that the solution to the binary-search
recurrence `T(n) = T(n/2) + theta(1)` is `T(n) = theta(lg n)`. (See Exercise
2.3-5 for a description of binary search.)
|
