COMP3023 Design and Analysis of Algorithms - Programming Assignment: Maximum contiguous array problem
COMP3023 24S Programming Assignment
Lecture 2 introduces a divide-and-conquer algorithm for the maximum contiguous array problem. In this programming assignment, you need to design and implement a dynamic programming algorithm under the following requirements.
Environment
- The implementation must be done in standard C (using gcc compiler). Please do not use visual studio. For the students who do not have the compiler, you can use online GDB at https://www.onlinegdb.com/.
- For FE students who haven’t taken COMP1023 Foudations of C Programming, you can use C++.
- Submissions which cannot pass gcc/g++ compilation, will directly receive 0. To check whether your code can pass compilation, use online GDB at least.
- Plagiarism will receive 0. Plagiarism can be (but not limited to)
o Copying from other students,
o Copying from internet,
o Providing copies,
o Hiring agents.
This assignment is not difficult. Be confident! You can work it out by yourself.
Implementation Structure
In your program, you need to implement three source files “mcs.c”, “lib.h”, and “lib.c” (“mcs.cpp”, “lib.h” and “lib.cpp” if you use C++).
For “mcs.c” (or “mcs.cpp”)
- It only contains the “main” function.
- It reads inputs from text files. The input text file is passed to the main function as an argument.
- For testing convenience purpose, text files are without “.txt” extension. But you can open them with text editors anyway.
- Each text file contains exactly one instance of MCS.
- The index of the array starts from 0.
For “lib.h” and “lib.c” (or “lib.h” and “lib.cpp”)
- .h is the header file for .c (or .cpp).
- They contain all other functions except “main”.
Functionality
- The input txt file contains the input array of integers as one line. Two integers are separated by a space “ ”. Negative integers start with the negative sign “-”. You can assume that the input file is robust. It does not contain any illegal integers or other symbols.
- When the calculation is finished, print the optimal value (sum of the MCS) and one optimal solution (start index and end index of the subarray) on separate lines on the screen. (The optimal value is unique, but the optimal solution may not.)
- Your program also writes the output (the optimal value and one optimal solution in the same format) to “xxx_out”, where “xxx” is the input txt file name. Again, please do not add any extension to output files.
Documentation
Other than implementation, each student also needs to submit a document, which contains
- the formal definition of the problem,
- the recurrence relation of your dynamic programming algorithm,
- definitions of the notations in your recurrence relation,
- pseudocode of your algorithm, and
- time cost analysis of your algorithm.
Submission
You need to pack all files in a package. Rename the package as COMP3023_24S_PA_XX and the document as XX_Description, where XX is your studend ID. Students who do not rename properly (the document or source files) will receive 10% off.
Bonus
Besides the basic requirements, students are encouraged to hunt for bonus. Each bonus is worth 5% of the total marks for this programming assignment.
- Documentation: Write the documentation in markdown files or LaTeX. All notations, equations, and pseudo code should be in correct environments.
- Functionality: Output all optimal solutions (both on the screen and to the output file).
- Functionality: The number of integers from the input is unknown. So, you cannot assume the maximum length of the input array. Thus, to read an arbitrary length array, you need to use dynamic memory allocation. The time cost of reading the input needs to be in 
.
If you implement any functionality bonus, you need to describe them in your documentation.
Sample
In the folder “Sample”, you will find all the source files described above. Take the C version in subfolder “c” for example (the C++ version is in subfolder “c++”). Currently, all source files are empty. The main function simple prints the argument on the screen. “lib.c” only tests the linkage. The package also contains “make.bat”. You can open it by a TXT editor. Then, you can see the compilation commands.
After executing “make.bat”, you will have “mcs.exe”. (Note that .bat files are only executable in Windows. For Mac users, you can directly type in the commands or create your own makefile. The extension for executable files is different in Mac OS.)
Next, if try to execute the sample code on the input file “in”, it will give you the following.
Example instance
Suppose the input file contains
The output should be
Because
