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
|
# 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.
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.
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)).
1. Exercise 3.1-1 from the textbook (5 marks)
1. Problem 3-1 from the textbook (10 marks)
1. Exercise 4.1-2 from the textbook (10 marks)
1. Exercise 4.2-1 from the textbook (5 marks)
1. Exercise 4.3-2 from the textbook (10 marks)
1. Exercise 4.4-7 from the textbook (10 marks)
1. Exercise 4.5-3 from the textbook (10 marks)
|
