当前位置:天才代写 > C++/C代写 > computer programs代写 Algorithms代写 C / C ++代写 Java代写

computer programs代写 Algorithms代写 C / C ++代写 Java代写

2020-12-15 16:46 星期二 所属: C++/C代写 浏览:126

computer programs代写

COMP3600/6466 — Algorithms

computer programs代写 This assignment consists of two parts. In the second part, you need to write computer programs. You should write

Convenor: Hanna Kurniawati ([email protected])

E-mail: comp 3600 [email protected] OR [email protected] Assignment 2

Due: Monday, 30 September 2019 23:59 GMT+10

Notes:computer programs代写

  • This assignment consists of two parts. In the second part, you need to write computer programs. You should write your programs in C/C++/Java. No other programming language is accepted. We will support only C++.
  • This assignment comes with two scaffolding, main.cpp and rbbtree template.h, as well as testcases. All can be downloaded from the class website.
  • Please submit both the report and the source codes, following the format below, with [studentID] replaced by your student ID, e.g., U1234567.

Please write your report in a single .pdf file, named A2[studentID].pdf.

Please name the source code that contains your main function for Part B Q2 to be A2[studentID].cpp(or the suitable extension).computer programs代写

Please put all your source codes in a single directory, named A2[studentID].

Pleasezip your report and the directory containing your source codes (please exclude the object files and executables) into a single file, named A2[studentID].zip .

Pleasesubmit the .zip file viaPlease note that the maximum file size you can upload is 200MB.computer programs代写

Please save your submission as draft, so that you can re-upload it until the last minute. Once the grace period is over, the last saved draft in wattle will be locked as your submission.

  • You can submit a scanned copy of a handwritten report. However, the handwriting must be neat enough for the teaching staff to read them. If we can’t read them, we will not mark them and therefore, you will get a 0 mark for the report component. Our preference is you type your report. This is a good time to learn how to use TeX/LaTeX.
  • We provide 13 hours grace period. This means, there will be no penalty if you submit before Tuesday, 1 October 2019 13:00 Canberra time. However, we will NOT accept assignment submission beyond this time.computer programs代写
  • Assignmentmarking:
The total mark you can get in this assignment is 100

This assignment will contribute 20% to your overall

Thisassignment is  However, we strongly suggest that you do this assignment. The results of this assignment will help you understand how much you have understood the materials.

  • Discussion with your colleagues are allowed and encouraged. However, you still need to work on the assign- ment on your own AND write the names you discussed this assignment with.computer programs代写
  • You are allowed to use materials from books, slides, etc. as reference. You still need to write the solution yourself and put a reference to the source. A reference need to be a full citation and specific, e.g., T.H. Cormen,C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms 3rd Ed. MIT Press. 2009. Sec. 2.2.
Clarifications:computer programs代写
  • 10 Sep’19: Add clarification on the requirement to use red-black tree for Part B Q2c, in particular for this question, your algorithm must:

Only use red-black tree datastructure

Assume that the maximum time index is a variable (i.e., the complexity requirement should still hold if the maximum time index is a variable k, which is given as input, rather than145)

In the implementation of the algorithm (Part B Q2d), the implementation must follow the algorithm you have written in Part B Q2c. You are only allowed to use other data structure to output the sorted list of session IDs

—that is, the second line of the output.

  • 9 Sep’19: Clarifications in blue text, which consists of:

Part A, Q1, clarify what k

Part A, Q2, clarifications of x and y and the input to the function, as well as n as the number of nodes in the tree T.

Part B, Q2b, n is the number of nodes in the red-black tree that are already in the tree when a node is inserted.

Part B, Q2c, n refers to the number of lecture sessions.computer programs代写

Part B, Program input: The session ID is sorted.

You can add functionalities in the code we provided with this assignment.

29 Aug’19: The ancestor of a node x includes the node itself.

29Aug’19: Please set the output of your program (for Part B Q2d) to be sorted in ascending

[40 points] Part A.computer programs代写

  1. [10points] Mr Bug is known for developing software that are  The latest software he delivers to Mr Fix’s company is supposed to sort an array of n numbers in ascending order. However, upon using the software, Mr Fix notices that the software does not sort the numbers exactly correct: It always places the numbers within k slots of its proper position.

