算法代写|COSC 2123/1285 Assignment 2: Algorithm Design & Complexity Analysis 2022

这是一篇来自澳洲的关于算法设计和复杂性分析的算法代写

 

1 Part I: Fundamental

Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists of an array A of n integers, two nonnegative integers ` ,u satisfying 0 ` u n1, and an integer k. We assume that n is a power of 2.

Algorithm mystery(A[0,…,(n1)],` ,u,k)

if ` == u then

if A[` ] == k then

return 1;

else

return 0;

end if

else

m = b(` + u 1)/2c ;

return mystery(A,` ,m,k)+mystery(A,m+1,u,k);

end if

a) [2 marks] What does mystery(A[0..(n 1)],0,n 1,k) compute (0.5 mark)? Justify your answer (1.5 marks).

b) [1 mark] What is the algorithmic paradigm that the algorithm belongs to?

c) [2 marks] Write the recurrence relation for C(n), the number of additions required by mystery(A,0,n1,k).

d) [2 marks] Solve the above recurrence relation by the backward substitution method to obtain an explicit formula for C(n) in n.

e) [1 mark] Write the complexity class that C(n) belongs to using the Big-Θ

Problem 2 (8 marks, 1.5 pages). Let A be an array of n integers.

a) [2 marks] Describe a brute-force algorithm that fifinds the minimum difference between two distinct elements of the array, where the difference between a and b is defifined to be |a b| [1 mark]. Analyse the time complexity (worst-case) of the algorithm using the big-O notation [1 mark]. Pseudocode/example demonstration are NOT required. Example: A = [3,6,1,3,20,6,9,15], output is 2 = 3-1.

b) [2 marks] Design a transform-and-conquer algorithm that fifinds the minimum difference between two distinct elements of the array with worst-case time complexity O(nlog(n)): description [1 mark], complexity analysis [1 mark]. Pseudocode/example demonstration are NOT required. If your algorithm only has average-case complexity O(nlog(n)) then a 0.5 mark deduction applies.

c) [4 marks] Given that A is already sorted in a non-decreasing order, design an algorithm with worst-case time complexity O(n) that outputs the absolute values of the elements of A in an increasing order with no duplications: description and pseudocode [2 marks], complexity analysis [1 mark], example demonstration on the provided A [1 mark]. If your algorithm only has average-case complexity O(n) then 2 marks will be deducted. Example: for A = [15,9,6,3,1,3,6,20], the output is B = [1,3,6,9,15,20].

Problem 3. [10 marks, 1.5 pages] (Dijkstra’s algorithm + min-heap) Given a graph as in Fig. 1, we are interested in fifinding the shortest paths from the source a to all other vertices using the Dijkstra’s algorithm and a min-heap as a priority queue. Note that a min-heap is the same as a max-heap, except that the key stored at a parent node is required to be smaller than or equal to the keys stored at its two child nodes. In the context of the Dijkstra’s algorithm, a node in the min-heap tree has the format v(pv,dv),where dv is the length of the current shortest path from the source to v and pv is the second to last node along that part (right before v). For example, c(a,1) is one such node.

We treat dv as the key of Node v in the heap, where v {a,b, c,d, e, f , g,h}.

Figure 1: An input graph for the Dijkstra’s algorithm. Edge weights are given as integers next to the edges. For example, the weight of the edge (a,b) is 7.

a) [1 mark] The min-heap after a(a,0) is removed is given in Fig. 2. The next node to be removed from the heap is c(a,1). Draw the heap after c(a,1) has been removed and the tree has been heapifified, assuming that ∞ ≥ ∞ (note: no need to swap if both parent and children are ). No intermediate steps are required.

Figure 2: The min-heap (priority queue) after a(a,0) has been removed.

b) [2 marks] Draw the heap(s) after each neighbour of c has been updated and the tree has been heapifified (see the pseudocode in the lecture Slide 30, Week 9). If there are multiple updates then draw multiple heaps, each of which is obtained after one update. Note that neighbours are updated in the alphabetical order, e.g., d must be updated before e. No intermediate steps, i.e., swaps, are required. Follow the discussion on Ed Forum for how to update a node in a heap.

c) [5 marks] Complete Table 1 with correct answers. You are required to follow strictly the steps in the Dijkstra’s algorithm taught in the lecture of Week 9.

d) [2 marks] Fill Table 2 with the shortest paths AND the corresponding distances from a to ALL other vertices in the format a ? ? v | dv, for instance, a c | 1.

2 Submission

The fifinal submission (via Canvas) will consist of:

  • Your solutions to all questions in a PDF fifile of font size 12pt and your agreement to the honour code (see the fifirst page). You may also submit the code in Problem 5.

Late Submission Penalty: Late submissions will incur a 10% penalty on the total marks of the corresponding assessment task per day or part of day late, i.e, 4 marks per day. Submissions that are late by 5 days or more are not accepted and will be awarded zero, unless Special Consideration has been granted. Granted Special Considerations with new due date set after the results have been released (typically 2 weeks after the deadline) will automatically result in an equivalent assessment in the form of a practical test, assessing the same knowledge and skills of the assignment (location and time to be arranged by the coordinator). Please ensure your submission is correct and up-to-date, re-submissions after the due date and time will be considered as late submissions. The core teaching servers and Canvas can be slow, so please do double check ensure you have your assignments done and submitted a little before the submission deadline to avoid submitting late.

Assessment declaration: By submitting this assessment, you agree to the assessment declaration – https://www.rmit.edu.au/students/student-essentials/ assessment-and-exams/assessment/assessment-declaration

3 Plagiarism Policy

University Policy on Academic Honesty and Plagiarism: You are reminded that all submitted work in this subject is to be the work of you alone. It should not be shared with other students. Multiple automated similarity checking software will be used to compare submissions. It is University policy that cheating by students in any form is not permitted, and that work submitted for assessment purposes must be the independent work of the student(s) concerned. Plagiarism of any form will result in zero marks being given for this assessment, and can result in disciplinary action.

For more details, please see the policy at

https://www.rmit.edu.au/students/student- essentials/ assessment-and-results/academic-integrity.

4 Getting Help

There are multiple venues to get help. We will hold separate Q&A sessions exclusively for Assignment 2. We encourage you to check and participate in the Ed Discussion Forum, on which we have a pinned discussion thread for this assignment. Although we encourage participation in the forums, please refrain from posting solutions or suggestions leading to solutions.