| Category | Difficulty |
|---|---|
| HW | 6 |
| Exams | 6 |
This class is the final requirement in the CS core, and is a surface-level introduction to a variety of algorithms.
The structure of the class is very typical to math/theory classes,
Overall, the class is a very standard, well-organized, and straightforward class. There are not many surprises, and you can do well in this class if you can learn how to recognize and apply the correct algorithms to problems.
The class is very well-organized in lectures, where every lecture has a set of notes or slides, and might even have past iterations, so can be read before the course starts.
The lectures are structured in a way approximately like:
- Example of problem associated with algorithm
- Big-O complexity
- Proof of Big-O
- More examples
- Can we do better?
Most lectures can be absorbed without any prep, but historically, there have been lectures that require some linear algebra knowledge, such as vector spaces, span, and eigenvalues. In general, you should take some sort of linear algebra course in college if you're a technical major, but if you haven't, I highly recommend learning at least what vector spaces are before taking 15-451.
The are two parts for every HW, a proof-based theory portion that is done as a group, and a programming section, that is done individually. They usually have different due dates, as HWs are done with oral presentations, that are based off of a first-come-first-serve signup basis, and programming assignments have historically been due on Sunday.
The first portion is a proof-based written section. In 451, you get to choose a group of 3 to work on these problems. Instead of asking for a written submission of all the problems, the course staff holds "oral sessions," which are presentations of the HW problem solutions by the group. The structure of the oral session is that the course staff chooses 3 problems at random for the group members to do individually, which means every group member should know how to do all the problems.
Unlike the 251 writing sessions, which can have quite brutal penalties for mistakes in proofs, 451 writing sessions are interactive, giving students opportunities to correct their mistakes if they make them. In general, graders of oral sessions are more lenient than a comparable writing session in 251.
In addition, since because of this leniency, you usually don't have to write out full in-detail solutions in prep for the session. You are usually fine just knowing 80% of how to do the problem, and filling in whatever gaps you didn't explicitly prepare for.
The second portion of every HW is a programming section. This part of the HW usually involves implementing a key algorithm learned in the course. As of when I took the course, the languages offered to code the algorithms are
C++JavaSML
For most people, C++ and Java are the way to go, but if you're hardcore, SML
is out there. There is an Autolab that gives you unlimited attempts to submit and
try to pass all the tests, with no hidden tests, so there is a lot less pressure for
the programming assignments. Although, if you have a bug, you usually have to
write your own tests to figure out what is wrong. There is also a leaderboard
to encourage competition among your peers, although most people are happy to just
get full credit.
If you're a true performance junky, using C++ is generally a stronger choice
than Java and SML.
Although you're "just coding an algorithm," you can make your life significantly better
by coding with good practices. For me, I did the following (I chose C++):
-
Use version control to manage your work (e.g.
git) I found that one repo was enough for all the HWs, no need for one repo per HW since the assignments are relatively small. -
If you use Object-Oriented Programming, please use classes to help organize your work.
-
As always, helper functions are nice to help split up your code.
-
Comment your code. It will help you spot your mistakes faster, even if no one is actually gonna read it. You have to justify your Big-O complexity anyway, so might as well document it well.
-
Have some sort of debugging system setup. Print debugging usually suffices for figuring out most issues with algorithm code.
-
Writing automated testing scripts is super helpful. For example, with
C++you can useMakefilesto build your test suite.
Exams are very straightforward applications of the algorithms and their properties.
Exams often have 3 sections:
-
T/F: Mostly just questions about properties of algorithms. For example, you may be tested about the Big-O time/space complexity of an algorithm, or what steps are performed for a particular algorithm.
-
Short answer: Usually a simple application of an algorithm learned in class, or filling in some blanks for the application of an algorithm. For example, a short answer question on Bellman-Ford might involve filling in the edge weight calculations for a few iterations. You could also be asked to calculate an expected value of iterations for an algorithm, or be asked to calculate the Big-O of a slightly modified version of an algorithm you have learned in class.
-
Long answer: Usually full proofs to justify a theorem. These are usually the most difficult parts of the exam, since they require more than just regurgitating some memorized formula or algorithm. However, they can be prepared for, by studying the proofs for algorithms you have done in the course. Usually, if you are stuck on a proof, you can try to mimic a proof you've learned in class, and that can give you some help on constructing a proof that works for the problem.
As a responsible exam-taker, you should make a mental roadmap of how you want to do the exam. For example, if you think getting the T/F questions out of the way first is good for you, then do that first.
You are also given a cheatsheet for exams, which if you write electronically, you can fit a surprising amount of information on them.
- CMU Official Website: you can find past iterations of the course here and find the old course notes
- Linear Algebra: There are some good resources here for you to self-study/review linear algebra