BAP Project Deliverables, (CS5234, SoC, NUS)

BAP Project Deliverables

What You Have to Do

In this project, you will implement at least two (algorithmic) solutions to the BAP partitioning problem. Specifically, you will design and implement

(a) a basic greedy constructive algorithm (which will be assigned to you), and
(b) an improved algorithm (of your choice and invention).

For option (b), try to come up with heuristic algorithms, or implement branch and bound to solve smaller instances exactly.

There is a lot of literature on the graph partitioning problem and the quadratic assignment problem, so these would suggest a number of possible approaches for BAP partitioning. However, there are significant differences between the BAP partitioning problem and these two problems, so it will be necessary to make appropriate adjustments or invent new algorithms.

Your Assigned Greedy Constructive Algorithm

Check here for your assigned algorithm and also brief descriptions of the greedy algorithms.
***Added: 15-Oct-2002***
(Note that the assigned greedy algorithms are NOT meant to find you good solutions, but rather get you started on coding a BAP partitioner. So, do not be alarmed if the quality of the solution is not good -- it is not expected to be. You are supposed to design an improved algorithm for the BAP partitioning problem -- which may include some combination of good heuristics and some search or any other algorithm you can think of.)

What to Submit

By the due date of the project, you should have

posted all your results to your Personal Score Page
submitted a hard-copy of your project report to me
submitted soft copy of your program(s) and project report (by email to us)

(Note: We are considering implementing an online submission of soft copies of your program(s) and report. Will keep you informed.)

BAP Report Format

Your BAP Project Report should have (at least) the following sections:

No:	Section Name	Description
1.	Problem Statement	Explain the BAP partitioning problem.
2.	Overview Of Solution	Explain the general idea behind your algorithm(s). (Illustrate with example(s).) This is an important part of the report.
3.	Correctness	Analyse the correctness of your algorithm. This is an important part of the report.
4.	Complexity Analysis	Analyse the complexity of your algorithm.
5.	Result and Observations	Results obtained by your algorithm, and Some Key observations, and possible reasons

BAP Project Deliverables,
Comb and Graph Algorithms