Specialization in algorithms and data structures from Yandex, HSE, UC San Diego and CSC

What algorithms are using social networks to search for a friend graph? How do TV companies choose which ads to show in order to maximize profits? How to assemble a genome from millions of fragments? How to calculate the shortest path from New York to Mountain View thousands of times faster than classical algorithms do?

At Coursera, another useful specialization, created with the participation of Yandex, appeared - “ Algorithms and data structures ”. Among the teachers are not only representatives of Yandex, HSE, St. Petersburg Computer Science Center, but also lecturers at the University of California at San Diego, so this time all the courses specialize in English.


')
Only five of them, at the end of the listeners waiting for the final draft. One of them is associated with bioinformatics, the second - with finding the shortest paths in real road networks and graphs. In the format of specialization, all materials are available for free. Payment is required only if you want to send homework for verification and get a certificate. Then you will need to program and submit about 100 tasks to the testing system. You can do this in C, C ++, C #, Haskell, Java, JavaScript, Python2, Python3, Ruby and Scala.

Today begins the first course - Algorithmic Toolbox . Under the cat - a program of specialization, information about teachers and their opinion about who it will be useful for and why.

Teachers

Mikhail Levin. Yandex, Faculty of Computer Science, HSE. Head of Big Data Analysis Service Yandex Data Factory. She teaches the Algorithms and Data Structures course at the School of Data Analysis, participates in creating the curriculum at the Faculty of Computer Science at HSE and Yandex. Twice he won medals at ACM ICPC in the team of Moscow State University. Mv Lomonosov. Many on Habré remember Misha’s lecture on how mathematics helps Yandex to make money from advertising.

Algorithms and data structures are the basics of computer science, so this is a required course in any computer science program. They need to be known not only in order to create databases, distributed systems and storages themselves, but also to make such services as, for example, search or navigator. Algorithms are used in data science, an essential piece of machine learning is machine learning algorithms.

Our specialization differs from the course in the ShAD with a significantly lower entry threshold, less evidence (they are, but many are optional), a set of themes, a stronger focus on practical examples and modern applications, the presence of the Capstone Project.

This specialization will be useful to both programmers and researchers. First, she will help her to improve her skills in order to get an interview at a top technology company, learn how to solve more complex tasks and thereby get a promotion at work. But researchers, for example, will be able to use the computing power of a computer instead of processing the experiments with their hands.

Daniel Kane , University of California, San Diego . Associate Professor of CSE and the Department of Mathematics. Daniel teaches an introduction to algorithms. Among his research interests are various areas of mathematics and computer science theory, and most of the work concerns number theory, computational complexity, and combinatorics. Daniel Kane graduated from Harvard, received a PhD from MIT.

Algorithms are now used everywhere: in software development, genome analysis, traffic jams prediction, recommender systems. You run into algorithms just by using the internet. They are used in any area of ​​Computer Science, so the course on algorithms and data structures is the basic part of any CS program.

Pavel Pevzner, University of California, San Diego, Laboratory of Algorithmic Biology, SPbAU. Pavel graduated from the Fiztekh, now a professor at the Department of CSE in San Diego, where he has been teaching algorithms in bioinformatics for 12 years. In 2011, he participated in the founding of the Laboratory of Algorithmic Biology in St. Petersburg, which developed the Rosalind platform. In recognition of his scientific work, Pavel received the title of Full Member of ACM and ISCB.

Algorithms are everywhere! Each of the trillions of cells in your body performs entire complexes of still poorly studied algorithms. They are the keys to answering important biomedical questions about which mutations distinguish people from each other and how they are related to our diseases. In this specialization, besides the fact that you become familiar with the theory of algorithms, you will develop your own. They will have to solve problems like collecting the genome, the greatest puzzle, out of a million tiny fragments.

Neil Rhodes, University of California, San Diego, Google. He graduated from UCSD, studied Computer Science. At a time when he already received a Ph.D., he decided to leave the university and start developing his own company, Palomar Software. For over a decade, Neil Rhodes has taught courses in San Diego on algorithms, machine learning, discrete mathematics, and the theory of computability. He developed training programs for Apple and Palm employees. The last seven years has been a developer at Google.

It is very important that the algorithms we use are efficient. A person needs search results in the blink of an eye, even if the machine searches among billions of pages. A poorly thought-out algorithm can literally for centuries deal with pages indexed by search engines or all posts on Facebook. Continuous improvement of the algorithms is necessary to ensure that these services are usable. That is why technology companies always ask a lot of algorithmic questions at interviews.

