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.

A while ago, someone in a Discord server I’m in asked how much of the math behind a system you need to know to implement it. I thought it was an interesting question, and I felt qualified to answer it, so I ended up writing quite a lengthy response. It just occurred to me that it might also be useful to other people, so I thought I would clean it up a little bit and archive it here.

In the first part of this talk, I made the case that theory is useful because it allows us to find (or at the very least, have the correct toolkit and language to explore) solutions to real-world problems. In this part, we are going to look at some examples of such problems and develop mathematical language to be able to discuss them more abstractly. I’ve put the term “real-world” in quotes in the title, because I’m going to be talking about these problems in a lot of generality. However, I want to stress that specific instances of these problems are actually relevant in industry, and I think it’ll be easy to see why once I start talking about them.

While all NP-hard optimization problems are identical in terms of exact solvability, they may differ wildly from the approximative point of view. If the goal is to obtain an answer that is “good enough”, some problems become much easier (such as KNAPSACK), while others (such as CLIQUE) remain extremely hard.