首页 > > 详细

代写COMP3001代写Java程序、C/C++语言代写

End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
Examination Cover Sheet 
 
 
School of Electrical Engineering, Computing and Mathematical Sciences 
 
Discipline of Computing - Curtin University 
 
COMP3001 Design and Analysis of Algorithms 
 
Final Assessment - Semester 1/2020 
 
 
Total Mark: 100 
 
Time allowed: 4 hours (start to finish) 
 
Assessment Availability: 1pm Monday 15 June 2020 to 1pm Tuesday 16 June 2020 
 
Test mode: Online test, open-book: you are allowed to access your hand-written notes, 
lecture slides, textbooks, and printed and electronic materials in your possession. 
 
CONDITIONS 
• The test must be completed by yourself only. No one else should do this test for 
you. Any attempts to compromise the system are strictly prohibited. Any breaches of 
this policy will be considered cheating and appropriate action will be taken as per 
University policy. 
• You are prohibited from communicating with people other than the unit 
coordinator/lecturer and the tutors during the test. 
• You are prohibited from providing information about your work and your test to 
others during and outside your test within two days. Some students may sit in the test 
after you. 
• You must complete and submit the "Student Declaration Form". 
• Some students sitting the test will be invited to an online interview. In the interview, 
students will be asked to explain their solutions and demonstrate their knowledge for 
randomly selected questions. Students will be shown the questions, as well as their 
written answers. 
 
INSTRUCTION 
 
• This assessment consists of four questions: QUESTION ONE to QUESTION FOUR 
of different types, with a total of 100 marks. Attempt ALL questions. 
• You can submit your answers multiple times during the assessment, but only the last 
submission would be used for marking. 
• You are allowed to use (i) n^2 for n2 and n_2 for n2, (ii) floor(x) for ⎣x⎦ and ceiling(x) 
for ⎡x⎤, (iii) Big Theta(n) for Θ(n) and Big Omega (n) for Ω(n), (iv) lg x for log2x, log 
x for log10x, and log_b(a) for logba, (v) >= for ≥, <= for ≤, and != for ≠. 
 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 1 of 6 
QUESTION ONE (Total: 25 marks). 
 
Q1 a) (5 marks). Consider the following algorithm to print out all the keys in a binary 
search tree in an inorder tree walk. 
 
INORDER-TREE-WALK (x) 
if x ≠ NIL then 
INORDER-TREE-WALK (left[x]) 
Print key[x] 
INORDER-TREE-WALK (right[x]) 
 
The recurrence of the running time complexity of the algorithm is T(n) = T(k) + T(n-k-1) + 1, 
where k is the number of nodes in the left subtree and n-k is the number of nodes in the right 
subtree. 
 
Use induction to prove that the recurrence is O(n). 
 
 
Q1 b) (Total: 10 marks). It is known that no comparison-based sorting algorithm has a 
running time complexity less than Ω(n lg n). 
 
(i) (5 marks). Suppose that your friend A claims to have a comparison-based sorting 
algorithm that satisfies a recurrence T(n) = 3T(n/4) + cn. Is your friend’s claim 
reasonable? Justify your answer. 
 
(ii) (5 marks). Suppose that your friend B claims to have a comparison-based sorting 
algorithm that satisfies a recurrence T(n) = 5T(n/4) + cn. Would you use your friend’s 
algorithm over merge sort for large n? Justify your answer. 
 
Hint: Solve the recurrence functions in (i) and (ii) to justify your answers. You don’t need to 
check for the regularity condition in your solution. 
 
 
Q1 c) (4 marks). Without using Stirling’s formula, prove that log(n!) is O(n log n). You need 
to give the values of n0 and c. 
 
Hint: log (a * b) = log a + log b. 
n! = n * (n-1) * (n-2) * … * 2 * 1. 
 
 
 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 2 of 6 
Q1 d) (Total: 6 marks). 
 
for (i ! 0 to n) do 
for (j ! 0 to n) do 
if (A[i] = B [j]) then 
return (TRUE) 
 
(i) (2 marks). What does the algorithm do? 
 
