Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

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.