(Graph Theory and Social Networks)
- 4/11: Turn in sheet of paper with your name,
which section you are enrolled in, and your topic choice
- 4/25: Turn in outline/draft to me in class
- Th 5/8 (8am, PHSC 230): Turn in final project; grad student presentations
(10-12 min each)
For your project, you will choose a topic and clear it with me.
The project is due at the end of the semester (and students enrolled
in the graduate section will also do brief presentations), however
you must also turn in a project outline/draft later in April.
This outline/draft should clearly state the details of what you plan
to do for your final project so I can let you know whether it is
acceptable or not and make suggestions.
Roughly, you are expected to learn and explain some topic related to
but not contained in the rest of the course, and there should be come
coding aspect to your project (computing examples, coding algorithms,
etc) in Python/Sage. The project must be typed. There are no
fixed page requirements, but I roughly expect 6-8 pages for undergrad
projects and 8-12 pages for grad projects, not counting attached
code and computer input/output.
More details will be given later. For now, let me just start listing
some possible project ideas. More ideas will be listed as we
progres in the course, and you do not need to restrict yourself
to this list.
- Routing problems (e.g. Hamiltonian paths, travelling salesman problem)
- Graph colorings (4-color theorem, chromatic polynomial)
- Topological graph theory (for those with some topology background)
- Ranking algorithms (like Google's PageRank)
- Graph partitioning (like the Karate club)
- Diffusion through networks (e.g., modeling spread of disease)
- Other random network models
- Strategic network formation (e.g., optimizing your position in a network)
Project report suggestions
Here are some suggestions to keep in mind for your project report.
Let me emphasize that these are not rules, but guidelines to help you figure
out how to structure your report.
- Your project should have, as much as possible, a unified thesis/topic.
Start with an introduction that explains the motivating problem behind
this topic, and say what you will do in the project. Have a body
that explains the project, and then end with conclusions/final remarks.
- Explain, as precisely as possible, relevant background definitions
and results. If this is reasonable for your project topic, include
proofs of some of the key results, or a sketch of the ideas if the
actual proofs are rather involved. Give references (books/papers,
not Wikipedia or some random guy's webpage if possible). In math,
references are usually given at the end (as endnotes).
- Explain what you did in terms of coding and summarize your results.
It is probably easiest if most of your code/computer output is included
as an appendix at the end.
Here are some friendly suggestions to help make a good presentations, which
should also help make you more comfortable when you present. And don't
worry---I'm not grading you on style, but on content: did you prepare?
did you learn something? do you have any idea what you're talking about?
If so, you should get full credit.
- Make slides using LaTeX with Beamer or Powerpoint.
- Have a title slide with a poignant title and your name.
- Each slide should be easy to read: generous font size, highlight
main ideas, and illustrative pictures are always nice.
- You don't need to talk about everything you did for your project
in your presentation. In fact, you shouldn't have time for this. Focus
on the most interesting/important aspects.
- You're presentation should have 1 or 2 main points. For most topics, it's
suitable to start with a motivating question, which you will at least
partially answer by the end. Emphasize the problem at the beginning, and
the answer at the end. Some speakers outline their talk in advance so the
audience knows where they're going, but it's probably unnecessary for a
10 minute presentation.
(This structure is similar to what I expect for a write-up.)
- Do you enjoy teachers who just read out of the book? If not, don't just
read your slides word for word either. Slides should
not be a transcript of what you're going to say, but visual
highlights/reminders to help the audience focus on and understand what
you're talking about.
- The audience for this presentation is your fellow students, not me.
Make it understandable for them, so they can learn something.
Your project write-up is directed to me, so you can say more advanced things
- Practice your talk at least 2-3 times, and time these.
The first time should be just
figure out exactly what you will say/how to explain things and get a general
sense of your timing. Then edit things in or out if you need to, and
try timing it again.
Repeat until you're confident you can finish in time (10-12 minutes, without
- Anticipate likely questions from the audience so you can prepare
anwsers and sound like a genius when you answer them skillfully. Or
pre-emptively answer them in your presentation.
- Did I say make sure you can finish in time? A minute over is forgivable.
Five is not. Keep an eye on the clock, and figure out how to shortcut to your
thrilling conclusion if you are running short on time.
- Thank your audience at the end.