CPTS 553 Graph Theory Project Assignment solution




5/5 - (4 votes)

All students will be required to write a 5 to 10 page (these are single-spaced requirements-at this level, a
well thought-out narrative should easily take 5 single-spaced pages) narrative project, followed by
references (please, not all Wikipedia) on any topic related to the course, to be turned in during closed
week. The project is to be typeset using LaTEX, MSWord’s Equation Editor, or other STEM professionallooking typesetting software. There must be mathematical content (equations, proofs, that sort of
thing; the final product should “look technical”) but students are not expected to prove original results
in their write-ups.
A suggested outline:
I. Introduce the topic, providing historical context and motivation, i.e., “why did someone
II. Notation, Definitions, Technical Background
III. Development of results concerning the main topic
IV. Observations, implications, tangential consequences, i.e., where has this topic led to or what
has this topic influenced?
V. The current state-of-the-art and future directions, i.e., where is this topic now and where do
people see it going?
Popular topics include applications of various families of graphs (fancy sorts of trees are *very* popular);
vertex- or edge-coloring algorithms or heuristics; graph drawing algorithms; graph-based efficient
storing, searching, or sorting techniques; network flows (max-flow min-cut problems); tournament
ranking schemes.
Alternatively, students may choose to construct a “graph theorist’s sketchpad” application that mimics
but expands on the sketcher I wrote and use for in-class examples. If you take this route, I will expect
you to demonstrate it via screen sharing during office hours toward the end of the semester or during
the scheduled final exam period for this course (consult the official WSU Registrar final exam schedule.)
Also, you must provide a short (3 to 5 page) narrative of your application’s features and how you
implemented your routines.
Finally, math 553 students are expected to prepare a 15-20 slide lecture (in power point form or the
equivalent) on their project topic. Given the large and geographically diverse enrollment in this course,
these lectures will not be presented.
The final write-ups are due at 5:00 on Thursday, December 17th. Demonstrations of sketchpad
applications during finals week will take place during the 10:00-1:00 exam block on Tuesday, December