BAP Project (Details), (CS5234, SoC, NUS)

Details of the BAP Project

Here are some project details for students in CS5234.

Working Individually

You must work individually. If you need to discuss, you should limit your discussion only to general approaches, and not on the detailed implementation of algorithms/techniques.

Submitting Your Results

BAP Challenge Site: We have a BAP Challenge Website that publishes the best solutions obtained by the students.

Personal Score Page: Each student will have a "Personal Score Page" that tracks your own BAP partitioning results. You must post your results to your "Personal Score Page" -- as we will be also grading based on the results on your "Personal Score Page". If you are user "leonghw", your personal page is at
http://www-appn.comp.nus.edu.sg/~cs5234/cgi-bin/2002/bap-results.cgi?personal=leonghw.
(Click on this page and type in your own user-id to replace "leonghw". Note that we use your SoC userid, ie [user-id]@comp.nus.edu.sg, not the one from [something]@nus.edu.sg.)

After you finish your first project milestone, you should start submitting your solutions to the general BAP Challenge Website that tracks the best result for each problem instance.

If you like, you can also see the (2001) TTP Challenge Web-site that contains the best tours obtained by last year's class for a different problem, the Travelling Tourist Problem (TTP).

Note: If you have problem accessing this link, please verify first that you have set your proxy preference to "bypass proxy for domain www-appn.comp.nus.edu.sg" before you send an enquiry to Li Shuai Cheng.

Some Intermediate Milestones (IMPORTANT!)

There are three intermediate milestones,

M1: Greedy Algorithm Ready -- by 17-Oct-2002
Some marks may be assigned to this milestone. We will grade this part after 17-Oct-2002.
For M1, you will need to do the following:

submit your code for Greedy Algorithm, and
post solutions (using your Greedy Algorithm) on your Personal Score Page.

To submit your code, please read instructions on submitting your code. (*Note: This is closed!*)

M2: Idea for Improved Algorithm Ready -- by 28-Oct-2002
For this milestone, you should have -- discussed with me or submitted to me -- your idea(s) for improving the algorithm to get better results. There is no need to submit any code for M2.

M3: Final Code and Report -- by ~~04-Nov-2002~~ 05-Nov-2002 (because of Deepavali holidays)
*** Added: 05-Nov-2002 Start ***
You will need to do the following:

Run your improved program on all the datasets and submit your best solutions to your own "Personal Score Page". Check details here
Submit your code for M3 -- read instructions here
Your Final Report --
Email me the soft copy and hand in hard copy to my office.
Please discuss the results you obtained and draw any conclusions and/or give explanations for the behaviour. or explanation

*** Added: 05-Nov-2002 End ***

Some Friendly Advice

Start Immediately: It pays to start thinking about the problem right away even though the deadline is still some time away. The first thing to do is to look through the slides on BAP to get a good understanding of the domain. Then look through the source code given to you to grasp the organization of the BAP code, especially the BAP Package Class and the Trivial Partitioner.
Get Greedy Done: The idea is to quickly get a basic working code of your assigned greedy algorithm -- have it designed, implemented, and tested. Then try to publish your initial results on your Personal Score Page.
Improved Algorithm: Once you have coded Greedy, you will be more effective in coding up improved algorithms. So, you can work on improving the algorithm to get better results. This may take quite a bit of trial and error.
Keep a log of your work on this project throughout this period. When you have ideas or algorithms, write a summary of it and record the results. Negative results are also worth reporting -- lots of good ideas don't work out. If you keep a fairly complete log of your work, then it should be easy to convert it to your final project report.

Where to get help...

First, check out this page on getting help. If that does give the answer to your problem, you can send email to my former student, Mr Li Shuai Cheng for help (with cc to me).

Details of BAP Project (Sept 2002)