OMSCS — Graduate Algorithms

Fun fact: Many GaTech students end up working for The Home Depot since the headquarters is in Atlanta.

Overview

(Or more specifically, how much time does this class really take?)

There are two major camps in this GA debate. The loudest and most prevalent viewpoint is that this class is intense; you’ll be spending hours on end doing practice problems in order to prepare for the unforgiving exams. The opposing viewpoint claims this course is one of the program’s easiest and lament the fact that it is required. After all, basic algorithms should be required before admission to OMSCS and the complainers are just ill prepared. As is common with these kinds of things, there is truth to both of these views.

One thing that makes this conversation confusing is that students often say that “Data Structures and Algorithms” should be a mandatory prerequisite before enrolling in OMSCS, but the contents of that class vary widely depending on where you take it. At my undergrad (and many other universities), we had two separate classes. One for data structures (think: linked lists, trees, hash tables, searching, and sorting) and another for algorithms (think: dynamic programming, divide and conquer, NP-Completeness, graph algorithms, etc.).

On the other hand, if you google “Data Structures and Algorithms Syllabus” you’ll get this UW CS373 syllabus which is akin to an intro data structures course as well as this Harvard CS 124 syllabus, which looks like a more comprehensive version of GA. While the vast majority of students have probably taken a data structures course, it seems that far fewer have taken a course dedicated to algorithms. So what do people really mean when they say you should already know “basic data structures and algorithms”?

If you’ve taken a course dedicated to algorithms, then it is very true GA will be redundant for you — I say this as someone who quite enjoyed GA and learned quite a bit, though my undergrad algorithms class probably had 80% overlap. So take a peak at the syllabus. If all this material is new to you, it is likely the type of problem solving and thinking that this class requires will be novel to you and it may take some time. On the other hand if you’ve seen these topics before, the class may be predictably trivial.

What to expect

Regardless of your preparedness, the grading in this class is more unforgiving than most other courses. 75% of your grade is determined by exams, with an optional final whose grade can replace your lowest exam score. The last 25% come from homework, quizzes, and coding projects. Do your best to get full credit on all of those; they should be essentially free points since this class is very relaxed when it comes to collaborating and searching for answers.

As for the three exams, each are made of two free-form questions which make up 2/3 of the points. The last section is multiple choice and make up the last 1/3 of the points. At 2.5 allotted hours, time is generally plentiful if you don’t have too much trouble with any of the questions. For example, I finished the first exam in less than an hour.

On the other hand, if the correct answer does not immediately jump out, you will be sorely wishing for more time. And here is where the biggest complaint for the course comes from. A single brain fart on one of the free-form response questions can lead to you dropping a letter grade. But by following some practical tips, you can safeguard against this scenario.

General Tips

• The textbook and lectures compliment each other nicely. If the material isn’t clicking, be sure you’ve done both.
• The topics are all nicely self-contained, which can be good from the exam point of view since you can cram the topics needed for the exam and then promptly shift your focus on new material afterwards.
• When I took the course, one of the TAs, named Joves, provided a comprehensive set of notes he created when he took this class. It was an incredible summary of the material that uniquely focused on the content and strategies that likely would appear on the exam. If he is still TA when you take the class, be sure to take advantage!
• Though Joves’ notes were the best bang for your buck, I am always a fan of George’s notes. They are short and sweet if you’re looking for an alternate perspective.
• Do all the homework, as well as the recommended practice problems from the textbook. Exam questions tend to be similar if not exact copies. The wikidot provides a pretty good list of practice problems to do.
• If you’re looking for more practice, don’t shy away from re-doing practice problems you’ve done before. Type out the answer like you would in an exam setting. Since exam questions are often quite similar to the recommended practice problems, knowing the solutions to those practice problems inside and out can really help.
• Coding projects aside, don’t write real code either for homework or practice. Pseudocode, math notation, and free-form answers are expected and will require practice.
• Practice brevity. Long word dumps can hurt your grade if you accidentally say something incorrect (and is frustrating for your grader). Ultimately, writing a proof is more like poetry than prose. If you try to boil everything down to their simplest axioms, your proof will be way too long. On the other hand, excessive handwaving with statements like “it’s obvious that…” or “we can therefore conclude…” followed by an unsubstantiated assertion is where points are lost.
• Continuing from the last point, much of the style and structure that is expected in your exam responses can be learned or inferred from office hours as well as Joves’ notes (if available). There is a general ideal structure for the free-form exam responses and it will make everyone’s lives happier if you adhere to them.
• Every topic section can generally be broken into two parts. First, Prof Vigoda will introduce some fundamental topic or idea. Here is where the majority of your mental energy should be focused and likely what the free response questions on exams will be based on. Afterwards, he will dedicate entire lectures to some application of that fundamental idea. These are more commonly found in the multiple choice section of the exam. In these application lectures, understanding the high level details is typically sufficient. They will often include many video segments diving into different aspects of a proof. It is pretty rare you will need to remember these details.
• While different students definitely struggle with different topics, I’d say this course is slightly more front-loaded than back-loaded. That’s especially true if you are in a position to skip the final.