Alexander Kulikov, Mathematical Institute. V.A. Steklov, Computer Science Center, Yandex. He graduated from St. Petersburg State University Mathematics, defended the degree of candidate of physical and mathematical sciences at the Steklov Mathematical Institute. His research interests are algorithms for NP-hard problems and circuit complexity. Alexander runs the Computer Science Center in St. Petersburg, which runs a branch of the Yandex Data Analysis School. Organizes in Russia conferences and student schools devoted to computer science.

Algorithms are needed in all sections of Computer Science, so questions about them are always in a technical interview. Curser already has two excellent courses on algorithms: one from Tim Rafgarden from Stanford, the second from Robert Sedgvik from Princeton. Our specialization compares favorably with them in that
in it a great emphasis is placed on the practical component. Everything
The students will need to implement the algorithms they have studied so that they work very quickly, even on large amounts of data. This will provide a deeper understanding of the algorithms, and valuable experience in writing and debugging fast and reliable programs. The second advantage of our specialization is more banal - it has more material.

To get to it, you need to have basic mathematical preparation (proof by induction, proof by contradiction), programming experience (C, C ++, C #, Haskell, Java, JavaScript, Python2, Python3, Ruby or Scala), to present how to work with lists / arrays and how recursion works. Specialization will be useful to any programmer who wants to become more popular and learn how to solve more complex problems.

Program

Specialization consists of five courses and a final project.

1. Algorithmic Toolbox

The first course is about algorithms that one cannot but know, and tasks that often arise in practice: sorting and searching, the divide and conquer approach, greedy algorithms, dynamic programming. Students learn when it makes sense to use greedy algorithms and how dynamic programming is used in the study of the genome. You can practice creating new algorithms and their effective implementation (so that they work in less than a second).

2. Data Structures

Efficient algorithms almost always use efficient data structures. This course will cover the main ones that can be used to solve various problems. Let's start with the basic structures: arrays, queues, stacks, trees; discuss what situations they should use. Then we will consider two ways to implement dictionaries - using hash tables and binary search trees. These structures are commonly used in programming languages ​​and databases. In practice, almost any nontrivial program uses hash tables or search trees in some way. And although these structures are usually implemented in programming language libraries, it is important to understand their strengths and weaknesses in order to use them effectively in their programs and to be able to extend existing implementations.

In addition, in this course, you will learn how Yandex.Disk manages to save a lot of space and why sometimes uploading a large file to Dropbox happens almost instantly; Get acquainted with the principles of building distributed hash tables used to store large data.

Finally, the course will look at data structures that allow you to perform queries like "retrieve the minimum element" or "check whether two elements belong to the same set."

3. Algorithms on Graphs

If you have ever launched a navigator to build a route or find out the approximate travel time, then you used algorithms on graphs. Graphs appear in a variety of realities: road networks, computer networks and, more recently, in social networks. If you are looking for a quick way to get to work, the cheapest way to connect several computers to a network or an effective way to find popular people on Facebook, you will have to work with algorithms on graphs.

In this course, you will learn what graphs are, what properties they possess, learn how to bypass them, and find out where it can be useful. We consider the shortest path search algorithms: from the simplest to those used in various navigation services. You will need the latter in the implementation of the final project, if you choose a project on the shortest paths. The course ends with a discussion of minimum spanning trees, which are used in the design of road, telephone and computer networks and are used in clustering algorithms.

4. Algorithms on Strings

From the point of view of Computer Science, all the text that surrounds us is a string. To create an effective search for it, developers are actively using algorithms on strings. They are used in medicine: with their help, researchers find mutations in the human genome that cause certain diseases. Algorithms on the lines will be devoted to the fourth course of our specialization.

5. Advanced Algorithms and Complexity

The study of the basic algorithms will be completed by this time, and we will move on to the advanced ones. The course will begin with streams in networks and their application - both obvious (search for optimal matching, non-intersecting paths, scheduling) and more unexpected (segmentation of images in computer vision, search for dense clusters in graphs). Next we will deal with linear programming for solving the problems of creating the optimal budget, searching for the cheapest diet according to given parameters, routing calls in telecommunications, etc.

After that, difficult tasks will remain, a good solution for which is not found and, most likely, will not be found. Listeners will learn how to solve them in practice. In the final, we will talk about the application of algorithms in big data and machine learning.