(ii) (2 marks). What is the best case upper bound running time complexity of the algorithm? 
Justify your answer. 
 
(iii) (2 marks). What is the worst case upper bound running time complexity of the 
algorithm? Justify your answer. 
 
 
END OF QUESTION ONE 
 
 
 
 
 
 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 3 of 6 
QUESTION TWO (Total: 26 marks). 
 
Q2 a) (Total: 10 marks). Suppose you were to run a marathon from a point A to another 
point B along a given route. In the marathon, you were allowed to stop and get water as many 
times as needed. However, since each stop takes time, you want to minimize the total number 
of stops as possible. Assume you know that you can run for up to k km after every stop. 
Further, you were given information about the locations and distances between water stations 
along the route. Let S = (s1, s2, …, sn) be the set of n water stations along the route, and D = 
(d1, d2, …, dn) be the set of their corresponding distances from point A to the station. In 
other words, si is the water station with distance di from point A. Note that d1 < d2 < … < dn, 
and assume the distance between neighbouring stations is at most k kms, and the distance 
between the last station and point B is k km. For example, consider for k = 15 kms and D = 
(5, 10, 13, 16, 20, 24, 27, 31, 36, 40, 45, 50). The optimal sequence of stops is (s3, s7, s10, 
s12), i.e., 4 stops. 
 
(i) (6 marks). Write the pseudo code of your algorithm to determine a set of water stations 
si that minimizes the total number of stops. 
 
(ii) (2 marks). Explain the idea of your algorithm, and use the given example for k=12 km 
to illustrate the working of your algorithm. 
 
(iii) (2 marks). Analyse the time complexity of your algorithm as a function of n, where n is 
the total number of water stations along the route fro A to B. Also, argue why your 
algorithm is the most efficient possible. 
 
Q2 b) (Total: 8 marks). Consider d sequences of elements. The elements in each sequence 
are already sorted in increasing order, and there are in total n elements. Design an O(n lg d) 
algorithm to merge all the sequences into one sorted sequence (in increasing order). As an 
example, for four sequences: (2, 5, 7), (4, 6), (1, 8), and (3, 8, 9), we have d = 4 and n = 10. 
Your algorithm should produce a sorted sequence (1, 2, 3, 4, 5, 6, 7, 8, 8, 9). 
 
(i) (6 marks). Describe your algorithm. Show that the time complexity of your algorithm is 
O(n lg d). You can assume d is in a power of 2, e.g., 4, 8, 16. You are NOT required to 
write the pseudocode of your algorithm. 
 
(ii) (2 marks). Show how your algorithm merges the d=4 sequences in the example. 
 
 
Q2 c) (8 marks). Consider an array of records, A, whose keys to be sorted only consist of F’s 
and M’s, for Female and Male respectively. For example, array A may contain the a list of 
keys A=(F M M M F F F M F M F M M F F M). 
 
• Write the pseudo code of a O(n) algorithm to sort the array in place, i.e., using memory 
storage of no more than constant size in addition to that of the array. 
• Illustrate the working of your algorithm using the example as its input. 
• Analyse the time complexity of the algorithm and show that its complexity is O(n). 
 
 
END OF QUESTION TWO 
 
 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 4 of 6 
QUESTION THREE (Total: 17 marks). 
 
Q3 a) (Total: 6 marks). 
 
(i) (3 marks). Working modulo 11, list all spurious hits that the Rabin-Karp matcher 
encounters in the text T = 3142531653586797 when looking for pattern P = 53. 
 
(ii) (3 marks). Given t3 = 3 for T = 3142531653586797, show in detail how Rabin-Karp 
matcher computes t4. 
 
 
Q3 b) (2 marks). Consider the following BF_String_Matcher (T, P) algorithm (from Lecture 
Slide). 
 
BF_String_Matcher(T, P) 
1 n = length [T] 
2 m = length[P] 
3 for s = 0 to n - m 
4 do if P[1..m] = T[s+1..s+m] 
5 then shift s is valid 
 
For T = and P = , the algorithm requires 
 
