School of Computing and Information Systems
Network | network | Algorithm | app代做 – 这个题目属于一个Algorithm的代写exam, 是比较典型的Network/network/Algorithm/app等代写方向
COMP20007 Design of Algorithms
Semester 1, 2022
Sample Mid Semester Test
Instructions to Students
- The total time to read, complete, scan and upload your solutions to this test is 1 hour. You have to allow at least 15 minutes to scan and upload your solutions.
- You must submit your solutions by 11:00 AM AEST.
- Late submissions will be subject to a 10% penalty per 5 minutes late and submissions after 11: AM AEST will not be marked.
- This test contains 4 questions which will be marked out of 10 marks.
- The test is open book, which means you may only use course materials provided via the LMS or the text book but must not use any other resource including the Internet.
- You must not communicate with other students or make use of the Internet.
- Solutions must be written on separate pieces of paper with pen or pencil. You must write your solution to each question on a new sheet of paper and clearly indicate which question you are answering on each page.
- You must not use a tablet to complete this test.
- You must also indicate which question is answered on which page via Gradescope.
- You must use a Scanner app on your smartphone to scan your solutions, email them to your laptop and then submit a PDF file to Gradescope via Canvas.
- A Gradescope guide to scanning your test can be found here:https://gradescope-static-assets. s3-us-west-2.amazonaws.com/help/submitting_hw_guide.pdf
- The Dropbox and Microsoft OneDrive mobile apps also have scanning capabilities.
Question 1 [2 Marks]
We know, from lectures, the following facts. For 0<< 1 <c,
1 lognnncnlogncnnn,
wheref(n)g(n)means bothf(n)O(g(n))andg(n)6O(f(n))(i.e.g(n)is not inO(f(n))).
For the following pairs of functions,f(n),g(n), determine if f(n)(g(n)),f(n)O(g(n)), orf(n) (g(n)), making the strongest statement possible. That is, if both f(n)O(g(n))andf(n)(g(n)) are true, youmustanswer with the formf(n)(g(n)). You must answer with f(n)on the left and g(n)on the right, for example, you may not answerg(n)O(f(n)).
Youmustshowallworking. A correct answer that does not show your working will result in 0 marks.
(a) f(n) = (n+ 1 )^3 , g(n) = ( 2 n)^3
(b) f(n) = 3 n+^1 , g(n) = ( 3 + 1 )n
(c) f(n) =n^3 + 1. 1 n, g(n) = (n^3 )^2 + 1. 1 n
(d) f(n) =log(nn), g(n) =
n
Question 2 [2 Marks]
A string of characters is called a palindrome if reading the characters from left to right gives the same sequence as reading the characters from right to left.
For example:abccba,ahgiighaandabgllggllgbaare all palindromes whileabcdabcd,lghddgland abcdare not.
Write the pseudocode for an Algorithm which, given a string and its lengthn, can identify a palindrome using only one scan from left to right(which means you can only access each letter once). Your algorithmmust employ the use of either a queue or a stack, and youmust justify your choice.
If you use a stack myou must use PUSH() and POP(), and if you use a queue you must use ENQUEUE() and DEQUEUE().
Assume for simplicity every input will be of even length.
Question 3 [3 Marks]
The following graph represents a road network where each edge presents a road segment. The costs of the road segments are given in the figure below. There are three hospitals at nodes B, D, and E, and an accident occurs at node H.
A
B
C
D
E
F
G
8 H
2
5
2
1
2
5
1
6
3
1
2
3
6
(a) Which algorithm would you use to find the nearest hospital from the accident. Explain how and
why you would use this algorithm.
(b) Which is the nearest hospital, which path would you take and what is the cost of this path? You
must show the execution of the algorithm described above.
(c) List the order of the nodes visited from H in the graph when a breadth-first search is used.
You should break ties in alphabetic order.
Question 4 [3 marks]
Consider the following recursive function, which takes an unordered array of integers,A, and an integer, k, and returns TRUE ifkappears inAand FALSE otherwise.
functionTHIRDSSEARCH(A[0..n-1], k)
ifn== 0 then
returnFALSE
else ifn== 1 then
return(A[ 0 ] ==k)
else
aTHIRDSSEARCH(A[ 0 ..n/ 3 1 ],k)
bTHIRDSSEARCH(A[n/ 3 ..n 2 / 3 1 ],k)
cTHIRDSSEARCH(A[n 2 / 3 ..n 1 ],k)
return(aORbORc)
For simplicity, you may assume the input array is of lengthn= 3 mfor some positive integerm, so that each recursive call gets an exact third of the input array.
(a) Write down, andsolve, a recursive formulaW(n) =...which describes the number of steps taken
by THIRDSSEARCHon an array of lengthn, for the worst case input. Make sure you include the
base case(s). Keep in mind that the basic operation is usually the most frequent or most expensive
operation. Remember the formula for the geometric series states that
k
i= 0
xi=
xk 1
x 1
.
(b) Use the language of,O,to bound the time complexity of THIRDSSEARCH, usingT(n)for its
runtime. You must include an upperandlower bound. Full marks are awarded only to the tightest
possible bounds.
(c) Explain how THIRDSSEARCHcould be slightly modified to improve its efficiency in the best case,
and repeat the analysis from part (b), with justification.