COMP2013代做、代写C++，Java/Python编程

日期：2024-04-23 09:40

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.