BAP Project: Tasks and Deliverables
CS3233, Fall 2005


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

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 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.)


What to Submit

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


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.
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,
CS3233