CS6515 OMSCS - Graduate Algorithm
Best TA!
GA has some of the best TAs I have seen in OMSCS! It is extremely well run and organized.
My Favorite TAs are Jamie McPeek (subjective to some people) and Emily Lentz - Jamie being the most active in Ed among all the TAs. In my opinion - If you spend time to properly phrase your thoughts and confusion (and doing your research before asking), Jamie is very patient and helpful. However do not expect him to spoonfed you, his responses are done in such a way to encourage you to arrive at the conclusion yourself; a true educator.
Also Emily Lentz for always listening to student feedback regarding the ambiguous questions (or wrong answers post grades) and rectifying them, as well as actively responding to student regrade requests and helping students to get their marks back!
Overall Review
CS6515, “Introduction” to Graduate Algorithms is more of a theoretical CS class and not a “Data structures and algorithm” class. In the sense the problem is given to you, and you need to use your toolbox to solve it, rather than “here is the Heap data structure, implement it”. The course is largely split into 3 parts, and gets more abstract and about proofs in the later sections. Since I am in the Machine Learning specialization, this is a must!
In my Study group, there are people without a math/CS background (engineering) and they did better than me. So it is definitely possible - however they also worked and prepared a lot harder than me by finishing up all the textbook practice problems, even beyond what is suggested.
The good
The content is actually very useful! Things like FTT was quite interesting to me since I have never encountered them before. For others, RSA or Linear programming is also very applicable in our daily lives.
Specifically for me, I really liked the dynamic programming section a lot - it gave me a whole new approach on how to solve DP problems. The next section that I liked and learnt a lot was NP-complete - It made me think about my past projects, where I had to make some assumptions in order to reduce the runtime, turns it is looking for a connected clique which is NP-complete (basically a really hard problem to do so in polynomial time).
The bad
Formatting and their requirements! This is by far my biggest critic of the course. I actually spend more time understanding (and reading Ed) about the way they want the answers to be delivered, rather than studying the actual content or the assignments.
Numerous errors and ambiguity in their MCQ questions (both in quiz and exams). For instance, one student asked if this question is supposed to have an answer in which the head TA replied “It would be unfair to ask a question without an answer” - It turns out that indeed the question was wrong, there is no answer! This is also not a one time occurrence!
The TAs also went pretty hard with OSI, which in my opinion was never really addressed properly. There were a lot of students who kept calling it out just to be shut down. Overall it generates a lot of unnecessary stress - On both Summer 2024 and Fall 2024, the “infamous” homeworks with plenty of OSIs were variants of popular leetcode problems (and not so much about the other programming homeworks). A couple of folks I know got caught and they have no reason to “cheat” for HW4 (in my opinion).
The grading of exams/homeworks can be really harsh, if you miss any small detail be prepared for anywhere from a -2 to -8. This is further made more stressful in the exam setting, if you do not have the intuition for one of the questions, you are potentially looking at a -16 points which is 5 percent of the overall grade (ouch!).
Time Requirements
I probably spend more tim than required, in order to create my notes and exam notes. Otherwise I probably estimate it to be about 10-15 hours given that I was exposed to more than half of the content (both in school and work) and formal mathematical proofs is something that I am very comfortable with!
Content
The content can be found in Omscs Wiki and GA lectures, and is broken down to 3 parts:
| Part | Content |
|---|---|
| 1 | Dynamic programming (DP), divide and conquer (DC) |
| 2 | Graphs and RSA |
| 3 | NP-Complete and Integer Programming |
The class becomes more and more abstract as you proceed.
- In DP, you need to come up with every moving part on your own, while in DC you could either do that or modify/chain well known approaches. (E.g sort an array or perform binary search)
- Starting from Graphs, you start chaining blackboxes to solve a problem. For example given a set of roads and cities, how and what can you solve to check that for any pair of cities, it is possible to reach each other?
- In the last part about NP problems, you are essentially trying to show that there is no known algorithm to solve it efficiently.
Always remember this!
Correct > Complete > Concise!
A correct answer should always be your top priority! E.g a $O(n^2)$ with correct outputs over $O(n)$ with incorrect outputs. Write as much code/words you need to make your solution complete, and, when all this is done, then work on making it optimal. For instance each for loop has 3 working lines? Can you make them into 1? Have a complicated if-else branching? Simplify it!
The other most important tip being:
Solve the problem the intended way! Do not be overly creative!
This is because this is a class with over 1000 students, and the workload on the TAs is pretty high. Your “creative” solution might be correct, but regrading process can be quite draining 
!
Resources
-
Omscs Wiki
- Tells you which textbook questions are useful that are also suggested problems.
- GA lectures
- GA notes by Teapowered
- GA notes by Monzersaleh
- My own notes
-
My own exam notes
- This is a different set of notes specifically just for exam prep.
(Feel free to drop me a note or comment down below if there are other resources you like me to include! 
)
Homeworks
For my semester there were 5 coding assignments and 5 written homeworks. Of the 5 homeworks 2 of them were a give away (Implement the union find data structure and using the scipy linear programming package). Some of the programming homeworks might include a written component.
Written Homeworks
The best tip I have is the solution intended for all homeworks (including the programming ones) turns out to be quite simple and elegant. If you finding yourself justifying or finding significant flaws with your approach, you should backtrack or try to approach it again!
For the written portions, be as specific as you can unless the TAs or lectures specifically point out certain procedures that you can simply state without details! This is also an area where a study group is very useful (Will talk about it later!).
Programming Assignments
During my semester homework 4 resulted in quite a few OSI cases (> 100) and is a variant of a common leetcode problem. This is unfortunate. From what I know, homework 9 was also a variant of the leetcode problem.
The whole situation is pretty unfortunate
- Try to code it with your own style (and not standard protocol / templates)
- Log your changes with IDE history to track your chances, incase you need to use it to defend yourself.
With that out of the way, here are the tips to do well:
- Test your code! Think of edge cases, write a brute force testing script when it is possible to do so!
- Learn to profile your code and see if any code can be simplified. O(2n) is different from O(n)! Squeeze every second of performance you can get!
- Check ed to see what are runtime people reported. For example you arrived at your O(nlogn) solution but someone else reported O(n).
- Read common recurring concerns highlighted by students and learn to read in between the lines!
For the last point regarding common recurring concerns, a common point (as well as my study group) asked that for a subset of the problem space, what if it is an invalid problem space? The TAs consistent response was “the overall input is valid”. On top of this, students were asking is using Infinity allowed? It turns out this two led to one edge case and using infinity allows you to solve it quite elegantly.
Exams
For the MCQ section - Study everything for the Exams! For my semester they test the smallest of details, the quiz is not a good representation of the final exam!
For the written components, in decreasing priority:
- Understand everything about the homeworks they have given you
- If the homework is about Problem Y to be solved with algorithm X, study everything about algorithm X, like, everything.
- Think about every possible variant problems you can solve with algorithm X.
- Look at the Ed posts on regrades, understand what people are getting wrong (even if you got full marks or did not get full marks) and what key words that they are looking out for!
- Understand everything about the practice problems
- These are the ones with solutions provided
- Understand everything about the suggested problems
- And then attend Joves Office Hours
Study group
A good study group is highly recommended! The first key benefit is because discussing of approaches is allowed for the homework, you get to learn a lot about other people’s approaches (whether they could be right, or showing them why they are wrong!). Sometimes your study group could come up with a brilliant idea, or provide tests cases (when it is allowed) to show that your approach is wrong. More importantly, they also discuss what “key words” or “ideas” needs to be shown in the written homework - a significant chunk of my study group got full credit for most homeworks (I got full credit for 8 homeworks, with 16/20 and 19.72 for the other two!). This also helps for your morale, after all, misery loves company!
The second key benefit is when it comes to regrade requests - I seen folks who do not have study group, and “pleading” with people to help them with their regrade requests which is not a good spot to be in. I personally had 4 regrades requests and had the necessary logistics fulfilled within the first hour thanks to my study group.
The last key benefit is the distribution of workload, such as creating exam notes, created flash cards, trying out suggested problems, summarizing office hours. Some folks went above and beyond to explore CLRS. On top of this, the study group can also collectively help to predict the exam questions based on the homeworks - I am happy to say my study group mostly got our predictions spot on !
Joves OH
Joves Office hours are indeed a marathon, and can be quite a fire hose of information. In this class the ability to come up with intuition is very important. If you have time to watch it, you should! Sometimes by learning the intuition you can get hint to solve some of the exams MCQ questions!
Front-loading Suggestions
Don’t waste your time with leetcode, and if anything leetcode will hurt you!
- In this class they have their own programming container classes, which is very different from python
- Leetcode spoils you with tests cases, and this is something you need to come up with
- Most OMSCS classes gives you the test suites as part of gradescope
For front loading:
- Study O complexity!
- For dynamic programming, study the lectures and practice problems
- For divide and conquer:
- Understand how Recursion works and Master Theorem
- Binary Search
- Merge Sort
- Quick Sort (Especially the choice of pivot)
- Graphs
- Study Graphs and their representation in adjacency list
Conclusion
Overall, the class content is good, interesting and I learnt a lot and the content is not difficult! Unfortunately I spend more time understanding their requirement and grading can be really harsh which contributes more stress than necessary! Finding a study group can be really beneficial, such as boosting your morale, discussing approaches, regrade requests, or trying to predict the exam questions!
Anyhows! This is my last course from OMSCS and glad to say I got out! Time to move on!