CS5234 - Combinatorial and Graph Algorithms
School of Computing, National University of Singapore
(Spring 2007)

Course Project

1. About Your Project

For your course project, you can do one of the following:
(a) design and implementation of BAP Algorithm
(b) design and implementation of algorithms to your "algorithms problem", and
(a) survey of an algorithms problem,

Your Project Choices: click here.

Deadlines

Stage 1: Proposal of Topic (Due: 26-Feb-2007)

You need to write a short (1-2 page) proposal for your chosen topic.
If you choose (a), write about what kind of approach you would like to try out for BAP Partitioning.
If you choose (b) or (c), write about the algorithmic problem you propose to study/survey and why you like to the problem, and how it is related to your current/planned research, and what you know about this problem. For (b), you should aso write about the algorithmic approach you would like to try out for this problem. For (c), you should give a list of papers (at least 2-3) that you plan to study in-depth for this problem.

Stage 2: Confirmation of Topic (28-Feb-2007)

I will confirm your topic with you by this date -- so you can start with your project.

Stage 3: Project Deliverables Due (3-Apr-2007 12-April-2007)

All project deliverables are due by this extended date.

The Details

For now, I give a quick summary of your project. More details on this will come later.

BAP Algorithm Implementation

For the LEDA assignment 2 (coming out soon), you will be implementing a simple heuristic for BAP partitioning. In this project, you will research and implement a more advanced algorithm for BAP partitioning. Your final deliverable will be a report on your algorithmic solution to BAP partitioing.

Implementation of Algorithms for Your Problem

In this project, you are expected to choose an algorithmic problem and do a quick survey of some approaches to the problem and then design and implement your own algorithm for solving the problem. Your final deliverable will be a report on your solution to the chosen algorithmic problem.

Survey on An Algorithmic Problem

In this project, you are expected to choose an algorithmic problem and do a survey of some (at least 2-3) state of the art research papers on the problem. Your final deliverable will be (a) a survey report of your algorithmic problem, and (b) a 30 min. presentation on the problem based on your survey report.

Delivarables for your Project and Submission -- NEW!!

For (A and B), your deliverables should include source code, object code, results of your runs on the various dataset, the relevant reference papers, the report you write for the project. (For (A), I am putting up a challenge web-site for you to compare your results. More info coming in one or two days. Sorry for the delay.)

For (C), your deliverables should include the relevant reference papers, the presentation slides, and the survery report you write for the project.

Please put all the deliverables for your project in one folder/directory and zip it up into a file called CS5234-Proj-.zip and submit it to the workbin called "CS5234 Project".

CS5234 Projects Page
CS5234 Home Page