In this project, you will implement at least two (algorithmic) solutions to the BAP partitioning problem. Specifically, you will design and implement
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.
Check here for your assigned greedy algorithm. The document also also give a brief description of the greedy algorithms.
(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.)
For Phase 1: By the due date (13-Oct-2005), you should have submitted to the CS3233 Workbin, a soft copy of your partitioner code (only the .h and .cpp of your greedy partitioner, not the whole program).
For Phase 2: By the due date (03-Nov-2005), you should have
Your BAP Project Report should have (at least) the following sections:
| No: | Section Name | Description |
| Problem Statement | Explain the BAP partitioning problem. | |
| Overview Of Solution | Explain the general idea behind your algorithm(s).
(Illustrate with example(s).)
This is an important part of the report. |
|
| Complexity Analysis | Analyse the complexity of your algorithm. | |
| Result and Observations |
Results obtained by your algorithm, and
Some Key observations, and possible reasons |