MO412 / MC908 - Graph Algorithms

Overview

This is a course on Graph Algorithms, with emphasis in Network Science. We will cover a few celebrated graph algorithms interspersed with chapters from Barabási's book.

We will have regular, face-to-face lectures this term. In a typical class, the instructor will start by showing a short presentation on the topic of the day, followed by discussions, and usually a review of related exercises from various sources. Students are encouraged to share their views and impressions. Some classes will have special events, such as student presentations, hands-on classes, exams, etc.

We have a lot of ground to cover in one semester. We know that Unicamp students have to deal with a heavy class load. To be able to fulfill your commitments, it is essential to be thoroughly organized. We estimate that a student will have to devote around 12 hours per week to this course, including time for reading, attending classes, and doing assignments.

Office hours

By appointment only.

Schedule

Below you will find a schedule for the semester containing the topics to be covered in each class, as well as the corresponding book chapter or other supporting resource. We may have to change class topics occasionally, due to unforeseen circumstances, but we expect the course to closely follow this schedule for the most part.

Grading

Grading will be based on a number of Assignments, including contributions to the Quiz Blog, a Quiz, and a Final Project. The Assignments and the Quiz are individual, but the Final Project is to be carried out by groups of 2 students, preferably with different backgrounds. If the number of students in the class is odd, we will allow one group with 3 members. In the Final Project, each group will select a network of interest, map it out, and analyze it.

The Quiz will be an exam with multiple choice questions created by MO412 students, including students from this offering, some of them edited by the instructor, collected in our Official Quiz Blog. Almost every week (see schedule), people have to submit a quiz question on the week's topics, usually on Fridays. People who successfully contribute to the Blog will earn extra points. People who fail to submit a question will be penalized.

The Assignments are homework problems assigned weekly by the instructor. These will sometimes be programming exercises. They are typically assigned on a Thursday after class and are due on the following Tuesday by noon.

For the Final Project, the groups must present their work as a 10-minute presentation, describing the data, how it was collected, basic characteristics of the network, and insights gained by doing the analysis. There will be midterm Preliminary Project Presentations where groups will present their network, how they will collect it, and relevant questions about it, in 5-minute presentations, based on no more than 5 slides. After the preliminary presentation, up until the final presentation, each group will meet weekly with the instructor for project guidance. Further guidelines about the Assignments / Final Project will be given during the course.

Each type of assignment will give rise to a numeric grade in the range 0 to 10. The contributions of each assignment type to the final grade are as follows:

Numeric grades will be converted to letter grades accorging to the following scheme:

Late penalties

For any of the Assignments, there will be penalties for late work. People who do not hand in their solutions on time will incur a late penalty of 20% of the grade per day, computed proportionally, with the granularity of 1 minute. So you are 1 day late your penalty is 20%; 2 days late, 40%; 1 hour late, 0.833%; and so on.

Fraud

Any attempt at fraud in this course will entail final grade equal to zero for all involved, with possible additional sanctions, as deemed necessary by the University administration.

References

Network Science. Albert-László Barabási. Cambridge University Press, 2016.

Introduction to Algorithms, 3rd Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. The MIT Press, 2009.

Algorithms, 4th Edition. Robert Sedgewick, Kevin Wayne. Addison-Wesley Professional, 2011.

Credits

Network Icon from PNGFLY.