Algorithms and Data Structures MicroMasters UCSD Review

Recently I have completed my edX MicroMasters Program in Algorithms and Data Structures by The University of California, San Diego. You can also take a shorter version of the program on the Coursera platform titled Data Structures and Algorithms Specialization. Given Coursera specialisation is a subset of the MicroMasters, this review should cover that Specialization as well.

This is a subjective review and not an objective analysis of the program. Let me provide you with my motivation for taking this course and then we will jump into it.

Motivation

I have been very lucky to have plenty of opportunities in my career. I held various roles in the industry from Software Engineer to Chief Software Architect. Many years ago now I remember being in the office and someone mentioning the “Towers of Hanoi” problem and how it can be solved with ~3 lines of code. I was surprised that this was possible and the solution could be so simple. So naturally being a curious ex-software engineer I have decided to have a go, I became hooked. This was not a jaded software engineering problem, this was a pure computational problem.

Towers of Hanoi (animation borrowed Dan Romik’s Home Page)

Years later, myself and a few of my colleagues at the time have been taking on progressively harder algorithmic challenges. From simple problems like “Trap Water” on LeetCode, all the way to “Expanding Nebula” from mysterious Google Foobar. After a while I wondered if there is something more official I could do to improve my algorithmic skills. More importantly I wanted to make sure I was not missing something fundamental from my repertoire, as I wanted to do some light independent research in the future. This is when I stumbled upon this MicroMasters.

Program Framework

MicroMasters is structured in a linear and very hands-on way, which is my preferred method of learning.

Every module comes with lectures, some pseudocode, proctored exams and what I would call Algorithmic walls. Algorithmic walls are coding problems, you have to write code that is computationally and memory efficient, and that passes all known and hidden tests.

These hidden tests are the hardest part, because if you miss something you are on your own to figure out what edge case or logic you have missed. For some problems this is easy, for others not so much. Luckily, if you are deeply stuck, for every course there is a discussion forum where trapped souls that cannot scale the wall congregate, and try to figure out what to do next. While there are no answers, forums are meagre and eerily quiet, at times there are few pointers that can nudge you in the right direction.

MicroMasters delivers on its promise of tons of algorithmic challenges that will stretch your mind and sometimes make you question your ability. If you have lots of time on your hands, love algorithms even more than me or are just super gifted at algorithms (not like me), or some combination of the two. Then you will be happy to know that every course has extracurricular hard coding challenges waiting for you.

I found myself at times frustrated with how lecturers framed problems, it felt as if they were either obfuscating or misleading. This is a MicroMasters and not a MicroBachelors. Naturally an expectation is that you will do independent research. Answers will not be handed to you on the plate, you need to earn them, however lecturers should be more precise with their language.

Just to give you a concrete example. Here is a screenshot from the discussion forums where myself (zkav) and another student (made anonymous) provided their feedback to the lecturers about misleading.

Lecturers gravitated towards low level details but often would not explain how an algorithm is used in the real world. What is the big idea behind it and why it works. Instead they focused on the nuts and bolts and too many times missed that top down introduction. I have used “Introduction to Algorithms” by Thomas H. Cormen and WilliamFiset’s YouTube channel as a supplement.

At other times lecturers were explaining something so painfully obvious I felt that I was missing something very important so I started to overthink which slowed me down. To resolve this issue I jumped to the algorithmic wall and ignored the lectures. I only watched them if I got stuck or was revising for the exam.

Program Overview

MicroMasters is composed of courses algorithms and concepts below, this list is not exhaustive, just my personal highlights:

1) Algorithmic Design and Techniques

Greedy, Divide and Conquer and Dynamic Programming.

2) Data Structures Fundamentals

Binary Search Trees, Linked List, Disjoint Sets, Heap Sort, Priority Queue, AVL Tree, Splay Tree and Amortised Analysis.

3) Graph Algorithms

