I wrote in May about the launch of Data Structures and Algorithms Specialization at Coursera. In September, the Advanced Algorithms and Complexity Course of this Specialization was launched, and I'd like to tell you more about it.
Course topics:
- Network Flows (Ford-Fulkerson and Edmonds-Karp algorithms).
- Linear Programming (the Simplex Method).
- NP-completeness (theory, reductions, solving NP-complete problems using SAT-solvers).
- Coping with NP-completeness (bruteforce optimizations, solvable cases, approximation algorithms).
- Streaming Algorithms.
The problems for this course were prepared by ifsmirnov, ilyakor, Michael, Perlik, romanandreev, Zlobober and Paul Melnichuk.
Network flows and the algorithms covered in the Specialization can sound as not very advanced topic for many Codeforcers. On the other hand, it is definitely a popular topic: there is a problem on network flows application virtually in every contest nowadays, and knowing the basic algorithms for finding flows is a must. One of the problems in the Programming Assignment of the Network Flows module supports that: Google Code Jam officially allowed us to use the statement of the problem Stock Charts from GCJ 2009 R2 (ilyakor has prepared the tests and the solutions for our version). Also, it often turns out that you should solve competitive programming problems on flows using Ford-Fulkerson algorithm, because it can be implemented extremely fasta, and it works fast in practice, but for the rare cases when the authors prepared specialized test cases breaking Ford-Fulkerson which is non-trivial.
Linear Programming has never been a competitive programming topic...right until the ACM ICPC World Finals 2016 where problem I just screamed "implement Dijkstra and Simplex Method". In the end, only one team from Stanford University solved this problem, and only two more teams tried. Stanford got lucky: they had the simplex method in their team notebook. However, according to what I observed during the finals as an ICPC analyst, they got unlucky too: it seems their implementation had a bug) As a result, they've spent a lot of time on fixing it and got the problem accepted only during the last hour, although they've started trying much earlier. I might have confused Stanford team's troubles with Wroclaw university's, though — sorry if that's the case. Anyway, so many teams have missed their chance for a much better result! One didn't have to solve anything, just needed to implement two algorithms, one of which many ACM ICPC finalists can implement without opening their eyes at night. romanandreev who prepared the problems on linear programming made sure that his solution passes on the problem I from World Finals 2016. Forums on the Coursera are flooded with discussions of accuracy problems and other subtleties of Simplex Method. Some of the students even complained that they have passed a full separate course just about Linear Programming, and have passed this problem there, but can't pass it in our course :) So you can test your implementation for the team notebook pretty well)
As opposed to competitive programming, in the real life Linear Programming finds lots of applications from optimizing advertising budgets, investment portfolios, diets, transportation, manufacturing, telecommunications to approximation algorithms for NP-hard problems, including the Travelling Salesman Problem.
It might sound surprising, but NP-completeness and coping with could be seen as the most practical part of the course. You'd argue that this is all about Complexity, but in practice most of the problems are NP-complete and it is much more efficient to see the problem is NP-complete at once and think of ways to cope with that (that's what we talk about in the two modules) instead of trying to come up with some clever data structure, essentially trying to prove P!=NP wrong, not knowing about that. Some of the problems use SAT-solver as a checker, because the problem is to reduce the initial problem to a SAT instance, and then it turns out modern SAT-solvers based on the latest research advances can solve huge instances in practice.
Streaming Algorithms are on the rise now, because often in Big Data processing you need to compute some statistic (number of different keys, the most frequent key, estimate the size of intersection of two sets of keys) based on terabytes of data using very limited amount of memory and reading the data just once or maybe twice. We've invited Michael Kapralov to cover this topic. We are going to add a problem on application of streaming algorithms later. It is challenging to separate the Streaming Algorithms from the regular ones under the typical time limits, but we already have a prototype, now it's only left to package what we got into a problem.
