When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Michael's blog

By Michael, history, 8 years ago, translation, In English

Last year we've won in Request for Proposals from Coursera, and this year we've launched the Data Structures and Algorithms Specialization at Coursera. It is now the main option for studying algorithms and data structures on the platform. Specialization is a series of courses ending with a Capston Project which enables to learn the subject much deeper than it is usually possible in the scope of a massive online course.

The Specialization is launched by University of California, San Diego (Computer Science program ranked 11-th in the world) and the Computer Science Department of Higher School of Economics:

  1. Daniel Kane — Professor at UCSD, Harvard graduate, PhD from MIT, four times Putnam fellow (US mathematical olympiad for university students), and there is even a wikipedia article about him.
  2. Pavel Pevzner — Professor at UCSD, last 12 years teaching Algorithms and Bioinformatics there, one of the authors of the Bioinformatics Specialization at Coursera.
  3. Neil Rhodes — Lecturer at UCSD, former Staff Software Engineer at Google, has been teaching for the last 10 years, developed educational programs for Apple.
  4. Alexander Kulikov — visiting Professor at UCSD, director of Computer Science Center and coordinator of Computer Science club in Saint Petersburg.
  5. Michael Levin — Chief Data Scientist at Yandex Data Factory, has been teaching algorithms for 8 years at Yandex School of Data Analysis.

One of the main features of the Specialization is large number of problems which enable the learners to really understand algorithms: you all know that it only seems you've solved the problem until you start implementing and submitting it. The same thing is true about specific algorithms and data structures. There are around 70 algorithmic problems in the Specialization. Many of those were prepared by Burunduk1, Gassa, GlebsHP, ifsmirnov, ilyakor, nk.karpov, Perlik, romanandreev, tourist, Zlobober, Paul Melnichuk and Ruslan Savchenko.

There are two options for the Capstone Project: Finding Shortest Paths in Road Networks and Social Networks using algorithms which are thousands of times faster than the classic ones or Bioinformatics Algorithms that are used to assemble a genome out of millions of small pieces.

If you're red or very yellow here, you probably won't learn lots of new things. However, I'll just post a few of the reviews from our learners regarding competitive programming:

"Amazing Course. I have been looking for this kind of course for months. Must for anyone who wants to be good in Competitive Programming and Algorithms"

"An excellent course. Though I have 10 years of experience in software engineering and I've participated in programming contests in my undergraduate years, this course gave me a much clearer vision on solutions for typical programming problems."

"Very good course on algorithms,particularly useful for competitive programming."

UPD. If you don't want to submit assignments and get a certificate, to see the videos and readings for free, you can go to a particular course, e.g. Algorithmic Toolbox, and select the option to "Audit only". The second course of Specialization is Data Structures, it has been launched in April. The other three courses are not launched yet, the next one — Algorithms on Graphs — will be available in June, next — Algorithms on Strings — in July, last — Advanced Algorithms — in August.

UPD.2 You can submit problems in one of the following programming languages: C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala.

UPD.3 Algorithms on Graphs course starts on June 6, and you can still enroll.

UPD.4 Algorithms on Strings course starts on July 25, you can already enroll.

UPD.5 Advanced Algorithms and Complexity course has started, and I'm going to write a separate about it.

UPD.6 The culminating project on Genome Assembly has launched, and the project on Advanced Shortest Paths launched as the last optional module of the Algorithms on Graphs course.

Greetings from ACM ICPC World Finals in Thailand!

  • Vote: I like it
  • +229
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Great work! Roughly speaking, what rating range is the course (and the problems) targeted towards?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The "lower bound" is to be able to write programs with loops, condition statements and recursion. The hardest problems in some of the courses are up to C-D of Div1, but these are usually optional to solve, and most of the courses don't have them.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also note that you can submit problems in one of the following languages: C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I wish we could atleast submit the assignments without having to buy the course :/

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    This is exactly what you cannot do without having to buy the course (but we also give away full test suites for the first programming assignment in each of the courses in the specialization). You can watch videos and read the readings without buying if you go through separate course's interface instead of whole specialization's interface. However, if the course is too expensive for you, there is an option to apply for financial aid.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I agree — Coursera lost a lot of appeal recently by blocking assignments for free listeners. I can understand complex assignments — like the ones in course mentioned, where you really need to run machine for solutions testing. But in situations where they blocked even simple quizes — I don't think they did a good job.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where I can find the option "Audit only" for the other 4 courses ?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Michael (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I bought it and working on it with you. Thank you guys!

