Graph-Theoretic Algorithms Spring 2024 Projects

Home

Outline

Resources

Schedule

Summaries

Assignments

Project

Final

Every student is required to do a project, which can be summarized as "be the teacher for one lecture". This means the following:

• Pick a fairly recent topic in the area of graph-theoretic algorithms. Some pointers are below, but selecting the actual material and finding and reading related literature is part of the project.
  
• Write lecture notes that explain the topic in detail, with lots of pictures.
• Record a video where you help the viewer understand the lecture notes more easily, typically by going over them and highlighting important parts.
  Two projects are different (let's call them presentation-projects): Here you do not have to record a video, but you must teach half a class, and the topic is more-or-less fixed by me.
• Have an 1-on-1 meeting with me where I ask you questions about your topic.

Topics

Topics that have been chosen

• Planar Graph Product Structure theorem.
• Parameterized complexity of dynamic problems.
• Approximating diameter in planar graphs.
• Steiner cuts in planar graphs.
• Matching in planar graphs.

Lecture notes

• Lecture notes should cover material that would fit into an 80-minute class, or as much as in one of the shorter chapters of the lecture notes (the chapters on cutwidth and separators are good examples). So aim for 6-8 pages (using those margins and fonts); more are ok if you have lots of pictures.
• Lecture notes should be easier to read than the original. You should provide lots of pictures and examples. For algorithms, it is strongly recommended to create a running example (ideally one that illustrates the various cases or difficulties that could arise). For complicated multi-case proofs, pick the most relevant situation(s) and explain this in great detail, then skip the other cases. For algorithms for constant treewidth, perhaps explain it only for treewidth 2 or 3.
• You must not copy from your references verbatim; rephrase everything in your own words. You are more than welcome to improve on your references if you see a simplification. Indicate (e.g. with a footnote) if there is a major part that you have developed yourself.
• You should tie your topic with the material that has been covered in class. E.g., if you are studying another graph class, say how it relates to graph classes that we have seen. If you study some width parameter, say whether it is larger/smaller/incomparable to the width parameters that we have seen.
  You should also use the same notations than what was used in class. (If you really want to use the notations from the paper instead, then at least point out in the notes what the corresponding notation from class was.)
• Break the topic down into easily understandable chunks. Group related topics into sections, break them down into subsections if appropriate. Clearly mark what the theorems and what the proofs are.
• Every step of what you write should be understandable to someone who has taken cs762. You need not (in fact, should not) define terms that we saw in class, except for perhaps a 1-sentence "Recall that...". On the other hand, obscure explanations (and in particular, an "it is obvious" when it isn't obvious) will reduce the grade.
• Motivate what you're doing. Giving the history of a topic (who did what when, in parallel with who?) is often entertaining, so if there is a colorful history, give it. If there are nice applications of your graph class/result, mention it. Relate your topic to what we've seen in class. Anything to excite the audience.
• Explain what you're doing. The good old suggestion "Say what you're going to do. Then do it. Then say what you just have done." applies. Every section (and most subsections) should start with a brief outline of what they contain. Most proofs benefit from first giving the overall idea of the proof, and then giving the nitty-gritty details.
• Pictures are really helpful. While you should avoid giving a definition only in a picture, it helps a lot to give the definition in the text and illustrate it in a picture. Similar holds for proof ideas. Pictures do not count towards the (loosely defined) page-limit, so do not skimp on pictures. Recall, they may be handdrawn and scanned/photographed.
• If you really can't figure out a step in your reference within a reasonable amount of time, then indicate in the lecture notes where the difficulty was. This will not be punished if the difficulty was beyond what can be expected.
• Be sure to include references to all sources you have used, and indicate which one(s) were your main references. Use full references (author, title, journal/conference-name, pages, year) and preferably include a DOI-link.
• Definitely use a spell checker, for example (under linux) "ispell filename.tex". Grammar errors are excusable (especially for non-native-speakers), as long as the meaning is clear. Spelling errors are not.

Videos:

• My recommendation would be to make the video an `annotation of the notes'. This means that you have your lecture notes in front of you, and you `walk through' them for the purpose of the reader, highlighting the important parts and perhaps adding further small examples. (In 2020 I taught cs762 via such videos; I can make selected videos of that available if you would like to see some examples.)
  There are other options if you'd rather not do an annotation of the nodes, e.g. you could create slides (more like a research presentation) or set up a camera that films you while you teach in a classroom (more like a real-life lecture). The choice is yours.
• Do not simply read out your notes. Instead, highlight the parts that are really important, and perhaps draw further examples. (On the other hand, straightforward-to-read parts of the notes, such as history or motivation, can probably be skipped.)
• Giving the nitty-gritty details of a proof in a time-restricted presentation is rarely helpful. Focus on the big picture, give the ideas of the proof (and perhaps do one illustrative case), but do not cover all details. The goal of the video should most be `engage the viewers so that they actually want to read the notes', not to give a complete proof.
• The presentation must be pre-recorded. Breaking it into multiple small pieces of (e.g. for easier downloading and viewing) is fine.
• The total viewing time should not exceed 30 minutes. This is not a rigid limit, but if you exceed it then the extra time had better been extremely helpful for understanding.
• It's the content that counts, not the quality of recording. While you should try to find a decent microphone (and camera if you don't use a screencast), I will not deduct for quality of video as long as it is understandable. Do not waste time on making fancy intros/transitions.

1-on-1 meeting:

• I will have read your lecture notes and watched your video. I may or may not have read parts of the relevant paper(s). If everything was perfectly clear to me, then the meeting will probably be quite short. But usually I'll have a few question or will ask for further explanation.
• You need not bring or prepare anything for the meeting. In particular, this is not a presentation; do not prepare slides. Some students find it helpful for answering questions to have their copy of the paper (with their annotations) or other study-notes that they created while preparing the project report.
• The 1-on-1 meeting will be evaluated primarily based on your ability to answer questions about your topic. Be ready to justify any claim in your lecture notes in detail, or clarify things by giving a different example. I may also ask about why you didn't include some parts of the paper(s).
• The 1-on-1 meetings may well be combined with the final, especially if I do not have a lot of questions. If you don't hear from me within a few days of the submission deadline, then assume that no separate meeting is needed.

Evaluation

Material selection is also a criterion. How well did you relate your topic to cs762 material? Did you give a well-rounded picture of what is known in this area, before going into the details for some of the results? Did you choose material at approximately the right level for cs762 students? Making your project super-easy to understand by covering only trivialities will lead to deduction. Excessive overlength may also lead to deduction.

Quality of presentation is also quite important, especially for the lecture notes. Videos will be evaluated on content only, and not on the quality of the technology used to deliver it (as long as it is usable).

Technicalities:

• Late submissions are accepted, but every day of delay leads to 10 fewer points (out of 100) on the grade.
• Lecture notes should be LaTeX. Talk to me if this poses a significant problem. Pictures may be scans or photos of handdrawings. Pictures must not rely on color (I will likely read a black-and-white printout.)
• Submit a PDF-file with your notes, as well as PDF-files of your main references (typically 1-2 papers).
• Videos should be a .mp4 or .webm file, though I am willing to accept other formats if you check beforehand with me that my computer can process it.
• Submit your files in the "Dropbox" region of assessments on the Learn web page for cs762. If you have trouble uploading your video, try uploading a link to a webpage that has the video instead. If all else fails, email me a link to where the video can be found. (Do not email me the video directly; my email inbox will crash.)
• Projects can be done in groups of up to 3 people, but groups of X people should result in lecture notes/videos that cover X times as much material.
• You are allowed to collaborate on this project, even with fellow students that aren't project partners. I recommend exchanging lecture notes with each other and critiquing, but will not coordinate this. Acknowledge any help that you have received in the lecture notes.
• I reserve the right to use part of your lecture notes in future versions of the cs762 lecture notes (with an acknowledgments to you in the intro).