COMP 572 Project -- Fall 2004
There are 4 different possible projects. 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 cszz@cs.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 maintained
here.
A list of the project demo times is maintained
here.
- Fibonacci Heaps (2 people)
Implementing Fibonacci heap algorithm and an animation that shows how
the data-structure looks and changes
- 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
- 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
- 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.
Important Deadlines
- Monday, November 22, 2004.
By this date you should email cszz@cs.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.
- Wednesday, Dec 8, 2004 at 1PM.
Project source code due.
- Hard Copy should be submitted at box in dept admin office on Dec
8, 2004 before 12:45PM
Hard copy can also be given to instructor at last class on Dec 7, 2004
- Soft copy should be emailed to
cszz@cs.ust.hk before 1PM on Dec 8, 2004
See here for softcopy format instructions
- Wednesday-Friday, Dec 8-10, 2004:
Individual group meetings to demonstrate project.
Originally we intended all groups to demo their projects. Since most
students are not writing GUIS we have decided to cancel the general GUI
requirement. Instead, only the small number of students/groups who are
writing GUIs need to demo.
- Only read this if your project has a GUI
- If your project has a GUI you must DEMO it
- Demos will be Wednesday Dec 8, from 2-4:30PM in the instructor's office.
Demo slots will start on the quarter hour and last 15 minutes, e.g.,
2PM, 2:15PM,...., 4PM, 4:15PM.
- A list of the currently scheduled and available project demo times is
available here.
- To reserve a demo time send email to
golin@cs.ust.hk before 1PM on Dec 6, 2004 with your first and second
choices of preferred demo time. You will receive confirmation of your demo
time before class on Dec 8, 2004.
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 19, 2004 and last
revised on
12/07/2004 00:42 +0800