I usually solve all problems and submit all assignments first and then watch lectures. :)

Lectures are very nice — I fixed some missing parts of my (missing) education (which were some things about hashing lately). Also I am really looking forward to the course on string algorithms, wondering how deep are you going to go?

Keep up the good work!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    We're going to do substring search, trie, building suffix array, building suffix tree given suffix array (but not building it from scratch using Ukkonen's algorithm), Burrows-Wheeler Transform, string compression using it and searching in the compressed form. We're not sure about regular expressions. Also, one of the Capstone Project options — the one on Bioinformatics — contains additional stuff like Hirschberg's algorithm.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks Michael,

      On strings my hope is to get another perspective on the same things. String algorithms are notoriously difficult for me to get intuition. It's not the same as being able to use and code. I have e.g. suffix automaton coded and I can use it for problem solving, but my intuition stumbles when I try to figure out if it can be used in some unusual situation. Or if certain modifications can be made to it to make it work in specific case. In this case I say that I understand algorithm, but don't have intuition for it.

      Don't know what to do with it — the only solution I have is to come back to it periodically, every time going through from very beginning (basics) to very end (coding up and using).

      Also I try to find more different approaches to view and expain it. I hope your course will become that point where I finally obtain intuition on suffix arrays and trees. If I get my intuition working, Ukkonen's algorithm will be a piece of cake :).

      On regular expressions — it is string related, but I would say that it is mostly about Automaton (DFA, NFA and so on) and it is a big-big topic in itself. So I wouldn't be surprised if you decide against inluding it in the course. I remember taking course at Coursera with prof. Ullman, which was entirely about automaton — great course it was.

      Good luck!

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Exactly: regular expressions are extremely important, but are not what is typically meant by Algorithms on Strings, and they are well worth a separate course, so I doubt we can include them and explain properly as a small part of the course.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks for the feedback: I'll try to think specifically about giving intuition.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The course Algorithms on Strings starts on July 25, you can enroll already.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Why no Ukkonen?

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It's too hard to teach in an online course. 99% of the learners will complain that it's too complex and won't be able to implement it in a reasonable time frame. Our goal is to have graded problems on all of the algorithms we teach, and practice shows that Ukkonen would be too hard. For competitive programming, I heard that nobody writes Ukkonen anymore, probably because suffix automaton is much easier to implement.

        However, Coursera is adding "Honors track", so I'm thinking about adding more optional videos and advanced problems later. If we do that, I'll start with Boyer-Moore, because it is what is used in practice for single pattern search. Maybe Ukkonen also won't be too hard to add on top of the currently available lectures on building suffix tree from suffix array in linear time.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hm, why there are no lectures about DAWG by the way? The same reason?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There are lectures about DAWG, if I understood you correctly, but we called it a "trie" instead of a "DAWG". Those lectures are in the first module.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I think you understood me incorrectly since DAWG is suffix automaton...

              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Ah, OK. Sorry, this doesn't look like a very popular terminology, but maybe I'm missing some source. We don't have lectures on DAWG/Suffix Automaton indeed. The main reason is that (my perception is) Suffix Arrays and Suffix Trees are widely used in practice for exact and approximate pattern matching, while Suffix Automaton is a topic from competitive programming which is not widely used in practice, at least for now. It is also a rather advanced topic. Still, in the end, the learners can build both Suffix Array and Suffix Tree in O(n log n), which is not bad, I think.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I really like idea of having additional materials for the "Honors Track". It will allow this specialization to be relevant to an even wider audience. Also a student can deepen their understanding of the covered subjects over time by going back to the class and doing the additional problems.

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            We've already prepared the problems for the Honors Track for the first class, Algorithmic Toolbox, but we haven't launched it yet, need to decide on the format, how many problems to require and which ones to get a diploma with Honors. As we get some time between preparing the last two courses of the Specialization, we're going to launch this Honors Track and then also for the other classes.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Will we be taught how to implement these algorithms in c++ or just the theoretical aspects(with / without pseudocode)?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You will be taught with pseudocode which is sometimes explained in the lecture and sometimes provided only in the slides cause it's boring for the lecture, and then you will have to implement all the algorithms in one of the available languages (C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala) and submit them into automated testing system. There will be starter files in C++/Java/Python3, and for the other languages you'll have to implement the solution from scratch. There are also dedicated forum threads for each problem where the learners discuss their issues with the problems.

        We consider programming assignments the main distinguishing thing about our Specialization, because you only understand the algorithm if you've successfully implemented it, otherwise you can think you understand it, but most probably you don't fully understand it. However, you won't be taught the details of C++ or any other specific language implementations, you will have to work this out yourself. Some level of programming experience is expected, at the very least half a year, better a year of programming before starting with this Specialization.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you for the feedback and the good wishes!