Depth First Search, Strongly Connected Components (Tarjan’s), Topological Sort, Breadth First Search, Shortest Distance (Dijkstra and Bellman-Ford) and Minimum Spanning Tree (Kruskal and Prim).

4) NP-Complete Problems

NP, NP-Complete, NP-Hard, 2SAT, 3SAT, Hamiltonian path and Approximation.

Program will make you think of Hamiltonian cycles in the unexpected places

5) String Processing and Pattern Matching Algorithms

Tries, Suffix Tree, Suffix Array, Longest Common Prefix (LCP), Burrows-Wheeler Transform and Knuth-Morris-Pratt.

6) Dynamic Programming: Applications In Machine Learning and Genomics

Optimisation using Dynamic Programming, Hidden Markov Model (HMM), String Edit Distance, Local, Global and Overlap String Alignment.

7) Graph Algorithms in Genome Sequencing

Euclidean Cycle, Euclidean Path, De Bruijn, De Bruijn Pair and some Genome Theory.

Highlights

During the Algorithmic Design and Techniques I realised that my dynamic programming knowledge had gaps. I have enjoyed building on my new dynamic programming knowledge during Dynamic Programming: Applications In Machine Learning and Genomics by building optimisation solutions for edit distance and Hidden Markov Model.

The Data Structures Fundamentals course was the most math heavy part of the MicroMasters due to the amortised analysis. For this module I strongly recommend that you study algorithmic complexity of all algorithms that you have covered in the module, or you learn how to calculate amortised algorithmic complexity on the fly. I enjoyed this module, in particular disjoint sets, priority queue and amortised analysis.

The Graph Algorithms course was delivered very well, probably the best course in the program, I have learnt a lot.

NP-Complete problems, this course was the most challenging of the entire program. I think the topic was not covered so well but also the concept was so novel to me. I mean never before did I have to think about reducing my problem to a logical circuit for SAT solvers to brute force a solution.

To fill in the knowledge gaps so that I could climb the NP algorithmic wall I had to resort to maths papers from other universities. I found this module very fascinating and satisfying, as for a long time I felt I knew what NP was all about, turns out I did not. I have written a whole article about this, P vs NP, Practical Guide for Software Engineers.

Travelling Salesman Movie 2012 — P versus NP problem.

After enjoying the graphs course so much, I felt I would breeze through the Graph Algorithms in Genome Sequencing. This was not the case unfortunately. I think I had to write the most amount of “thoughtful” code in the entire program for this part of the MicroMasters. It made me rethink my love for graphs. I think overall, this was my issue, as due to my personal life circumstances I had to take about 6–8 months break from the program to focus on personal matters. It was very hard to get back into the MicroMasters again after that. I strongly recommend that you do not take long breaks once you start.

Lowlights

I felt that String Processing and Pattern Matching was delivered poorly, concepts were brushed over quickly and too much pseudocode given away for mindless implementation. However I did like the subject of text compression and given I am a fan of Donald Knuth, it was nice to learn about Knuth-Morris-Pratt algorithm.

I was surprised to find the Max Flow algorithm in the capstone. It was not mentioned in the lectures. I was looking forward to the lecture on the subject since the Graph Algorithms course, as I have noticed that WilliamFiset covered it in one of his videos and it piqued my interest. But no, there it was, as a coding problem, heavily understated, buried in the capstone as a “circulation problem” with just words “reduce this to Max Flow”. To save you time, it should have said “express problem as Max Flow with Edge Demands and then reduce it to Max Flow” or something like that. There are some math papers online that provide the theory that will get you mostly there.

Conclusion

Writing this review I am realising that the course had a few shortcomings. Having said that, I have learnt a lot and I have filled in the knowledge gaps, so my primary goal was achieved.

Inefficient delivery of material has wasted time, this time “waste” was useful in some aspects. It allowed me to linger on topics for long enough for them to be understood on a deeper level.

Overall, it was a challenging and nourishing program. Special thanks to Alexander S. Kulikov, and Pavel A. Pevzner as they made this entire MicroMasters come to life. I highly recommend it.