Welcome to CMSC 14100! The syllabus and other information about the course can be found on Canvas.
This class is an introduction to computer science. So what is computer science? Computer science departments like ours are filled with all sorts of exciting work being done.
What unifies all of this stuff? At the core of it all, the same basic questions are being asked: how can this problem be solved by a computer and how hard is it to? We can break this down a bit more. Computer science is the mathematics of the structure of problems and problem solving. What does this look like in practice?
We'll be focusing on four main ideas in this course:
Our work is to put these things together. What does this look like?
The problem we are faced with is a large one. After going through med school, medical students do a residency with a hospital for a few years. But how do they get matched with those hospitals?
One unsatisfying way to do this is to just arbitrarily assign residents to hospitals. There is an issue with this: residents want to go to particular hospitals and hospitals want particular residents. What can end up happening when people are unhappy is that they go outside the system: hospitals and residents start going around and making side deals. This is not good because the system starts to collapse like this.
So the big challenge is this: coming up with a way to make these assignments so that everyone is satisfied well enough that a single entity can't trade around. That is, you might not have your top pick, but everyone you'd rather get matched with is already matched with someone they'd pick over you. In this way, our outcome has some sort of stability.
Abstraction is the act of taking our problem and smoothing out details that may not be totally relevant. This is not a new practice—remember that physicists love perfect frictionless spherical cows in a vacuum.
One thing you notice is that this problem isn't specific to residents and hospitals. You can imagine many different scenarios where you may want to assign pairs from two distinct groups: interns and employers, grad students and doctoral advisors, trainers and Pokémon, and so on. So the fact that these are residents and hospitals isn't that important.
This means there's something else that's not so important: the specific criteria by which each judges the other. Does it matter that a resident as twenty different conditions that they use to judge prospective hospitals? Well, not really. Think back to when you applied to universities—by the end of the process, you had a rough idea of where you wanted to go and how those schools ranked. So we can distill all of this information down to this same idea of preferences. We assume that both residents and hospitals do this work for us and they can provide a ranking of their preferred choices.
In these ways, we can abstract the pieces of our problem into something more general.
Now that we have our abstract pieces, we need to put them together. Something that mathematicians and mathematics is good at is turning all sorts of problems into other kinds of problems. By taking abstract pieces, we can arrange them in such a way that they resemble some other known structure or problem.
In our case, we notice that we have two groups, residents and hospitals, and these groups have some sort of relationship with each other. The particular model we'll be using is a graph, which is a useful structure for representing relationships among objects. Because we have two distinct groups (we're not pairing residents off with each other for example), we have what's called a bipartite graph. Finally, graph theory has a convenient notion for our problem—the idea of a matching, which is a choice of pairs such that each member of the graph belongs to at most one pair in the matching (it's possible that someone doesn't get matched).
So our problem about assigning residents with hospitals is really a problem about finding a particular matching in a bipartite graph. What's nice about this is that many others have already studied such structures and concepts before. We know quite a bit about bipartite graphs and matchings and we can make use of this work when trying to solve our problem.
Once we have an appropriate model, we can try to use it to solve our problem. In our case, we want to find a matching in our bipartite graph such that no resident or hospital can trade with any other, because anyone else would have to trade down.
What we want is a series of steps that will construct our desired matching.
Such a description of instructions is an algorithm. Algorithms are not new either. You may recall that there's a process to follow when doing something like multiplying two large numbers or doing long division. These are both algorithms.
This seems to work for our example—we would need to check closely. But there's an obvious question here: does this really always work? If I give any ranking of residents and hospitals, will I always get a stable matching? Does a stable matching even always exist?
The answer to that question happens to be yes! This algorithm is the Gale–Shapley algorithm, due to Gale and Shapley in 1962. This resulted in a Nobel Prize in Economics in 2012 (Unfortunately, there is no Nobel Prize for computer science, or even mathematics). How do we know this is the case? Because we can prove that the algorithm is correct. (This is not the focus of this class—you'll find that in CS 272)
But there are still more questions we can ask. For instance, is there ever only one stable matching? If not, then does the algorithm always give me the same one. Is there anything special about the one that this algorithm gives me?
It turns out the answer is there can be more than one stable matching! And what is not so obvious is that the result from the Gale–Shapley algorithm does have a special quirk. The choices that the algorithm makes happens to construct the stable matching that maximizes the preferences of the residents and minimizes the preferences of the hospitals.
These are all questions that one encounters in algorithm analysis. Algorithms are really constructive proofs. When a mathematician wants to know that something exists, one way to prove this is to give a series of steps to construct the desired object. But what is new is the existence of machines that can execute algorithms and our ability to translate algorithms in precise enough language to tell them to do this—this is programming. This leads to our next and final focus.
Complexity is about how difficult a problem is to solve. While abstraction, modeling, and algorithms are things that existed before computer science, complexity is a newer concept that is arguably the big idea that computer science has contributed. Intuitively, it makes sense that some problems are easy and some are hard. A big question that wasn't really answered until recently was how to measure and think about this.
Here's a rough way to think about how long this might take for the algorithm we just saw. Notice that we have to go through every resident and for each resident we have to go through their list of hospitals. So if we have $n$ residents and $m$ hospitals, we might have to look at up to about $n \times m$ possible pairings to decide our final matching. This happens to be pretty good—there are about $n!m!$ possible matchings to comb through.
If we think of algorithms as either a proof or hand calculation, then there's not much to say about how hard it is to do: it'll always be as fast as you or I can read or execute it. But once we have machines that are capable of executing algorithms on inputs of astronomical size, the question of how difficult problems are to solve becomes much more relevant. For example, if we have enough computing power, are there any problems that are really out of reach?
This observation implies that there are some problems that can't be feasibly solved and that there might even be some problems that are impossible to solve algorithmically, using computers. (In truth, this was the very first result in computer science—that there are problems that are impossible to solve algorithmically)
What's interesting about this idea of difficulty is that it's not something that can easily be solved simply by getting more computing power. Some problems are just so hard that the power required grows faster than our ability to improve computers and some problems are simply impossible to solve.
Putting these things together, we have all of the pieces of a solution to a computational problem: abstract the problem into more convenient pieces, take those pieces and model the problem, show how to compute a solution via an algorithm, and evaluate the complexity of our algorithm and problem. But notice there no programming is actually necessary. As I've noted, programming is the act of translating an algorithm into precise enough language that a machine can execute it.
One can argue that we don't actually need to learn programming to learn computer science. In fact, this course exists: it's called CMSC 27200 Theory of Algorithms. Of course, if we tried to make an introductory CS course with no programming, I imagine most of you would drop the class in the middle of the first lecture.
We teach programming as part of introductory computer science not just because programming is a useful skill, but because it's a good way to learn the other parts of computer science. Imagine, for instance, that there was a machine in math that could tell you immediately whether your solutions or proofs were correct and you got the chance to fix them before submitting them for grading. You'd be a lot more effective at learning math by getting immediate feedback.
It turns out that machine already exists—it's called a computer.