This means, suppose the correct position of a number x in the sorted array is at indexi, then in the output of Mr Bug s/w, the number x can be placed in any index between [max(0, i k), min(i+kn)]. Since Mr Bug is no longer reachable, Mr Fix decided to take the output of Mr Bug software and sort them correctly. Since the data can be any type of data, Mr Fix would like to use comparison-based sorting to sort the output of Mr Bug’s software. Mr Fix thinks for these “pre-sorted” numbers, the comparison-based sorting procedure takes Ω(n log k) number of comparisons, rather than Ω(n log n), where k ≤ n . Is he correct? Please provide the proof to support or refute Mr Fix argument.computer programs代写

[20points] Let T be a full binary search tree of height h.

And, let A(x) of a leaf node x in T be the ancestor set of x (i.e., it is the union of x’s parent, grandparent, all the way to the  Here, we follow a common convention in algorithms that duplicates in union set of tree nodes is checked based on the key and that the ancestor of a node includes the node itself. Suppose f (x, y) = aA(x)∪A(y) a.key. Please:

(a)[10 points] Design an algorithm that can compute f (x, y) in O(n log n) time, where n is the number of nodes in T.

(b)[10 points] Derive the time complexity of the algorithm you designed in 2a.

Note that when one implements a function that takes x and y as inputs, these inputs become input argument to the implemented function. To simplify the problem, you can assume each node has a unique key. Of course, if your algorithm can handle non-unique key, it should be fine too.computer programs代写

3.[10 points] Every student enrolled at UNA is given a locker to store their books.

The locker has a lock mechanism akin to a luggage lock with 3-digit password lock (Fig.  1 shows an illustration).   Suppose the password each lock is set uniformly   at random and independently from the other locks by the locker administrator, and suppose this password cannot be changed. The administrator will improve this lock mechanism once the number of enrolled students at UNA is large enough that there’s more than 50% chance that two UNA students have the same password lock. How many enrolled students should UNA has before the administrator improve the lock mechanism? Please explain your answer.

Figure 1: An illustration of the luggage lock for UNA’s students’ lockers.

[60 points] Part B.

Finding a parking spot during semester time is a big problem at UNA, and Mr ParkingPls is determined to address this problem. To this end, he observes that the difficulty in finding a parking spot is worst on a certain day of the week and a certain time on that day. He hypothesises that the main culprit of the worst parking problem is that there is an extremely large number of overlapping lecture sessions on that particular day and time. If this is true, he can recommend that UNA either redistribute the lecture slots more evenly during the week or rent a nearby land on the particular day and time each week to expand its parking capacity.

Of course first,  Mr ParkingPls must test his hypothesis.computer programs代写

To  this end,  he has obtained the schedule of all lectures  at UNA. Since all classes at UNA either starts or ends at the beginning of an hour or half an hour, Mr ParkingPls simplifies the lecture sessions representation by creating a time index for every half-hour between 06:00 and 20:00 (inclusive) within a week —that is, time-1 refers to Monday 06:00, time-2 refers to Monday 06:30, , time-145 refers to Friday 20:00—. He then represents each lecture session as a half-open interval of time index, e.g., interval [3, 5) means the lecture starts on Monday 07:00 end ends (at a negligible amount) before Monday 08:00. The question is now to find the time index with the most number of overlapping lecture sessions. Now, since he has only limited knowledge about Algorithms, he asks your help.

computer programs代写
computer programs代写

Your tasks

  1. [15pts] Mr ParkingPls is convinced that to find the time index with the most overlapping lecture sessions, one only needs to find overlaps between time indices at the beginning or end of the intervals, rather the entire time index. The question is:

(a)[5 pts] Is Mr ParkingPlscorrect?

(b)[10pts] If Mr ParkingPls is correct, please support your answer with a  Otherwise, please provide a counter-example.computer programs代写

2.[45 pts] Since Mr ParkingPls would like to use this work for other much larger projects where new sessions can be added quite often, Mr ParkingPls would like to use Red-Black Tree and asked your help.

To help him, please:

(a)[10 pts] Design a suitable Red-Black Tree data structure for Mr ParkingPls’ problem. This means that givena Red-Black Tree implementation as defined in [CLRS]  13, how you would use/augment/modifythis underlying data structure for Mr ParkingPls problem. Hint: You might want to read [CLRS] sec. 14.3 first (provided as additional resources to this assignment).

(b)[5 pts] Please provide an algorithm with (log n) complexity for inserting a node to the tree you have designedin 2a, along with the derivation of its complexity  The notation n refers to the number ofnodes that are already in the tree prior to insertion. For the algorithm, you can use the insertion procedure of Red-Black Tree in [CLRS] ch. 13 as a basis and stated only the modifications needed, if alterations are needed. If no alteration is needed, please explain why.computer programs代写

(c)[15 pts] Please provide an algorithm for finding the time index with the largest number of overlapping lecture sessions in the red-black tree you designed. Please also provide the correctness proof (using loop invariant) and the time complexity (with its derivation) of your algorithms. You will get full mark if the time complexity of your algorithm is O(1) and at most 9 points if the time complexity of your algorithmisO(log n), where n is the number of lecture sessions.

 Please note that in this question:computer programs代写
  • You can only use red-black tree datastructure
  • You need to assume that the maximum time index is a variable (i.e., the complexity requirement should still hold if the maximum time index is a variable k, which is given as input, rather than 145) because, Mr ParkingPls would like to use the algorithm for other parking issues

(d)[15 pts] Please implement the above solution such that the user can find the time index by giving the command “A2[studentID] input file name” OR “java A2[studentID] input file name” from thecommand prompt. The input format is described in the next section. We provide you with a main.cpp and a scaf- folding for Red-Black  If you use C/C++, you need to implement the node insertion function and the algorithm you provided in 2c on top of the provided main function and Red-Black Tree scaffolding.computer programs代写

If you use java, you need to make sure that your java program accepts the same input as the provided main.cpp .

You also need to develop Red-Black Tree yourself. If you choose this path, you might want to first check which operations of Red-Black Tree you need for this assignment and implement only those operations. Note: You are not allowed to use TreeMap or other Java Red-Black Tree library.

Program Marking: If your program compiles and runs, you will get 3 points. We will then run your program on 6 test cases: 2 cases would have up to 5,000 sessions, 2 cases would have 5,001 – 500,000 sessions, and 2 cases would have 500,001 – 5,000,000 sessions. For each test case, your program will be given a total of (log n + 0.01)sec CPU time to find a solution. computer programs代写

This time limit includes the time for reading the file, inserting the data to the red-black tree, finding the solution, and printing the solution. The time limit will be rounded up to 2 decimal digit. You can assume your program will have access to at most 12GB RAM. It will be run as a single thread process on a computer with Intel i7 3.4GHz processor. For each test case that your program solves correctly within the given time and memory limit, you will get 2 points.

Examples of the test cases are available in

https://cs.anu.edu.au/courses/comp3600/a2-testCases.zip.

Input to the Program computer programs代写

The program will accept a single argument, which is the name of the input file. The input file contains N + 1 lines, where N is the number of lecture session intervals.

The first line consists of a single number, which is N.

Each line in the next N lines consists of three numbers, separated by a white space. The first number is the session ID, the second number is starting time index, and the third number is the ending time index.

The session ID is sorted, in the sense that ID-i would be in line-(i + 1).

Example:

5

1 96 101

2 46 49

3 76 77

4 8 10

5 4 10

Output of the Programcomputer programs代写

The program outputs two lines to the standard output stream (i.e., use cout if you use C++).

The first line contains two numbers, each separated by a white space. The first number is the time index with the most number of overlapping lecture sessions. Let’s denote this time index as t. The second number (denoted as K) is the number of lecture sessions that overlap with time index t.computer programs代写

The second line consists of K numbers sorted in ascending order, each separated by a white space. Each number in this line is the ID of the session that overlaps with time index t.

Example output for the above input:

8 2

4 5

computer programs代写
computer programs代写

其他代写:考试助攻 计算机代写 project代写 java代写 algorithm代写 代写CS  function代写 C/C++代写 Data Analysis代写 app代写 物理代写 paper代写 r代写 金融经济统计代写 matlab代写

合作平台:天才代写 幽灵代写 写手招聘 Essay代写

 

天才代写-代写联系方式