COMP3023 Design and Analysis of Algorithms
Spring 2025
Programming Assignment
Problem Description
Let be a directed acyclic (no cycle) graph, be a vertex weight function (positive weights are given to vertices, not edges), and be two vertices. A path from to is maximum if
1. is a simple path (no vertex is repeated twice);
2.the weight of the path is maximized.
For example, in the graph below, the weight of each vertex is the number next to the vertex name.
The maximum path from to is because there are 3 different simple paths:
- and
- and
- and
and is maximum.
Design and implement a dynamic programming algorithm to find the maximum path from to .
Implementation Requirement
1.Your program should be implemented in C or Java with only standard library.
2.The package COMP3023_25S_PA.zip contains following files.
a.PA.c or PA.java – the source code file, where you implement your algorithm (currently empty);
b.make.bat – a windows bat file (cannot be used in linux or MacOS), which contains building instructions; and
c.in – an example of an input file name (without file extension).
3.Your program will be executed with an argument, which specifies the input file name. For example, if your code is written in C, your program will be executed by PA.exe in. If it is in Java, then java PA in.
4.The format of an input file is as follows.
a.The first line contains only one positive integer – the number of vertices.
b.The second line contains two integers and , where is the start and is the end.
c.The second line contains positive integers separated by white spaces – the value of each vertex.
d.Line 3 to Line present an 0-1 matrix – the adjacency matrix of the graph. Two entries are separated by a white space. If row column has value 1, the edge is from vertex to vertex .
e.You can assume that all input files are in the correct format.
For example, the above graph is presented in the file in as
4
0 3
3 2 1 4
0 1 1 1
0 0 0 1
0 0 0 1
0 0 0 0
5.An output files should be as follows.
a.The file name is xxx_out, where xxx is the input file name.
b.The first line has one integer – the weight of the maximum path.
c.The second line has a sequence of vertices – the vertices on the maximum path. Vertices are named by a natural number (starting from ).
For example, the expected output of the above input is in the file in_out as
9
0 1 3
Vertex , , and are named as , , and respectively.
Submission Requirement
You only need to submit PA.c or PA.java to iSpace. Please DO NOT RENAME. You should write your name and ID on the first row of your code as a comment.
Marking
-5% - submission
-5% - compilation
-90% - test cases
Penalty
-capped at 5% for compilation failure by any reason (errors, wrong file name, etc.)
-10% off for no student name and ID in the source file
-0% for late submission
-0% for BOTH copying and copied
-0% for LLM or assignment agent
Bonus
-Programs will be ranked by their running time.
-Top 1% will receive 3% bonus.
-Top 5% will receive 2% bonus.
-Top 10% will receive 1% bonus.
