Мы в прошлом году выиграли в конкурсе заявок и в этом году запустили специализацию по алгоритмам на Coursera, которая в результате является на этой платформе основным способом изучения алгоритмов и структур данных. Специализация — это не один курс, а целая последовательность курсов, заканчивающаяся Capstone Project, что позволяет изучить предмет значительно глубже, чем это обычно получается в рамках массового онлайн-курса.
Мы — это University of California, San Diego (11 место в мире по Computer Science) и ФКН ВШЭ:
- Daniel Kane — профессор в UCSD, закончил Гарвард, получил PhD в MIT, четырежды победитель Putnam competition (американская студенческая олимпиада по математике), про него даже есть страница в википедии.
- Павел Певзнер — профессор в UCSD, последние 12 лет преподает там алгоритмы и биоинформатику, является автором специализации по биоинформатике на Coursera, по материалам которой в десятках ВУЗов во всем мире сейчас преподают биоинформатику, является одним из основателей Лаборатории алгоритмической биологии в Санкт-Петербурге, которая разработала платформу Rosalind.
- Neil Rhodes — лектор в UCSD — в прошлом Staff Software Engineer в Гугле, преподает последние 10 лет, разрабатывал программы обучения для Apple.
- Александр Куликов — visiting professor в UCSD, научный сотрудник ПОМИ РАН, директор Computer Science Center и координатор Computer Science клуба в Санкт-Петербурге.
- Михаил Левин — 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, стал опциональным модулем в конце курса по алгоритмам на графах.
Всем привет из Тайланда!
Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).
Great work! Roughly speaking, what rating range is the course (and the problems) targeted towards?
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.
Also note that you can submit problems in one of the following languages: C, C++, Java, Python2, Python3, C#, Haskell, Javascript, Ruby, Scala.
I wish we could atleast submit the assignments without having to buy the course :/
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.
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.
Where I can find the option "Audit only" for the other 4 courses ?
First two courses — Algorithmic Toolbox and Data Structures have already launched, and you can go directly to those courses. Three other 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.
I got it, thanks !
Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).
Затея класс! Сколько стоят услуги вашего кофеноса?
Я пока не понял: вам кофеноса одолжить, или вы хотите нам с чем-нибудь помочь?)
зачем вам второй?)
Ну так много не бывает, тем более ты парень опытный в этом вопросе
о, вот и он сам пожаловал. не такой опытный, как ты
Ну разумеется не такой, я ведь носил, а не ты
Нужно больше задач
Auto comment: topic has been updated by Michael (previous revision, new revision, compare).
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!
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.
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!
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.
Thanks for the feedback: I'll try to think specifically about giving intuition.
The course Algorithms on Strings starts on July 25, you can enroll already.
Why no Ukkonen?
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.
Hm, why there are no lectures about DAWG by the way? The same reason?
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.
I think you understood me incorrectly since DAWG is suffix automaton...
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.
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.
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.
This is Awesome news, thank you!
Will we be taught how to implement these algorithms in c++ or just the theoretical aspects(with / without pseudocode)?
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.
Thank you for the feedback and the good wishes!
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.
Thank you for the feedback and for the good wishes!
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.
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.
Algorithms on Graphs course starts on June 6, and you can still enroll.
Wasn't the course titled Algorithms on Graphs and Trees earlier ?
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.
Auto comment: topic has been updated by Michael (previous revision, new revision, compare).
Worth Studying. Really Good Specialization at Coursera Thanks for your efforts for that
Thank you for your kind feedback!
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.
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.
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?
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.
Автокомментарий: текст был обновлен пользователем Michael (предыдущая версия, новая версия, сравнить).
where can I find lectures of previous semester. without registering for this sem?
where can I find lectures of these courses?
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?
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
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.
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!
Auto comment: topic has been updated by Michael (previous revision, new revision, compare).
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
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.
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.
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!
Thank you!
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