»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Just went through some of the lectures. Daniel does a great job of explaining things. Looking forward to finishing it. Thanks and good luck to the team.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the feedback and for the good wishes!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, Data Structure and Algorithms Specialization at Coursera offers two capstones, one of them is about the Shortest Paths Capstone, however I only see information about Bioinformatics Capstone. Is it possible already to take the Shortest Paths Capstone? If I take the specialization right now I could choose that Capstone? Thank you very much.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Due to some technical restrictions, we cannot make the two Capstone Projects as separate courses, and so now it looks like there is only one project. There will be two projects inside to choose when we launch it. However, it will launch in September, currently we only have Algorithmic Toolbox and Data Structures courses launched, and Algorithms on Graphs course will be launched soon.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Algorithms on Graphs course starts on June 6, and you can still enroll.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wasn't the course titled Algorithms on Graphs and Trees earlier ?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It was, but it's too long a name. There is a module about spanning trees, but adding even more material would make the course too long.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Michael (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Worth Studying. Really Good Specialization at Coursera Thanks for your efforts for that

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This seems like a really amazing set of courses. I am looking forward to going through them in the coming months.

Unless I missed it, it doesn't seem like you cover the subject of interval/segment/BIT trees anywhere. Is this something that you could expand on in the future? Seems like a most fundamental subject as far competitive programming is concerned.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You're right, it's fundamental for competitive programming, but not nearly so in the real-world applications, that's why it's left out in the current version of the Specialization. We'll discuss it as well as other suggestions from this thread.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I figured that was the reason. I am just wondering, do you know what percentage of your user base is coming from an interest in competitive programming?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, unfortunately I don't know that, only very rough estimations. However, I assume that not a huge part for now, below 10%, as the primary audience of Specializations are working professionals seeking to grow and change job or get a promotion.

»
7 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

where can I find lectures of these courses?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    All the links are given in the post. You can go by link to the corresponding course, register and see the lectures. What is your question exactly?

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 5   Vote: I like it +1 Vote: I do not like it

      Is there a way to see lectures without enrolling to the course? as it requires payment. also link redirects to courses which are undergoing now (from oct 24). where can i find lectures of previous season?? (july)

      PS: i found the option to audit the course. sorry for asking stupid question

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes, as you've found out, it IS possible to audit the course without paying. This works only if you go by link to the specific course, not by the link to the whole Specialization. In this case you won't be able to submit problems.

        Also, the fact that the courses are undergoing now is not a problem, since new session starts every 2 weeks.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it +5 Vote: I do not like it

          I really liked the lectures so far. Would love to see some advance topics like flow algorithms. And some advanced data structures such as treaps.

          Thanks!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Michael (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Mr. Michael, I stumbled upon this specialization on coursera, and seems you're one of the instructors there. https://www.coursera.org/specializations/data-structures-algorithms

Can you tell me whether the 'Big Networks' project is a part of the specialization ? or is it only the 'Genome Assembly' capstone ? or both ? Also, can you link me to the final specialization certificate of any student who have completed the specialization ? Since its a paid course ( a great one, i agree :) ) , i would like to view a sample of the final specialization certificate, apart from the intermediate certificates.

Regards, Ryan

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Ryan, I am one of the learner of this course. It's a great course. I have completed 5 courses and currently on last Capstone Project. Certificates are issued each after one course. If you want to view certificates. Here is one link to my 5th course certificate.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Big Networks is an optional project at the end of the third course, Algorithms on Graphs. It is called Advanced Shortest Paths there. I don't have access to students'certificates, but see the comment from a learner above.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for creating this course. It is great! I just wish there were more learners that I could work with, I find the forums are often empty.

I love your lectures, very clear to understand with lots of good examples!

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow~~~~~~~~~~~! This is amazing!! Although I still have not started learning this course, I believe that this will help me a lot on algorithm design, especially how to think about a problem and how to find out breakthrough points. Thanks a lot for all your hard work and great contribution!! :D