Graph-Theoretic Algorithms Spring 2020 Delivery

Resources

Outline

Summaries

Project

Exams

Delivery

The class will be completely delivered online, through a mix of PDF-notes and videos. The LEARN page (under "Content") gives you, for each lecture, a number components to work through. (Students that are not registered but want to "sit in": Contact the instructor for direct links to videos/notes, but they will not be structured as nicely.)

• A few pages (typically around 15) of lecture notes. These are being posted on Perusall, a web page that permits group-annotations on PDF-files. (You can read them there directly, or you should be able to download them as PDF from their web site.)

  If you have questions, please mark them as annotations directly at Perusall; I will be monitoring the annotations and clarify (possibly in the next online meeting) as needed.

• A few (typically 4-5) videos that in total should be at most 30 minutes. These cover the same material as the lecture notes, but omit all the trivial or notation-heavy parts and instead focus on the pictures and walk through the examples.

  If you understood everything from the next then you could skip the videos. But I recommend watching them anyway.

  The videos are .webm files which most built-in video players should be able to read (but I am told that some Mac video players had trouble). If need be, install VLC. Here is a small sample video to try it out.

• Scans (as many as videos) of the pages used during the videos.

  You can usually ignore these. They are here because the video is sometimes blurry so that you can't see exactly what was written. And sometimes the pages in the video are not quite what was in the lecture notes (due to later improvements of those lecture notes) . So perhaps you find these useful.

• A few (typically 3) quiz-questions. These should be completely trivial once you read the notes / watched the videos. Answers should be short (at most 2 sentences) and uploaded to the Dropbox on LEARN. For pictures, photos of handdrawn pictures are perfectly acceptable.

  The deadline for these is the day after the corresponding lecture-date. It should only take a few minutes to do them, so do them as soon as you have read/watched!

• One assignment-question. These may require deeper thinking, creativity, mulling over what you have seen. The questions are not completely in sync with the lectures; sometimes you should look for earlier/later lectures for inspiration.

  Upload the answer (preferably in latex in PDF) to the Dropbox on LEARN. Note that latex can easily include photos of handdrawn pictures, and this is acceptable to use. Do not skimp on pictures; they really help me understand what you mean.

  The deadline is 2 weeks after the corresponding lecture-date.

  A few meta-comments that apply to all quizzes/assignments:

  • Graphs by default are simple, connected and n≥3 (or any other small constant number, as needed). For assignments, think about what happens if these assumptions are violated, e.g. write “note that I used here that the graph is simple” if appropriate.
  • For “prove or disprove” questions, the answer often is “true if X holds but false otherwise”. If so, then state exactly what assumption you make. Giving multiple answers (depending on what holds) is a good idea.
  • You are allowed to use any theorem that was mentioned in class, even if its proof was omitted.
  • I am posting questions for quizzes and assignments on perusall as well. Clarification-questions that don't give any hints could be placed there; for any other questions about them email me.
  • Since some students are studying while abroad, all due dates are in the time zone "AoE". This means "anywhere on earth", so submit by the submission date in your local time zone and you will be fine.

• I will hold virtual office hours twice a week (WF 3:30pm) through LEARN (Connect->Virtual Classroom).

  No new material is covered here (and they are completely optional). If there are no student-questions, then I do tutorial-style things, perhaps go over the lecture notes pages again, or answer some of the reinforcement-questions from the lecture notes. In later office hours, I might also go over the solutions to assignment-questions.

• I will upload complete lecture notes once in a while, so that you can see the overall flow and/or read parts that were not covered in the lecture but that you are interested in.

• Disclaimer: Making videos is very time-consuming. I have neither the time nor the expertise to make these into really nice videos. Expect pauses, "umm", blurriness, ... Apologies but with fairly little advance notice and severely limited available equipment, this is the best that I could do. (Further random thoughts of mine on this here.)

• Disclaimer: I am very new to LEARN and undoubtedly some links will not work as expected. Contact me if something is amiss.

• The split of the topics into lectures is done roughly to how it was in Spring 2017 (see the table below), so that we cover approximately the right amount of material.

  As you can tell, the course will run on a somewhat condensed schedule (each lecture will be equivalent to about 2 hours class time). Unless we are on a complete lockdown, I will be away (with very limited internet access) from mid-July to early August.

Webmaster: