Recent
news items :
Assignment 5: “Graph 3-Coloring” or “SkipLists” or “SomethingElse”
Tuesday, November 12, 2002
Due: Tuesday, December 3, 2002
Previous page
|
Next page
Your choice ...
Choose one of the three options.
A chance for fame and fortune ...
The best three demos shown in class,
as decided by a vote of the audience,
will get book prizes.
Anyone who does a textbook-quality implementation
of a novel demo will be exempt from the final exam.
Files to submit
Submit a single file named assign5. To create that
file, have in a directory all the files it takes to compile and
run your program, including
a makefile that lets the user compile and run your program
by typing make run.
Do not have any .o files nor any executables.
Then do
This creates the file you then submit.
Graph 3-Coloring
Description
Implement a demo of a “graph 3-coloring” algorithm.
Graph 3-coloring is the task of coloring each
node of the graph either red, green, or blue
with the constraint that the two endpoints of any
edge must get different colors. If that is not
possible then the number of edges where both endpoints
have the same color (the number of “violations”)
should be as small as possible.
Details
Graphs are discussed in Chapter 15 of our textbook.
Generate the graphs randomly in such a way
that edges never cross. Let the user choose
how many nodes and how many edges
there should be. Do a pointer-based implementation,
not an “adjacency matrix” (= two-dimensional array).
Provide a menu option that shows the user a brief
description of the algorithm, e.g., “For every edge,
the colors of its endpoints get changed if that decreases the
total number of violations, until no such improvement step
is possible anymore”.
A note of caution
It is not important that your algorithm
always find an optimal coloring.
Just implement some algorithm that does work on many
graphs and that can be easily described in words.
Generating graphs randomly is not the least part of this
project.
SkipLists
Description
Produce an interactive demo that helps people
understand SkipLists.
Details
You need to implement SkipLists and you need
to provide a main program that lets the user
try out insertions and deletions.
The lists need to be drawn in a graphics window.
How to get started
-
Get a basic doubly-linked list to work.
This you can scavenge from Assignment 3 (the
“CatalogBrowser”).
-
Implement a main menu that lets the user add and
delete items.
-
Display your lists in a graphics window.
-
Change the node class so that nodes come not with
single pointers but with arrays of pointers.
-
Change the insertion and deletion operations to that
instead of working only at one level of pointers
they work at all levels.
SomethingElse
Description
Implement some other project of your
choice that makes use of the material covered in this course.
Details
If you choose this option email a brief description
of your project
to your TA by noon, Tuesday, November 19.
What you propose needs to be comparable in scope
to the SkipList or Graph 3-Coloring version of this assignment.
Previous page
|
Next page
|
Back to top
© 2002 Karl Winklmann
3:40 PM, Thursday, December 12, 2002