(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.

- max-flow min-cut theorem
- 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)

- 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.

- 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 there.
- 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 audience questions).
- 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.

Course Home