算法分析代写 Analysis of Algorithms代写 Practice Exam代写
614CSCI-570 Analysis of Algorithms Practice Exam - 2 算法分析代写 True/False Problems 1. For every graph G and every maximum flow on G, there always exists an edge such that increasing the ...
View detailsSearch the whole station
算法分析作业代写 IMPORTANT NOTES • If you are asked to develop/design an algorithm, you need to describe it in plain English first, say a paragraph,
• If you are asked to develop/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.
• 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 Canvas Discussion Forum or drop us an email at sonhoang.dau@rmit.edu.au.
• 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.
• All stories are fictitious and just for fun. Please do not take them seriously.
One day, your niece comes to visit you with a worried look on her face. It turns out that her teacher just gave a very tricky problem as part of their VCE Algorithmics Unit 3.
She has spent 3 days working on it without any success. As a loving (and very capable) uncle/aunt, you must help her out. Here is the problem.
Consider the algorithm mystery() whose input is an integer array A of size n.
a) [2 marks] What does the algorithm compute? Justify your answer.
b) [1 mark] What is the algorithmic paradigm the algorithm belongs to?
c) [1 marks] Write the recurrence relation (formula + base condition) for C(n), which counts the number of array elements comparisons.
d) [3 marks] Solve the 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.
As the Bitcoin price has quadrupled in the past one year (9/2020-9/2021), you have made a decision of becoming a miner to earn some profit. You find out that in Bitcoin blockchain and the like, miners are responsible for constructing blocks and if successful (being the first to solve a puzzle), will receive not only a base reward but also transaction fees included in the transactions in the block.
While the base reward is fixed and out of control of the miners, the transaction fees are not. You quickly figure out that one way for the miners to maximise their profit is to select the set of transactions that sum up to the highest fee. The problem formulation you come up with is: given n available transactions, in which transaction t_{i} has size s_{i} and pays fee f_{i} , 1 ≤ i ≤ n, the miner should select a set I of transaction (indices) that has the maximum total fee ∑_{i∈I }f_{i }while guaranteeing that the total size ∑_{i∈I} s_{i} does not exceed the block size limit b.
Design a greedy algorithm for this problem (note that it does NOT have to return the optimal solution): algorithm description (1 mark) + short pseudocode (1 mark) + complexity analysis (1 mark). Run it on the toy example in Table 1 with b = 8 and write down the list of transactions selected by the algorithm in their corresponding order (1 mark).
Design a dynamic programming algorithm of complexity O(nb) that can find a set of transactions that maximises the profit: write down the recursion formula (1 mark), build the dynamic programming table for the toy example in Table 1 with b = 8 (2 marks), and identify the set of transactions output by the algorithm together with the maximum profit (1 mark).
In the search for the meaning of life, you set off for a dangerous trip to visit a mysterious oracle living in a temple at the heart of the Great Victoria Desert. Barely escaping a terrible sand storm, you’ve finally found the oasis at a great cost: all the supplies have been buried under the sand and the only camel has run away. To make it worse, there is no sign of any source of water and all the plants surrounding the temple are dead. Apparently the oasis has been drying up for quite some time.
“Speak, human! You can ask me one question.” What a hoarse and emotionless voice! Is it because she has not had water for a long time? “Oracle, I… ”, You hesitate. Before going, you had a list of all deep-meaning questions prepared. But now, what the heck! Licking your chapped lips, you ask “Oracle… where can I find water?” The oracle regards you for almost five seconds, and then asks “Computer scientist, yes?” “Y… yes,” you reply, clearing your throat. She’s an oracle after all. But you suddenly have this strange thought: what did the oracle do for a living before taking this… job? But surely you cannot ask a second question.
The oracle immediately pulls out a piece of paper and a pen, writes something down and hands it to you eagerly as if she has been waiting to do this for a long time. Although it is rather dim in the temple, you can still feel her intense gaze under the veil. “The answer is in the solution,” said the oracle, still with her emotionless voice. You turn toward the door to get some more light.
It is a vaguely familiar problem about a compression algorithm. Not again!!! You groan and turn back to face the oracle, ready to shoot another question or at least, a complaint. But there is nobody there… But the unbearable thirst reminds you that you should not worry about the oracle’s whereabouts. The answer for where to find the water is in the solution, and you need to crack the problem first. Is the oracle helpful? Or does she just want to play? There’s only one way to find out…
Construct a min-heap (tree) using the bottom-up heap construction to represent the frequencies in Table 2 (using the given order). Please use (label:frequency), for example, “H:1”, for nodes in the heap. Describe (draw) all the steps required (use two-head arrows to indicate an exchange between two nodes). 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 the keys stored at its two children nodes.
Illustrate (draw) the process of dequeuing the two letters of smallest frequencies from the heap one by one (dequeue -> repair -> dequeue -> repair).
Illustrate (draw) the process of enqueuing the new element (i.e. enqueue -> repair), which results from the combination of frequencies of the two dequeued elements earlier. For example, if ‘H:1’ and ‘Y:2’ were dequeued, then the new element ‘HY:3’ would be enqueued.
Provide a complete construction of the Huffman tree (3 marks) together with the codes for all letters (1 mark). Only the complete final tree needs to be given. However, each intermediate node must be labelled with both frequencies, e.g. “3”, and the step in which it is constructed, e.g. “Step 1”. When constructing the trees, the following rule applies: for every node from the root, the frequency of its left child must be smaller than or equal to that of its right child.
(Have you found out her answer? Does it help?)
Figure 1: A toy example of twelve transactions with their corresponding sizes (red) and fees (green). For example, t_{3} has size s_{3} = 1 and fee f_{3} = 2. The dependency among transactions is represented by arrows: t_{j} → t_{i} means that t_{j} depends on t_{i} . For instance, t_{7} depends on t_{3}, which in turn depends on t_{1}. The block size limit is b = 18.
After executing your algorithms that select a set I of transactions from a pool of n unconfirmed transactions (waiting to be included in a block) that has total size ∑_{i∈I }s_{i }≤ b, where b is the block size limit, while achieving maximum total fee ∑_{i∈I} f_{i} , you discovered a problem with this formulation. It dawned on you that the transactions are NOT independent of each other. For instance, if Alice pays 1 bitcoin to Bob in Transaction
Figure 2: Dependency among Bitcoin transactions. Transaction j uses one output of Transaction i as its input. In such a case, Transaction j depends on Transaction i.
Suppose that you have run a preprocessing algorithm that returns the dependency list L_{j} that comprises of all i where t_{j} depends on t_{i} , for each 1 ≤ j ≤ n. For instance, in the toy example in Figure 1, L_{10} = {6,8} and L_{11} = {2,7}.
Design an efficient algorithm (worst-case complexity O(n^{2} )) that takes as input the number of transactions n, the sizes s_{i} and fees f_{i} , the dependency lists L_{i} , i = 1,…,n, and an index set J ⊆ {1,2,…,n}, and returns the list T_{J} (J ⊆ T_{J}) of ALL the transactions (indices) that must be included if the transactions {t_{j} : j ∈ J} are to be included in a block, so that the Dependency Rule is respected. For example, when J = {4,7}, we have T_{J} = {1,2,3,4,7}. Note that T_{J} must contain J as a subset. The solution must include: 算法分析作业代写
– (2 marks) algorithm description,
– (1 mark) short pseudocode, and
– (1 mark) complexity analysis, and
– (1 mark) the list of transactions T_{J} output by the algorithm applied to the toy example in Figure 1 with J = {5,10,11} and the corresponding total size & fee.
Based on Part a), design an exhaustive search (algorithm) that returns a set of transactions (indices) J^{∗} to form a block that respects the Dependency Rule and has total size at most b while maximising the total transaction fee. Input to the algorithm: n, b, s_{i} , f_{i} , L_{i} , i = 1,…,n. The solution must include:
– (1 mark) algorithm description, and
– (2 marks) the set of transactions (indices) J^{∗} output by the exhaustive search, its total size and its (maximum) total profit for the toy example in Figure 1.
b) [1 marks] Applicable if the algorithm can find an unrelated partitions with balance index 1 for h = 14 in less than 10 hours.
c) [1 bonus mark, 1 page] Provide a mathematical proof that the algorithm developed in Part a) can find an unrelated partition with balance index 0 or 1 for ALL h ≥ 2.
See the examples in Figure 3 for unrelated partitions of balance index 0/1 when h = 2,3. There can be other partitions satisfying the requirement. More details on how to prepare the solution for Problem 5 will be updated on Assignment 2 Queries (Discussion Forum).
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). 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.
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.
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 discussion forum on Canvas, 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.
更多代写：CS工程作业代写 托福在家考试作弊 英国法律Assignment代写 加拿大BIO生物学论文代写 法律专业论文作业代写 homework代写
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
CSCI-570 Analysis of Algorithms Practice Exam - 2 算法分析代写 True/False Problems 1. For every graph G and every maximum flow on G, there always exists an edge such that increasing the ...
View detailsCS420/520: Graph Theory with Applications to CS Homework 1 cs图论代写 Homework Policy: 1. Students should work on group assignments in groups of preferably three people. Each group submits ...
View details有留学生找澳洲CS代写被发现的么？想了解一下代写的靠谱程度 澳洲CS代写 有不少外出留学的留学生就能够发现，国外的作业可以说是多到离谱，基本上不是在写作业就是在写作业的路上，但是这些作业如果不做也不...
View detailsParallel Computing Homework Assignment 1 并行计算家庭作业代写 1.In the global sum problem that we discussed in class, in lecture 1, if we assume that there is a variable called my_rank (loca...
View details