-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHW4.html
More file actions
233 lines (207 loc) · 9.81 KB
/
HW4.html
File metadata and controls
233 lines (207 loc) · 9.81 KB
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
<!DOCTYPE html PUBLIC "-//w3c//dtd html 4.0 transitional//en">
<!-- saved from url=(0076)https://reed.cs.depaul.edu/lperkovic/courses/csc421/homeworks/Homework4.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<meta name="GENERATOR" content="Mozilla/4.76 [en] (X11; U; Linux
2.2.17-14 i686) [Netscape]">
<title>Algorithms</title>
<!--<base target="_top">--><base href="." target="_top">
</head>
<body bgcolor="#ffffff">
<div align="Center">
<h2> Homework 4 </h2>
<h3> Due by 4:30pm on October 7, 2020</h3>
</div>
<center>
<h3>
<hr></h3>
</center>
<h3>Viewings and Readings</h3>
<i> [Links to the slides, recordings, and quiz are on the </i><i><a href="https://reed.cs.depaul.edu/lperkovic/courses/csc421/">course
web site</a></i><i>.]</i><br>
Review the week 4 lecture slides.<br>
View the week 4 lecture recordings and the discussion session
recording.<br>
Complete the week 4 quiz.<br>
Read sections 2.5-8 of the textbook.
<h3>Problems</h3>
Please write precise and concise answers. Except where explicitly
indicated, your algorithm descriptions should use either clear,
concise, and precise plain English or clear, concise, and precise
pseudo-code that uses a style similar to the pseudo-code in your
textbook. Submit your solutions to problems <b>1-5</b> via <a href="https://d2l.depaul.edu/">D2L</a> as a Word or PDF file or as
scans/photos of legible handwritten notes. Submit your solution to
problem <b>6</b> via <a href="https://depaul.kattis.com/courses/CSC421/Fall2020">Kattis</a>.<br>
<br>
<br>
<b>1.</b> Problem 14(a) page 51 in your textbook.<br>
<div> Suppose you are given two sets of n points, one set {p1
, p2
, . . . , pn
} on the
line y = 0 and the other set {q1
, q2
, . . . , qn
} on the line y = 1. Create a set
of n line segments by connect each point p<sub>i</sub>
to the corresponding point q<sub>i</sub>
.
Describe and analyze a divide-and-conquer algorithm to determine how
many pairs of these line segments intersect, in O(n log n) time. [Hint:
See the previous problem.
</div>
<br>
<pre>
Two lines will intercect in two scenarios
Either p[i] > p[j] AND q[i] < q[j]
OR
p[i] < p[j] AND q[i] > q[j]
We can solve this by with two merge sorts with some extra functionality
We do the classic mergesort on set p.
Recurseively dividing p in half and using the left and right halfs as input in recusrion
Base case is when there is only one element left in the array
Merge the left and right together by going through left and right and adding them to new array sorted
Any sorting done When the left index > right index we need to make sure the same index changes on set Q
This Recurseively runs until p is completely sorted and q also has the same changes
We can then run the merge sort again on q with one difference
Whenever left > right we add one to a counter
Since p is sorted, any sorting that happens in q means theres an intercect based on the scenarios we layed out earlier
We return that count at the end of the sort and thats the number of intersections
</pre>
<br>
<b>2.</b> Problems 24(a)(b)(c) page 57 in your
textbook.<br>
<div>
Consider the following classical recursive algorithm for computing the
factorial n! of a non-negative integer n:
<pre>
Factorial(n):
if n = 0
return 1
else
return n * Factorial(n - 1)
</pre>
<div>(a) How many multiplications does this algorithm perform?</div>
<br>
<div>n multiplications are performed</div>
<br>
<div>(b) How many bits are required to write n! in binary? Express your answer
in the form Θ(f (n)), for some familiar function f (n). [Hint: (n/2)<sup>n/2</sup> < n! < n<sup>n</sup>.]
</div>
<br>
<br>
<div>
(c) Your answer to (b) should convince you that the number of multiplications
is not a good estimate of the actual running time of Factorial. We
can multiply any k-digit number and any l-digit number in O(k * l) time
using either the lattice algorithm or duplation and mediation. What is
the running time of Factorial if we use this multiplication algorithm as
a subroutine?
</div>
<br>
<div>
O(n)
</div>
</div>
<br>
<b>3.</b> Problem 2(a) page 94 in your textbook.
Do this by appropriately modifying the pseudo-code on page 84 of the
textbook.<br>
<div>
Describe recursive algorithms for the following variants of the text segmentation problem. Assume that you have a subroutine IsWord that takes an
array of characters as input and returns True if and only if that string is a
"word".
</div>
<div>
(a) Given an array A[1 .. n] of characters, compute the number of partitions
of A into words. For example, given the string ARTISTOIL, your algorithm
should return 2, for the partitions ARTIST-OIL and ART-IS-TOIL.
</div>
<pre>
{{Is the suffix A[i .. n] Splittable?}}
// set global var sum to keep track of all valid answers
sum = 0
Splittable(i):
if i > n
return true
for j = i to n
if IsWord(i, j)
if Splittable(j + 1)
sum = sum + 1
return False
</pre>
<br>
<b>4.</b> Problem 4(a) page 94 in your textbook.
You may answer this question with a recursive formula or an
algorithm described using pseudo-code. Hint: compare <tt>A[1]</tt>
and <tt>B[1]</tt>, consider the two cases <tt>A[1]==B[1]</tt> and
<tt>A[1] != B[1]</tt>, and write/compute the <tt>LCS(A[1..n],
B[1..n])</tt> in terms of <tt>LCS(A[2..n],B[2..n])</tt>, <tt>LCS(A[1..n],B[2..n])</tt>,
and <tt>LCS(A[2..n], B[1..n])</tt>.<br><br>
<div>
(a) Let A[1 .. m] and B[1 .. n] be two arbitrary arrays. A common subsequence
of A and B is both a subsequence of A and a subsequence of B. Give
a simple recursive definition for the function lcs(A, B), which gives the
length of the longest common subsequence of A and B.
</div>
<br>
<pre>
Basically recursively check if the first index of each matches
If they do move on to the next character for both
If not remove the first index of the longer one and recurse until one array is empty
lcs(A[i .. n], B[j .. n]):
if length A == 0 OR length B == 0
return 0
if A[1] == B[1] {
return lcs(A[i + 1 .. n], B[j + 1 .. n]) + 1
} else {
if length A > length B {
return lcs(A[i + 1 .. n], B[j .. n])
} else {
return lcs(A[i .. n], B[j + 1 .. n])
}
}
</pre>
<p><b><b><br>
[One, but not both, of problems 5. and 6. is optional]<br>
</b></b></p>
<p><b><b></b>5.</b> Problem 6(a) page 96.<br><br>
<div>
This problem asks you to design backtracking algorithms to find the cost of
an optimal binary search tree that satisfies additional balance constraints.
Your input consists of a sorted array A[1 .. n] of search keys and an array
f [1 .. n] of frequency counts, where f [i] is the number of searches for A[i].
This is exactly the same cost function as described in Section 2.8. But
now your task is to compute an optimal tree that satisfies some additional
constraints.
</div>
<br>
<div>
(a) AVL trees were the earliest self-balancing balanced binary search trees,
first described in 1962 by Georgy Adelson-Velsky and Evgenii Landis. An
AVL tree is a binary search tree where for every node v, the height of
the left subtree of v and the height of the right subtree of v differ by at
most one.
Describe a recursive backtracking algorithm to construct an optimal
AVL tree for a given set of search keys and frequencies.
</div>
<br>
<pre>
We can use the formula from lecture that calculates total cost recursively for each specific node chosen to be the root
Cost(T, f [1..n]) =SUM(i=1 -> n for f[i]) + Cost(LEFT SUBTREE(T), f [1..r - 1]) + Cost(RIGHT SUBTREE(T), f [r + 1])
To do a normal cost optimization of a tree we
We pass in as input the tree, height of current node, and A
For each A[i] we insert A[i] into the tree
We recursively cut A in half and run and sum the cost functions on the left and right half of the array so the new A[] will be either the left or right half in the next recursive call
We save this sum in a minValue var and change whats saved if any other node being the root creates a more optimal cost
After the sums return we can also check here whether the tree is AVL, if the height of the left subtree - height of right subtree is > 1 or < -1 then the tree is imbalanced and we can prune this result
We keep cutting the array in half until the base case on one element in the array in which case the forumla above would equal Cost(T, f [1..n]) =SUM(i=1 -> n for f[i]) + <s>Cost(LEFT SUBTREE(T), f [1..r - 1]) + Cost(RIGHT SUBTREE(T), f [r + 1])</s>, so return f[i]
</pre>
</p>
<p><b> 6. </b>
Week 4 problem <i>boggle</i> on <a href="https://depaul.kattis.com/courses/CSC421/Fall2020">Kattis</a>.
Submit your solution via <a href="https://depaul.kattis.com/courses/CSC421/Fall2020">Kattis</a>.<br>
</p>
<p><br>
</p>
<br>
<div id="fpCE_version" style="display:none">8.5.0</div></body></html>