跳转至

Project 5-Three Partition

Project 5 - Three Partition

Solo 的补分proj.

Project Description

You have a very simple task: just partition a series of numbers into three parts and make their sum is the same.

More formally, you will first get a positive integer \(N\) indicating that there will be totally \(N\) numbers as follow. And then you will get N positive integers \(a_1,a_2,\cdots a_n\), you should calculate whether there is a three - partition that can partition them into three parts and their sum is exactly the same, if the answer is yes, you also need to output the 3 parts in 3 lines.

For example, if the input is 5 1 2 3 4 5, obviously there is a three - partition that can partition 1 2 3 4 5 into three parts and their sum is exactly the same, so you should first answer yes and output 1 4 in the first line, output 2 3 in the second line, output 5 in the third line(actually the order of lines and the order of numbers in each line don't matter).

But if the input is 5 7 8 9 10 11, you should answer no because there is no three - partition that can partition 7 8 9 10 11 into three parts and their sum is exactly the same.

You should try different types of algorithm to solve the problem, and for each type of algorithm, you should analyze the time complexity and answer the question: Is the time complexity polynomial time?

Also to check the correctness of your algorithm, you should generate appropriate data to check it, including small scale and big scale, and analyze their running time.

Bonus: If partition these numbers into \(4,5,\cdots,k\)(\(k\) is a given number but not a input) parts, do your above different types of algorithm also work? If not work, can you try some new type of algorithm to solve it? If work, Can you analyze the time complexity of them?

Group Presentation Submission

You should upload zip to 5-1 and slides to 5-2.

You are required to upload your submission materials in a zip file that contains the project report (in pdf format), the source code (including the implementation and the testing code), and the testing data. The file structure should be organized as follows:

PxGyy.zip
├── code
│   ├── source code files (*.c,*.h, ...)
│   └── readme.txt (Instructions on how to build the executable file and how to run it)
├── documents
│   ├── PxGyy.pdf
│   └── Other materials if necessary
└── testcases
    ├── 1.in (Input file 1, plain text in UTF-8, the same below)
    ├── 1.out (Output file 1)
    ├── 2.in
    ├── 2.out
    ├── ...
    └── readme.txt (Simple specification of testing data)

In the name of report document and zip PxGyy.pdf/zip, x is the project number (5 for this project) and yy is your group number with 2 digits, 01 for example. E.g. P5G01.zip.

report

The report should be written clearly and neatly in English. It should starts with a title page containing the title, the group id if you work as a group, the author names, and an abstract summarizing your work. Within the main text following the title page, the report should present the following contents.

  • A clear description of this project.
  • A description of different types of algorithm.
  • A theoretical analysis of their time complexity.
  • A description of your experiment, including the data you use in test and the analyze of the running time. You have better use a graph to present it.
  • bonus If partition these numbers into \(4,5,⋯,k\)($\(k\) is a given number but not a input) parts, do you r above different types of algorithm also work? If not work, can you try some new type of algorithm to solve it? If work, Can you analyze the time complexity of them? Conclusion and discussion. You are encouraged to write your report using \(\LaTeX\) (try overleaf.com), but Microsoft Word is also fine.

code

Generally, you are required to implement in C or C++. You should not use any STL if you implement in C++. You may ask TA for permission if you want to use a language other than C or C++. The source code should be in good style, and have sufficient comments.

test

All the testing data should be stored and uploaded (even if they are randomly generated).

A readme.txt that simply specifies the testing data is required.

slides The slides should be named as PxGyy.pptx, where x is the project id and yy is your group number with 2 digits, 01 for example. E.g. P5G01.pptx. The slides should submitted to 5-2.

Pay attention that only the group leader needs to upload the materials and submit them. Other group members do not need to upload anything, but should click the "submit" button of 5-1 and 5-2 to be graded.

Individual bonus Submit

You should submit a zip to 5-3, and the requirement of zip is the same as above. The zip file should be named as Px_id_name.zip instead, where id is your student id and name is in English without spaces. E.g. P5_3240100000_ZhangSan.zip.

\(\text{phira phira lēṃge!}\)