首页
网站开发
桌面应用
管理软件
微信开发
App开发
嵌入式软件
工具软件
数据采集与分析
其他
首页
>
> 详细
辅导3121-21T2编程、讲解C/C++,Java程序设计 辅导R语言编程|调试Matlab程序
项目预算:
开发周期:
发布时间:
要求地区:
3121-21T2-HW1-SOLUTION
1. Question 1
You are given an array A of n distinct positive integers.
(1) Design an algorithm which decides in time O(n2 log n) (in the worst case) if there exist four
distinct pairs of integers {m, s} and {k, p} in A such that m2 + s = k + p2 (10 points)
(2) Solve the same problem but with an algorithm which runs in the expected time of O(n2).
(10 points)
Solution for Question 1(a):
(1) Square all numbers in A, storing in an array S.
(2) Find all combinations of sum ai + sj, i, j ∈ [0, n? 1], i 6= j storing in an array C with i, j.
(3) Sort C based on sum using merge sort, guarantee worst case O(nlogn).
(4) Loop through C and find two adjacent elements with the same sum and distinct is, js values,
and these 4 integers are the indexes of answers.
(5) Time complexity = O(n) +O(n2) +O(n2logn) = O(n2logn).
Solution for Question 1(b):
(1) Square all numbers in A, storing in an array S.
(2) Find all combinations of sum ai + sj, i, j ∈ [0, n ? 1], i 6= j storing in a hash table M ,
M [sum] = [(A[i], A[j]), ...].
(3) Loop through M and in each slot find if there is more than one pair of (A[i], A[j]) that
produces the same value of (A[i])2 + A[j].
(4) Time complexity = O(n) +O(n2) +O(n2) = O(n2).
2. Question 2
You are given a set of n fractions of the form xi/yi (1 ≤ i ≤ n), where xi and yi are positive inte-
gers. Unfortunately, all values yi are incorrect; they are all of the form yi = ci + E where numbers
ci ≥ 1 are the correct values and E is a positive integer (equal for all yi). Fortunately, you are also
given a number S which is equal to the correct sum S =
∑n
i=1 xi/ci. Design an algorithm which
finds all the correct values of fractions xi/ci and which runs in time O(n log min{yi : 1 ≤ i ≤ n}).
(20 points)
Solution for Question 2: In order to find all the correct values of the fractions, we need to find
the value of E that all denominators were increased by. Since for all i, yi > ci > 0 and E = yi ? ci
is positive, we know that
0 < E < min{yi : 1 ≤ i ≤ n}
Then, define
P (k) =
n∑
i=1
xi
yi ? k =
n∑
i=1
xi
ci + E ? k
which is strictly increasing for 0 < k < min{yi : 1 ≤ i ≤ n}, with P (k) = S precisely when k = E.
This means that we can binary search over this range using P (k) to find E in O(log min{yi : 1 ≤
1
2 3121-21T2-HW1-SOLUTION
i ≤ n}) steps. Each step involves evaluating P once, which takes O(n) time. As such, the overall
runtime of our algorithm is O(n log min{yi : 1 ≤ i ≤ n})
3. Question 3
You are given an array A consisting of n positive integers, not necessarily all distinct. You are
also given n pairs of integers (Li, Ui) and have to determine for all 1 ≤ i ≤ n the number of elements
of A which satisfy Li ≤ A[m] ≤ Ui by an algorithm which runs in time O(n log n). (20 points)
Solution for Question 3:
We first sort the array A in O(n log n) time using merge sort. For the ith query (Li, Ui), we do
binary search twice to find the index of:
(1) the first element with value less than Li; and
(2) the last element with value greater or equal to Ui.
The difference between these indices is the answer to the ith query.
We can do a binary search in O(log n) time. There are n queries and we need to do 2 × n binary
searches. Therefore, the total time complexity is O(n log n).
4. Question 4
You are given an array containing a sequence of 2n?1 consecutive positive integers starting with 1
except that one number was skipped; thus the sequence is of the form 1, 2, 3, . . . , k? 1, k+ 1, . . . , 2n.
You have to determine the missing term accessing at most O(n) many elements of A. (20 points)
Solution for Question 4:
Let’s denote the array as A. It can be inferred that:
(1) for all i = 1, 2, ..., k ? 1, we have A[i] = i.
(2) for all i = k, k + 1, ..., 2n ? 1, we have A[i] = i+ 1.
Clearly, if A[j] = j then also for all i < j we have A[i] = i and if A[j] > j then for all i > j we have
A[i] > i. Thus the task is to find the smallest index i such that A[i] > i and we can do this with a
binary search in O(log (2n ? 1)) = O(n) time.
5. Question 5
Read about the asymptotic notation in the review material and determine if f(n) = O(g(n)) or
g(n) = O(f(n) or both (i.e., f(n) = Θ(g(n))) or neither of the two, for the following pairs of functions
(1) f(n) = log2(n); g(n) =
10
软件开发、广告设计客服
QQ:99515681
邮箱:99515681@qq.com
工作时间:8:00-23:00
微信:codinghelp
热点项目
更多
代写 gr5280、代做 java/pytho...
2024-12-22
代写 data 编程、代做 python ...
2024-12-22
chc5049 代做、代写 sql 编程设...
2024-12-22
comp1038 代写、c++编程设计代...
2024-12-22
chc5028代做、代写c/c++设计编...
2024-12-21
代做program、代写sql程序设计
2024-12-21
itc228编程代写、代做java程序...
2024-12-21
代写comp 330 (fall 2024): as...
2024-12-21
代写busi2105 quantitative me...
2024-12-21
代做7ssgn110 environmental d...
2024-12-21
代做busi2105 quantitative me...
2024-12-21
代写csc 110 y1f fall 2024 qu...
2024-12-21
代做management accounting au...
2024-12-21
热点标签
mktg2509
csci 2600
38170
lng302
csse3010
phas3226
77938
arch1162
engn4536/engn6536
acx5903
comp151101
phl245
cse12
comp9312
stat3016/6016
phas0038
comp2140
6qqmb312
xjco3011
rest0005
ematm0051
5qqmn219
lubs5062m
eee8155
cege0100
eap033
artd1109
mat246
etc3430
ecmm462
mis102
inft6800
ddes9903
comp6521
comp9517
comp3331/9331
comp4337
comp6008
comp9414
bu.231.790.81
man00150m
csb352h
math1041
eengm4100
isys1002
08
6057cem
mktg3504
mthm036
mtrx1701
mth3241
eeee3086
cmp-7038b
cmp-7000a
ints4010
econ2151
infs5710
fins5516
fin3309
fins5510
gsoe9340
math2007
math2036
soee5010
mark3088
infs3605
elec9714
comp2271
ma214
comp2211
infs3604
600426
sit254
acct3091
bbt405
msin0116
com107/com113
mark5826
sit120
comp9021
eco2101
eeen40700
cs253
ece3114
ecmm447
chns3000
math377
itd102
comp9444
comp(2041|9044)
econ0060
econ7230
mgt001371
ecs-323
cs6250
mgdi60012
mdia2012
comm221001
comm5000
ma1008
engl642
econ241
com333
math367
mis201
nbs-7041x
meek16104
econ2003
comm1190
mbas902
comp-1027
dpst1091
comp7315
eppd1033
m06
ee3025
msci231
bb113/bbs1063
fc709
comp3425
comp9417
econ42915
cb9101
math1102e
chme0017
fc307
mkt60104
5522usst
litr1-uc6201.200
ee1102
cosc2803
math39512
omp9727
int2067/int5051
bsb151
mgt253
fc021
babs2202
mis2002s
phya21
18-213
cege0012
mdia1002
math38032
mech5125
07
cisc102
mgx3110
cs240
11175
fin3020s
eco3420
ictten622
comp9727
cpt111
de114102d
mgm320h5s
bafi1019
math21112
efim20036
mn-3503
fins5568
110.807
bcpm000028
info6030
bma0092
bcpm0054
math20212
ce335
cs365
cenv6141
ftec5580
math2010
ec3450
comm1170
ecmt1010
csci-ua.0480-003
econ12-200
ib3960
ectb60h3f
cs247—assignment
tk3163
ics3u
ib3j80
comp20008
comp9334
eppd1063
acct2343
cct109
isys1055/3412
math350-real
math2014
eec180
stat141b
econ2101
msinm014/msing014/msing014b
fit2004
comp643
bu1002
cm2030
联系我们
- QQ: 9951568
© 2021
www.rj363.com
软件定制开发网!