COSC 2123代写、Python/Java程序代写

日期：2022-10-12 10:25

Algorithms and Analysis

COSC 2123/1285

Assignment 2: Algorithm Design & Complexity Analysis

Assessment Type Individual Assignment. Submit online via Canvas → Assignments → Assignment 2. Clarifications/updates/FAQs can be

found in Ed Forum → Assignment 2: General Discussions.

Due Dates Deadline 1 Week 11, October 4, 23:59, for Problems 1-3,

Deadline 2 Week 12, October 16, 23:59, for Problems 4-5

Marks 40

IMPORTANT NOTES

• If you are asked to design an algorithm, you need to describe it in plain English first, say a paragraph, and then provide an unambiguous pseudo code,

unless specified otherwise. The description must include enough details to understand how the algorithm runs and what the complexity is roughly. All algorithm

descriptions and pseudo codes required in this assignment are at most half a page

in length. Worst-case complexity is assumed unless specified otherwise.

• Standard array operations such as sorting, linear search, binary search, sum,

max/min elements, as well as algorithms discussed in the pre-recorded lectures

can be used straight away (but make sure to include the input and output if you

are using them as a library). However, if some modification is needed, you have to

provide a full description. If you are not clear whether certain algorithms/operations are standard or not, post it to Ed Discussion Forum or drop Hoang a Team

message.

• Marks are given based on correctness, conciseness (with page limits), and clarity of your answers. If the marker thinks that the answer is completely not understandable, a zero mark might be given. If correct, ambiguous solutions may still

receive a deduction of 0.5 mark for the lack of clarity.

• Page limits apply to ALL problems in this assignment. Over-length answers may

attract mark deduction (0.5 per question). We do this to (1) make sure you develop

a concise solution and (2) to keep the reading/marking time under control. Please

do NOT include the problem statements in your submission because this

may increase Turnitin’s similarity scores significantly.

• This is an individual assignment. While you are encouraged to seek clarifications

for questions on Ed Forum, please do NOT discuss solutions or post hints leading

to solutions.

• In the submission (your PDF file), you will be required to certify that the submitted

solution represents your own work only by agreeing to the following statement:

I certify that this is all my own original work. If I took any parts from

elsewhere, then they were non-essential parts of the assignment, and they

are clearly attributed in my submission. I will show that I agree to this

honour code by typing “Yes":

2

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 ≤ n−1, and

an integer k. We assume that n is a power of 2.