Exam 1

• All dynamic programming problems you are likely to see can be solved in a similar fashion to longest increasing subsequence (LIS), longest common subsequence (LCS), chain matrix multiply (CMM), or knapsack. Be sure to understand these four problems very, very well. When faced with a new problem, the first step should be to decide which one of these four problems is most similar. The solution will likely follow.
• For many, dynamic programming seems utterly impossible at first. Practice, practice, practice is key. Do and re-do problems from the textbook.
• Here are some trains of thought that helped me wrap my head around DP. Lots of practice problems will be slight variations of one another. These are very helpful to work though. Think about what stays the same between the two variations and their respective solutions. Think about what changes and why. Recall that DP is all about overlapping subproblems. The base case of a DP problem is usually trivial to solve. Now imagine the problem is 1 unit longer. Think about how that changes the solution. What new information is needed? Why can’t the solution used for the base case suffice? Now go about the problem from the other direction. Imagine the problem is very long, but you already have the solution to all the subproblems (i.e. your table is already filled out with the required info). Think about what the different possibilities for the contents in that table can be. If you needed to add another entry to that table, can you figure out what work you need to do that?
• Expect to solve a DP problem for one of the free-form response exam questions. Again, you should be able to structure it as either LIS, LCS, Knapsack, or CMM.
• The instructors expect DP solutions to be in four parts: base case, recurrence, pseudocode algorithm, and run time. Be very clear and explicit that you are addressing each of these (like by putting them in their own sections with a header).
• It’s possible that DP shortest path algorithms will appear as a free-response question, but more likely will be part of the multiple choice section.
• Prepare to create a divide & conquer algorithm for one of the free-response questions. Be ready to use merge-sort (check if sorting the problem may help), and/or binary search (check if you are searching for something in an ordered list).
• As a sanity check, think of the simplest brute force solution for the problem asking for a divide & conquer approach. If your divide & conquer solution has a runtime that is equal or slower to the brute force approach, treat that as a red flag.
• Remember to explicitly label and address the three parts to a divide & conquer problem: algorithm, correctness, and runtime.
• FFT, solving recurrences, linear time median algorithm, and fast integer multiplication are all likely to appear as multiple choice questions.

Exam 2

• If you’re given a graph problem (or two) on the exam, you will need to use some combination of techniques from Djikstra’s, minimum spanning tree, strongly connected components, max flow, and/or topological sorting. Know each of these algorithms very well and the scenarios and types of graph (directed/undirected) they are used on. In fact you should explicitly try all of them on the problem and think about why they are/aren’t appropriate for the given problem.
• Be prepared to do some modular arithmetic, likely as part of the multiple choice. This will take some practice.
• RSA and the different applications of max flow and the SCC algorithm are all likely for the multiple choice section.

Exam 3

• The free-response questions are almost guaranteed to be two NP-reductions. Understand the ones taught in the lectures very well. Know when each one is appropriate. For practice problems, if you try one of the NP problems and the reduction doesn’t easily follow, think about why that is. The reductions on the exams generally have a single obvious choice of an NP problem that should be used.
• The NP reduction will mostly likely be in the form of a graph (think clique, vertex cover, or independent set), a logic problem (think SAT or 3SAT), or a knapsack-like problem.
• If the problem specified a budget (rather than a goal) try using vertex cover.
• The number one mistake students make is doing the reduction the wrong way. Always reduce the known problem into the unknown problem. Even after a lot of practice, when it came to the exam, I still ended up wasting 30 minutes because I tried doing the reduction the wrong way.
• I find that NP reductions require a unique mental shift. Throughout most of the semester, you spent your mental energy trying to find ‘the answer’ to some problem. For NP reductions, you must remember that you are not trying to find an answer to the given problem. Rather, the first step is to assume there already exists a solution to that problem. Given that blackbox solution, your job is to solve a different NP problem (i.e. one that seems similar and was covered in class) by transforming it to an instance of the new problem.
• LP problems and the halting problem will be found in the multiple choice. Be prepared to formulate a linear program in standard form, find the dual, and determine feasibility and boundedness.

Final

• I unfortunately have no tips here. I did not take the final since I was comfortably getting an A after exam 3. Hopefully after following the above tips, you’ll be in the same position!
• For many of you, this will be your last class before graduation. Having the last couple weeks of the semester off since you don’t need to take the final is an excellent graduation gift.