For context, these are some things I learned in the process of putting together and delivering a guest lecture to a first-year discrete math course last summer. The talk was about the research I was doing at the time, and I was allotted about half an hour for the presentation. Again, I meant to write and post this last year, but clearly that didn’t happen.

Here is a long list of sources I consulted at various points while doing research for this project. As it might have become clear through reading the previous installments of this series, this was more a talk about the densest subgraph problem than it was about theory being useful in computer science. There are a few reasons for that, which I might explain in more detail at some point in the future. This means that I presented a lot of information that I borrowed from other people! Here’s an annotated bibliography of sorts, in case you were interested in going deeper, for whatever reason.

In Part 3, we discussed the densest subgraph problem (DSP) and some algorithms for solving it. In this section, we’ll be looking at how we can generalize this problem and those algorithms to solve some other problems. This is the part of the talk where I will introduce some fancy new math I had to learn in order to understand how one might generalize iterative peeling to solve adjacent problems.

In Part 2 of this talk, we gave a crash course to graph theory and showed how we can use it to view some real-world problems as instances of the densest subgraph problem (DSP). But what exactly is the DSP? If you’ve studied graph theory, you may have heard of something called the Maximum Clique Problem. The goal of the max clique problem is to find the largest complete subgraph in a graph. If we consider our vertices to be people, and edges to represent a friendship relationship between two people, in the max clique problem we are trying to find the largest friend group in a community.

This page was last updated on February 9, 2025.

What is COMP 1805? Is it math or programming?

COMP 1805 involves no programming, though at times reading pseudocode may be involved. It is very explicitly a math course, though it’s probably not the math you are used to doing in high school. Whereas high school math courses teach you techniques for doing different sorts of calculations and algebraic manipulations, there are close to no calculations in COMP 1805. Instead, the course is about learning the language used by computer scientists and mathematicians to describe problems more formally (which in turn, makes it easier to decide whether or not a problem has been “solved”). Topics covered in COMP 1805 include “foundations of math and reasoning” such as propositional logic, basic set theory, functions and relations on sets, and proof techniques, as well as topics intended for computer scientists, such as an introduction to graphs and networks, Big O notation, and asymptotic analysis of algorithms.