Блог пользователя Michael

Автор Michael, история, 9 лет назад, По-русски

Мы в прошлом году выиграли в конкурсе заявок и в этом году запустили специализацию по алгоритмам на Coursera, которая в результате является на этой платформе основным способом изучения алгоритмов и структур данных. Специализация — это не один курс, а целая последовательность курсов, заканчивающаяся Capstone Project, что позволяет изучить предмет значительно глубже, чем это обычно получается в рамках массового онлайн-курса.

Мы — это University of California, San Diego (11 место в мире по Computer Science) и ФКН ВШЭ:

  1. Daniel Kane — профессор в UCSD, закончил Гарвард, получил PhD в MIT, четырежды победитель Putnam competition (американская студенческая олимпиада по математике), про него даже есть страница в википедии.
  2. Павел Певзнер — профессор в UCSD, последние 12 лет преподает там алгоритмы и биоинформатику, является автором специализации по биоинформатике на Coursera, по материалам которой в десятках ВУЗов во всем мире сейчас преподают биоинформатику, является одним из основателей Лаборатории алгоритмической биологии в Санкт-Петербурге, которая разработала платформу Rosalind.
  3. Neil Rhodes — лектор в UCSD — в прошлом Staff Software Engineer в Гугле, преподает последние 10 лет, разрабатывал программы обучения для Apple.
  4. Александр Куликов — visiting professor в UCSD, научный сотрудник ПОМИ РАН, директор Computer Science Center и координатор Computer Science клуба в Санкт-Петербурге.
  5. Михаил Левин — Chief Data Scientist в Yandex Data Factory, преподаватель курса алгоритмов в ШАДе, куратор программы ПМИ на ФКН ВШЭ.

Одна из главных "фишек" специализации — большое количество задач, позволяющих по-настоящему разобраться в алгоритмах: ведь всем вам хорошо известно, что пока не начнешь писать задачу, только кажется, что решил ее правильно и полностью понимаешь. Дело обстоит точно так же и с отдельными алгоритмами и структурами данных. Всего в специализации порядка 70 алгоритмических задач, многие из которых подготовили Burunduk1, Gassa, GlebsHP, ifsmirnov, ilyakor, nk.karpov, Perlik, romanandreev, tourist, Zlobober, Павел Мельничук и Руслан Савченко.

В рамках Capstone Project специализации вы сможете заняться либо алгоритмами поиска кратчайших путей на реальных графах дорог и социальных сетей, которые работают на практике в тысячи раз быстрее классических алгоритмов, либо алгоритмами биоинформатики, с помощью которых собирают геном из миллионов фрагментов.

Конечно, если вы красный или сильно желтый, вероятно, вы узнаете не очень много нового. Тем не менее, процитирую некоторые из отзывов на нашу специализацию, связанные со спортивным программированием:

"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. Если вы не хотите сдавать задачи и получить сертификат, чтобы посмотреть видео лекции и прочитать readings, нужно пройти по ссылке на конкретный курс, например, Algorithmic Toolbox, и выбрать опцию "Audit only". Второй курс специализации — Data Structures — запустился в апреле. Остальные три курса пока не запущены, ближайший — Algorithms on Graphs — запускается в начале июня, следующий — Algorithms on Strings — в начале июля, последний — Advanced Algorithms — в начале августа.

UPD.2 Задачи можно сдавать на одном из следующих языков: C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala.

UPD.3 Курс по графам стартует 6-го июня, еще можно записаться.

UPD.4 Курс по строкам стартует 25-го июля, уже можно записываться.

UPD.5 Курс по продвинутым алгоритмам и теории сложности стартовал, про него я собираюсь написать отдельный пост.

UPD.6 Финальный проект по сборке генома стартовал, а проект по продвинутым алгоритмам поиска кратчайших путей, включающий Contraction Hierarchies, стал опциональным модулем в конце курса по алгоритмам на графах.

Всем привет из Тайланда!

  • Проголосовать: нравится
  • +229
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Затея класс! Сколько стоят услуги вашего кофеноса?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Я пока не понял: вам кофеноса одолжить, или вы хотите нам с чем-нибудь помочь?)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      или вы хотите нам с чем-нибудь помочь?)

      зачем вам второй?)

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится

        Ну так много не бывает, тем более ты парень опытный в этом вопросе

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          о, вот и он сам пожаловал. не такой опытный, как ты

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится -8 Проголосовать: не нравится

            Ну разумеется не такой, я ведь носил, а не ты

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Нужно больше задач

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Why no Ukkonen?

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                8 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thank you for the feedback and the good wishes!

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where can I find lectures of previous semester. without registering for this sem?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

where can I find lectures of these courses?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          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!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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