COMP3506/7505 课业解析

COMP3506/7505 Task2： 

题意：实现sortQueue与FindMissingNumber这两个算法，保证算法的高效 解析： sortQueue：在原始队列上使用O(1)的额外辅助空间，对队列中的元素进行从小到大的排序；将大的数放到后面，这样每轮都有元素到达制定位置，最坏的情况下复杂度是O(n^2) FindMissingNumber：使用递归算法检查数组中按照某种算术序列缺失的元素。返回正常序列的和减去缺失数组的和的差值即为缺失数据 

 涉及知识点： sortQueue：冒泡排序 FindMissingNumber：递归思想

COMP3506/7505 Homework Task 2
Due Fri 23 Aug 2019, 5:00pm
10 marks total
Overview
The goal of this problem set is to become an expert at writing non-trivial algorithms and analysing
the runtime efficiency of these algorithms.
You have been supplied with the file Algorithms.java. You are required to implement two methods - sortQueue and FindMissingNumber. Your implementations of both these algorithms
should be as efficient as possible.
sortQueue
The sortQueue algorithm is described as follows:
Given a queue of elements implementing the Comparable interface, sort the elements of the queue
using O(1) extra space.
Dequeing the elements of the sorted queue should yield each element in ascending order. Your
solution should take a java.util.Queue as input (https://docs.oracle.com/javase/7/docs/
api/java/util/Queue.html). You are not allowed to convert this queue to another data structure.
Example:
Input: Queue(1, 3, 5, 4, 2)
Output: Queue(1, 2, 3, 4, 5)
Input: Queue("a", "b", "c", "b", "a")
Output: Queue("a", "a", "b", "b", "c")
1
findMissingNumber
The findMissingNumber algorithm is described as follows:
Given an array of integers representing an arithmetic sequence, find the missing element.
You may assume that the missing element will not be at the start or end of the sequence, that the
input array will contain at least two elements, and that exactly one element will be missing from
the array.
Example:
Input: [2, 4, 6, 8, 10, 12, 14, 18, 20]
Output: 16
Input: [4, 1, -5]
Output: -2
Your Task
1. (3 marks) Write an iterative implementation of the sortQueue algorithm described above.
You may write one or more helper methods as a part of your solution. Your algorithm must
use O(1) extra space (that is, it must run in-place) and your solution should be as efficient
as possible.
2. (2 marks) Represent the worst-case running time of your sortQueue algorithm as a mathematical function. Then, use the mathematical definition of big-O to determine an asymptotic
bound on this function (that is, you should compute the values of c and n0 to show that the
bound exists). You may assume the runtime complexities of the standard queue methods
are as described in lectures.
3. (3 marks) Write a recursive implementation of the findMissingNumber algorithm described
above. You may write one or more helper methods as a part of your solution. Your algorithm
should be as efficient as possible.
4. (2 marks) Express the worst-case running time of your findMissingNumber algorithm as a
mathematical recurrence. State an asymptotic bound in big-O notation for this recurrence.
Explain how you determined this bound.
2
Constraints
• You may only add private helper methods to Algorithms.java
• You may not add any member variables to Algorithms.java
• You may not use anything from the Java Collections Framework. The only exception to this
is using java.lang.Comparable and java.util.Queue in sortQueue.
• Your implementation should only use basic Java programming constructs and not other
libraries (apart from the ones described above)
Failure to adhere to these constraints will result in no marks for this exercise.
Submission and Marking
Submit two files as a part of your submission. Your solution to questions 1 and 3 should be in
Algorithms.java. Your answers to questions 2 and 4 should be in a PDF file named README.pdf.
Do not submit any other files or directories. To preserve anonymity, please do not include your
name in either of these files (it is okay to include your student number).
Questions 1 and 3 will be marked by an automated test suite with timeouts present on each of
the tests. A sample test suite has been provided in AlgorithmsTest.java. This test suite is not
comprehensive - there is no guarantee that passing these will ensure passing the tests used during
marking. It is recommended, but not required, that you write your own tests for your algorithms.
Your sortQueue algorithm must be iterative and use O(1) extra space, and your findMissingNumber algorithm must be recursive to be eligible for any marks for these questions. Marks may be
deducted for poor coding style and/or inefficient algorithms.
You should submit README.pdf through Turnitin - this will be manually marked by a tutor. Any
asymptotic bounds should be as tight as possible. Your solution should be electronically processed
- hand-written answers will not be accepted. If you are comfortable with the LATEX typesetting
system, it is recommended that you write your answers using it, however it is not a requirement.
Late Submissions and Extensions
Late submissions will not be accepted. It is your responsibility to ensure you have submitted your
work well in advance of the deadline (taking into account the possibility of computer or internet
issues). See the ECP for information about extensions.
Academic Misconduct
Students are reminded of the University’s policy on student misconduct, including plagiarism. See
the course profile and the School web page:
http://www.itee.uq.edu.au/itee-student-misconduct-including-plagiarism.
3