CS-6515 Graduate Algorithms

Ben Yu -

This will likely be the final course you'll take in your OMSCS journey. It's a pre-requiste to gradate for all specializations and at least in 2023 you were most likely unable to register for the class until your final semester (unless you were very lucky and go an early waitlist position). If you search for course reviews online, you'll find that this course has built a reputation over the years for being difficult. While the material is moderately challenging, I found that it was a unique combination of the course's logistics and grading mechanics along with it being a graudation requirement that adds a level of stress and anxiety that doesn't exist for the other courses.

For my semester the course was broken down to the following deliverables:

  • Homework: 14%.
  • Coding projects: 7%
  • Mini-Quizzes: 7%.
  • Logistic quizzes: 3%
  • Exams: 69% (3 total)

Based on the breakdown, you can see that the homework, projects and quizzes are mostly there as a preparation tool and forcing function to study for 3 seperate exams/midterms, which makes up the bulk of your grade. During my semester the breakdown was:

  • Exam 1: Dynamic Programming, Divide & Conquer, FFTs
  • Exam 2: Graph Theory: Strongly Connected Components, Minimum Spanning Trees, Max Flow. Modular Math & RSA
  • Exam 3: NP Completeness, Linear Programming, Halting Problem

Each exam usually consisted of 2 short answer problems and a section of multiple choice questions. What most students (myself included) struggled with is the particular requirements for answering each short answer question. Due to the particular nature of this course, the instructors will require your short answers to follow a specific format, which are provided for you in your homework, quizzes and regularily reviewed at Office Hours and on Ed posts. The formatting requirements ensures that we're demonstrating a deep understanding of the material and ensures we can be evaluated fairly in an online setting. But in my opinion the strange and sometime obtuse requiements also relaxes the level of programmatic and mathematical rigour from equivalent graduate level algorithms course that I've takin in the past. Seeing other iterations of this course from other universities like MIT, Berkley and UofT (we used the same textbook as my undergrad course ECE-358H1!) I think the course could benefit from actually increasing the level of difficulty of the questions but increase the duration of the exams or make the exams open book.

Curriculum:

  1. Dynamic Programming - The bane of any technical programming interview . DP is an optimization technique to breaking down problems into smaller subproblems and efficiently storing solutions to avoid redundant computations. We cover the typical problems like longest common subsequence, knapsack, shortest path etc... Dynamic Programming was also the only type of problem where we could solve the problem with pseudocode.
  2. Divide & Conquer Algorithms - Break your problem into smaller, more manageable subproblems, solving them recursively, and combining their solutions to derive the final result. We review classic algorithms like mergesort, quicksort then cover advanced techniques such as Strassen's algorithm for matrix multiplication, median of medians
  3. Fast Fourier Transform - We review the basic components of how the FFT works as a divide and conquer algorithm. This section was a highlight for me personally as it made me have a deeper appreciation for the algorithm itself and it's use for fast multiplications
  4. Graph Theory - Strongly Connected Components - Students delve into algorithms for identifying strongly connected components within directed graphs, gaining insights into their applications in network analysis, social network modeling, and compiler optimization.
  5. Graph Theory - Minimum Spanning Trees - MSTs represent a cornerstone of graph theory, offering elegant solutions to connectivity problems in network optimization. Through algorithms like Kruskal's and Prim's, students learn to construct minimum spanning trees efficiently, unraveling their applications in network design, clustering analysis, and routing algorithms.
  6. Graph Theory - Maximum Flow - Maximum flow algorithms play a pivotal role in modeling and optimizing flow networks. Students explore algorithms like Ford-Fulkerson and Edmonds-Karp and derive the min cut/max flow theorem.
  7. Modular Math & RSA Encryption - This was a particularily interesting section for me since it dealt with number theory and primes. We dove into primality testing, Euler's theorem and work through the RSA encryption algorithm itself, gaining a deep understanding of it's role in cryptography.
  8. NP Completeness and Reductions - The concept of NP completeness serves as a cornerstone of computational complexity theory, offering insights into the inherent difficulty of solving certain decision problems. Through reductions and complexity analysis, students explore the intricacies of NP-complete problems, gaining a profound appreciation for the limits of efficient algorithmic solutions. We review the basic Karp NP Complete Problems like: SAT, 3SAT, Clique, Vertex Cover, Knapsack etc...
  9. Linear Programming - Linear programming provides a powerful framework for optimizing objective functions subject to linear constraints, with applications spanning operations research, economics, and engineering. Students learn the simplex method and interior point methods, mastering techniques for solving linear programming problems and unlocking their potential in resource allocation, production planning, and decision-making.

I'm really glad that I was able to take this course and it served as a fitting end to my OMSCS journey. Algorithms serve as the core foundation of computing and every domain ranging from machine learning to compiler design. By appreciating the role of algorithms and complexity theory, we gain insight into the fundamental mathematical realities that power and limit the applications we rely on daily, and allow us to build even more powerful tools for everyone.