Algorithm mystery(A[0,...,(n−1)],`,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,n−1,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-Θ notation.

3

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

a) [2 marks] Describe a brute-force algorithm that finds the minimum difference between two distinct elements of the array, where the difference between a and b

is defined 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 finds 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].

4

Problem 3. [10 marks, 1.5 pages] (Dijkstra’s algorithm + min-heap) Given a graph

as in Fig. 1, we are interested in finding 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 heapified, assuming that ∞ ≥ ∞ (note: no need to swap if

both parent and children are ∞). No intermediate steps are required.

c(a, 1)

b(a, 7)

h(−, ∞)

e(−, ∞) f(−, ∞) g(−, ∞)

d(a, 5)

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 heapified (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.

5

S: vertices whose shortest

paths have been known

Priority queue of remaining vertices

1 a(a,0) b(a,7), c(a,1),d(a,5), e(−,∞), f (−,∞), g(−,∞),h(−,∞)

2 a(a,0), c(a,1)

Table 1: Complete this table for Part c).

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.

Shortest Paths Distances

Table 2: Complete this table for Part d).

6

2 Part II: Advanced

Problem 4 (9 marks, 1.5 pages). A database of n records, each of which has size m bits

(we assume that m is large) is maintained at two different servers X and Y. As sometimes

a record may get updated at one server and not at the other, the servers X and Y have

to sync their (possibly different) databases x = (x1,..., xn) and y = (y1,..., yn) from time

to time to make sure they are the same. At the synchronization time, the two servers

exchange some data in one or several rounds of communications.

A trivial synchronisation algorithm is as follows: X sends x via the internet to Y,

which verifies every record of x against that of its database y; for each 1 ≤ i ≤ n, if xi = yi

then Y does nothing, otherwise, it will either update yi ← xi

if xi

is newer or send (i, yi)

to X if its record is newer; upon receiving a pair (i, yi), X updates xi ← yi

. We assume

there is an efficient mechanism (which is not our focus) to decide which version of the

record is newer (e.g., using a naming convention like ver-1.2.1 is newer than ver-1.2.0).

While this solution works, it requires a huge bandwidth because at least n records have

to be sent across the network.

Our goal is to design a more efficient protocol/algorithms using a tool called cryptographic hash function. A cryptographic hash function h(·) takes as input any piece of

data x of any size and returns a fixed-size string h(x) (e.g., h(x) is of size 256 bits for

SHA-256). Moreover, different from a non-cryptographic hash function (Week 11), they

are collision-resistant, that is, it’s hard to find two different inputs that hash to the same

output. As a consequence, in practice, we can assume that if a 6= b then h(a) 6= h(b). For

simplicity, we assume that the following assumptions hold.

• At most one item is different between the two databases, that is, either xi = yi for

all i = 1,...,n, or there exists an index i

∗

such that xi

∗ 6= yi

∗ and xi = yi for all i 6= i

• The computation complexity is measured by the number of hashes required to

be computed by both X and Y and also by the amount of data that are hashed. For

instance, the trivial protocol described above requires no hash computation, and

hence, the computation complexity is zero.

• The communication complexity is measured by the number of hashes and the

number of records communicated between X and Y. For instance, the trivial protocol sends no hashes and n records, which is very expensive (a record is much larger

than a hash).

Your task is to design a synchronisation algorithm that requires a small communication complexity (most important) and also a reasonable computation complexity.

More specifically, you need to include the following in your answer.

a) (Overview - 2 mark) An overview of how your algorithm works, why it solves the

problem, and what are the communication and computation complexities.

b) (Detailed description - 3 marks) A detailed description of the main steps of the

algorithm, describing what X and Y do to sync the two databases. You could also

write your description using a pseudocode. The goal is to guarantee that other people can understand clearly how the algorithm works. The format of the pseudocode

is not important.

7

c) (Demonstration - 2 marks) A demonstration of how the algorithm works on a

small example, e.g., when n = 8.

d) (Analysis - 2 marks) State the communication and computation complexities of

your algorithm and explain why it has these complexities. The input size is (n,m).

The given marks are maximum possible for the parts. Your actual marks depend on

how efficient your algorithm is (regarding the communication complexity (major criteria) AND the computation complexity) and also how well it is presented. A correct and

efficient but poorly written solution could still attract a low mark. An incorrect solution

will get a zero mark.

8

Problem 5 (5 marks, 2 pages). Research a well-known problem of your own interest in

any field (science, engineering, technology) that can be solved by a computer algorithm.

Write a 1- to 2-page report on a popular algorithm that solves that particular problem and include in your report: (1) a problem description and why it is important and/or

interesting, (2) the algorithm description, (3) a pseudocode, (4) a demonstration on a toy

example, and (5) a complexity analysis.

You could include a few (1-5) references that you used when researching the problem/algorithm, but the writing should be your own. A similarity score of 25% and above

between your report and any existing source may indicate plagiarism. The report should

be typed in a text editor, e.g., words or Latex, and not handwritten. Marks will be

decided based on the correctness, clarity, and the sophistication of the problem/algorithm discussed. A report that is not well written or about a trivial/straightforward

problem/algorithm will receive a low mark.

Note that the problem/algorithm should NOT be among those already discussed in

the pre-recorded lectures/workshops. If you present a problem/algorithm that has been

discussed in the lectures/workshops, you will get a zero mark for Problem 5.

You could start from our textbook or check the following list from Wiki for a start.

https://en.wikipedia.org/wiki/List_of_algorithms

9

3 Submission

The final submission (via Canvas) will consist of:

• Your solutions to all questions in a PDF file of font size 12pt and your agreement

to the honour code (see the first page).

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-andexams/assessment/assessment-declaration

4 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.

5 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.

10