COMP 572 Project -- Fall 2007

There are 4 different possible projects (you may also suggest something not on the list).  Projects 2-4  come in different variations. Each project/variation indicates the maximum size of a group that can work on that project/variation. Click on individual projects for more details. All programs should be written using languages/packages that are "normally" available on either our department Windows or Solaris machines.  When registering your project (see below),  you should indicate what languages/packages you will be using. We will contact you if there is a problem.

If you have any questions concerning the project please send email to the TA at qinzhang@cse.ust.hk  or me at golin@cs.ust.hk. Answers to questions of general interest will be posted on the  PROJECT FAQ

A list of who is registered for which project is available here.

1. Fibonacci Heaps (2 people)
   Implementing  Fibonacci heap algorithm and an animation that shows how the data-structure looks and changes
    
2. Max Flow   Test Cases
   • A: (1 person) Implement Ford-Fulkerson algorithm
   • B:  (2 person) Implement part (A) and a graphical user interface (GUI) for the FF algorithm
   • C:  (3 person) Implement  part (B) along with another GUI that implements Max-Cardinality matching of Bipartite graphs
      
3. Max-Bipartite Weighted Matching   Test Cases
   • A: (1 person)  Implement Hungarian algorithm
   • B: (2 person)  Implement part (A) and a GUI for the Hungarian Algorithm
      
4. Simplex  Test Cases
   • A: (1 person) implement the simplex algorithm
   • B: (2 person) implement part (A) and a GUI for simplex showing tableaus
   • C: (3 person) implement part (B) and, for n-m=2, draws 2D polygon and shows correspondence of tableaus and polygon
   • D: (3 person) implements part (B) and another GUI that allows entering a max-flow problem and then uses simplex to solve max flow.
      
5. Suggest your own project.
   Please come to see me if you would like to suggest a project not on the list.

Important Deadlines

• Friday, November 23, 2007. By this date you should email qinzhang@cse.ust.hk,  registering your project.  You should tell him (i) which project/variation you will be doing and (ii) the students in your group.  Your email should also (iii)  indicate what languages/packages your code will be written in (if you change your plans later, please send an update email). Only one group member should send the email, with the message being cc'd to all other group members.
   
• Friday, Dec 7, 2007 at 4PM.  Project source code due (both hard and soft copies required)
  1. Hard Copy should be submitted at box in dept admin office on  Dec 7, 2007 before 4PM
     Hard copy can also be given to instructor at last class on Dec 6, 2007
  2. Soft copy should be emailed to qinzhang@cse.ust.hk before 4PM on Dec 7, 2007
     See here for softcopy format instructions
      
• Tuesday-Thursday, Dec 11-13, 2007: Individual group meetings to demonstrate project.
  Only groups that write GUIs must demo their projects.  We will post a demo schedule closer to the date.

Important Details

In your submitted code, the part that implements the algorithm(s)  must be fully and clearly documented so that the marker can read it and understand what each part of the algorithm is doing (and is able to map it to the algorithm)  The GUI does not have to be as fully documented.

All work must be done by your group. That is, no sharing of code between groups is allowed.  All algorithmic code, e.g., the implementations of simplex, the Hungarian algorithm etc., must be written by your group.  With that said,  you may use any off -the-shelf GUI software you find (as long as it has not been developed by any other class group).  In particular,  if you can find good GUIs for implementing basic graph editing (needed for many of the projects) you may  use them.

This page was released on November 2, 2007 and last revised on 11/22/2007 18:59 +0800