A. 3 comparisons between characters in T and P. 
B. 14 comparisons between characters in T and P. 
C. 24 comparisons between characters in T and P. 
D. 21 comparisons between characters in T and P. 
E. None of the answers are correct. 
 
 
Q3 c) (Total: 9 marks). Data compression. 
 
A file has alphabets {A, B, C, D, E}, where A has frequency 32, B has frequency 64, C has 
frequency 8, D has frequency 16, and E has frequency 8. 
 
(i) (3 marks). Give the Huffman code for each of the alphabets. 
 
(ii) (3 marks). How many bits are needed to represent the alphabets in the file? Explain 
your answer. 
 
(iii) (3 marks). Use the Shannon’s entropy to show that the computed Huffman code is 
optimal. Give the details of you computation. 
 
 
END OF QUESTION THREE 
 
 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 5 of 6 
QUESTION FOUR (Total: 32 marks). 
 
Q4 a) (4 marks). Explain if the following statement is True or False. Your explanation must 
include detailed computation of the number of scalar multiplications of the two alternative 
full parenthesizations. 
 
Consider the matrix chain multiplication problem with p0=1000, p1=100, p2=20, p3=10, and 
p4=1000. A full parenthesization (((A1A2)A3)A4) requires more scalar multiplications than 
another full parenthesization ((A1(A2A3))A4). 
 
 
Q4 b) (Total: 10 marks). Consider the following incomplete tables generated by the 
dynamic programming algorithm (discussed in the lecture) for solving the matrix chain 
problem, where the four consecutive matrices are A, B, C, and D. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
(i) (2 marks). If matrices A and D have dimensions A = 6×4, and D = 3×2, what are 
the dimensions of matrices B and C? Explain your answer. 
 
(ii) (6 marks). Calculate m[1, 4] and s[1, 4]. Show your detailed calculations. 
 
(iii) (2 marks). Show the optimal bracketing of the matrices in part (i) that produces 
the number of multiplications in m[1, 4]. 
 
 
 
 
 
 
 
 
 
 
 
 
0 ? 42 18 4 
108 36 0 3 
72 0 2 
0 1 
1 2 3 4 m 
? 2 3 4 
1 2 3 
1 2 
1 2 3 4 s 
End of Semester 1, 2020 
COMP3001 Design and Analysis of Algorithms 
 
 
Page 6 of 6 
Q4 c) (Total: 8 marks). Consider 5 items with weights w = (2, 6, 2, 4, 5) and values v = 
(40, 40, 25, 30, 50). For example, the weight of item 1 is 2 and its value is 40, while item 5 
has a weight of 5 and a value of 50. 
 
(i) (6 marks). Use the 0/1 Knapsack dynamic programming algorithm (discussed in the 
lecture) to fill out the following Table P, assuming the total weight of the selected items 
is at most 9 units. In your answer, you can represent the entry at row i and column k in 
Table P as P[i, k]. For example, P[5, 9] = x and P[3, 7] = y. 
 
i / k 0 1 2 3 4 5 6 7 8 9 
5 x 
3 y 
 
(ii) (2 marks). Use Table P to determine what items should be selected to achieve maximum 
values. Explain your answer 
 
 
Q4 d) (Total: 10 marks). Consider the following parallel search algorithm that requires 
CRCW model. 
 
Algorithm Parallel_Search (x, A[1 .. n]) 
 
index ! -1 
forall Pi do in parallel 
if A[i] = x then 
index ! i 
endif 
endfor 
 
(i) (4 marks). Modify the algorithm to find each index in array A that stores x. Use array B 
to store the indices. Hint. B[i] = -1 means A[i] ≠ x. 
 
(ii) (2 marks). Is the modified algorithm cost optimal? Justify your answer. 
 
(iii) (2 marks). Compute the speedup of the modified algorithm. 
 
(iv) (2 marks). Does the modified algorithm also require CRCW model? Explain your 
answer. 
 
 
END OF EXAMINATION 

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp2

联系我们 - QQ: 99515681 微信:codinghelp2
© 2014 www.7daixie.com
程序代写网!