COMP2013代做、代寫Data Structures and Algorithms
COMP2013代做、代寫Data Structures and Algorithms
時間：2024-04-24 來源： 作者： 我要糾錯
COMP2013 Data Structures and Algorithms
Programming Assignment 2 Deadline: 10:00am, 22th April, 2024
Instructions
Submit the soft-copy of your program to Learn@PolyU
You can only submit one program file (either C++ or Java or Python),
and the filename must follow the format below.
Language Filename format Filename example
C++ mainStudentID.cpp main10987654d.cpp
Java mainStudentID.java main10987654d.java
Python mainStudentID.py main10987654d.py
- We only accept file types in .cpp, .java, .py. We do not accept file types like .ipynb, .h, etc.
Section 1. Problem
You have n pipes with lengths in meters. You need to connect all these pipes into one pipe. You can
connect two pipes into one at a time. For two pipes with length i and j meters respectively, the cost to
connect them is 𝑡𝑡(𝑖𝑖,𝑗𝑗) = 𝑚𝑚𝑚𝑚𝑚𝑚(𝑖𝑖,𝑗𝑗) + 3; the connected pipe has length i+j meters.
The task is to minimize the total cost to connect all n pipes into one pipe, where the total cost is the sum
of all connection costs.
Example: you have 4 pipes in length 6, 5, 2, 8. After connecting all pipes, you will get one pipe with
length 21 meters. Your task is to minimize the total cost to connect these pipes into one. There can be
different ways to perform the connections. Given 4 pipes, there are
4
2 ×
3
2 = 18 ways to perform the
connections, and below shows one possible way (not with optimal cost),
- Connect pipes with length 6,5 first, with cost 9, and result in three pipes with length 11,2,8
- Then connect pipes with length 11, 2, with cost 14, and result in two pipes with length 13, 8
- Then connect pipes with length 13, 8, with cost 16, and result in one pipe with length 21.
- The total cost of the connections above is 9+14+16=39.
For this example, an optimal way to connect pipes should have minimum cost 34.
Given n pipes, implement a greedy algorithm that can correctly obtain the minimum total cost to connect
them into one pipe, adhering to the requirements above. Your program should have time complexity
O(nlogn). (You do not need to prove the optimality of your greedy algorithm.)
Section 2. input and output of your format
In the table below, it shows a sample of the input file and the output of your program. Your program
should take as input a filename (e.g., file1.txt), and then read the integers (one integer per line) in the file.
These integers are the length of pipes. The number of non-empty lines in the file is the number of pipes
you need to handle.
Your program will output an integer value to the screen, which is the minimum cost obtained by your
program.
Sample input file “file1.txt” The output on screen (stdout)
6 34
5
2
8
We will run your program by a command line like:
where the argument “file1.txt” is an example of the input filename.
Your program should only output the result number.
Please follow the above output format and DO NOT print any extra information.
Notes:
- We will use 10 test cases to grade your program
- The pipe length is positive integer in range [1, 1000]
- In a test case, the number of pipes is at most 10000.
Implementation Instructions:
In your implementation, you can use existing libraries that support data structures like list, stack, queue,
min-heap, max-heap, priority-queue, etc. (In other words, you do not need to implement these
fundamental data structures)
You are allowed to use operator or standard library function (e.g., in C++, Java, Python) to perform
lexicographic comparison for string. Examples:
• C++: https://cplusplus.com/reference/string/string/compare/
• Java: https://docs.oracle.com/javase/tutorial/java/data/comparestrings.html
• Python: https://docs.python.org/3/library/stdtypes.html#comparisons
Section 3: Grading Criteria
Naming conventions, compilation and execution commands
Before submission, rename your program to
mainStudentID.cpp, e.g., main10987654d.cpp
OR mainStudentID.java, e.g., main10987654d.java
OR mainStudentID.py, e.g., main10987654d.py
[C++ and Java only] Make sure that you can compile your program using the command:
g++ mainStudentID.cpp -o mainStudentID
OR javac mainStudentID.java
o No marks will be given if your program cannot be compiled.
Language Command line
C++ (after compilation) ./mainStudentID file1.txt
Java (after compilation) java mainStudentID file1.txt
Python python mainStudentID.py file1.txt
We will run your program by a command line like:
./mainStudentID file1.txt
OR java mainStudentID file1.txt
OR python mainStudentID.py file1.txt
where the argument “file1.txt” is an example of the input filename.
Make sure that you can execute the above commands on the COMP apollo server successfully.
Otherwise, no marks will be given. The current versions on apollo are as follows:
g++ (GCC) 4.8.5, javac 1.8.0_20, Python 2.7.5
Test files for grading
Total marks: 100 marks
Your program will be graded by using 10 test files.
For each test case, if your program can return the correct output within 1 minute, it is a successful case
and you get 10 marks. Otherwise, this is a failed case with 0 marks.
- The running time of your program will be measured on the COMP apollo server.
If your program is not a greedy approach, extra 50 marks will be deducted from the total marks you
get from the 10 test cases above. Final grade of the assignment is in the range [0,100].
Appendix
(1) How to activate your COMP account?
Please click the following link to activate your COMP account:
https://acct.comp.polyu.edu.hk/
according to the instructions in:
https://acct.comp.polyu.edu.hk/files/COMPStudentAccountSelfActivation.pdf
(2) How to login the COMP apollo server?
[Step 1]
Use PuTTY (or any SSH client
program)
Enter the host name
csdoor.comp.polyu.edu.hk
Click the “Open” button.
If you see the message “The host
key is not cached for this
server…”,
just accept to continue.
[Step 2]
Enter your COMP account
username and password.
Note that, when you are entering
the password, it is not displayed
in PuTTY.
[Step 3]
Enter the hostname apollo
Then enter your COMP account
password (the same as in Step 2).
[Step 4]
Use WinSCP (or any SFTP client program).
Enter the host name csdoor.comp.polyu.edu.hk
Enter your COMP account username and password.
Upload your program to the server.
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
標簽：
|
|
|
|
|
|
|
|