Course Algorithms from Coursera (1-3 weeks of study)

A month ago, several times on Habré, articles about the wonderful resource Coursera, where you can take courses in various areas, skipped. Among other things, I was very interested in the course “Algorithms” (part 1), which I signed up for and began to study it. Now the course is nearing completion, and I decided to write a small report on the first part of the course (I hope I’ve had enough to describe the second part of the course upon its completion), so that the respected% username% can determine whether to sign up for the next course iteration or not.

I must say that shortly before the start of the course I didn’t show myself very well during the interview with Odnoklassniki on the traditional point of all developer vacancies - “Confident / Good / Excellent knowledge of algorithms”, this became an additional incentive to start studying this course. I note that I had previously studied the algorithms in the framework of the subject “Data Structures” at the institute, and so later occasionally in the framework of the next 4 years of work. In general, pieces of knowledge: somewhere good, even with in-depth preparation for interviews, and somewhere gaps.

So, first, a little about how the course is built. Course duration 6 weeks. Every week there are open lectures on two topics (for each topic there are 4-6 lectures for 10-20 minutes). Having listened to lectures, tests for each of the topics are performed to consolidate, as well as one practical exercise - a Java program, for the implementation of an applied task. For each of these verification works, points are awarded (I don’t know where they will go, I suspect that at the end of the course they will be processed into the final grade). Additionally, there are questions on the topic studied that can be asked at interviews (there are no grades, just for general development).

Now a little about what topics will be covered in the first 3 weeks of the course (the whole course is in English and for some topics I am not sure that I know the adequate Russian name).
')
Week 1

• Union-Find: the problem of determining whether an element belongs to a specific set of elements, as well as the operation of combining elements is considered. In fact, the conversation is about trees and the search for the belonging of an element to a specified subtree and about adding an element to a specified subtree. The pros and cons of solving this problem in practice through an array and through a linked list are considered.
• Analysis of Algorithms: consider the concepts of algorithm complexity, the best, worst, and average cases of the algorithm, methods for estimating the time of the algorithm, as well as a way to calculate the memory consumption by data structures in Java.
• As a practical task, it is proposed to implement the solution Percolation task. Unfortunately, I don’t know how to correctly translate this task into Russian (in the comments they suggest that this task is called “Percolation”), so I’ll put the point on the fingers: a two-dimensional array of cells is given, each of which can be turned on / off, after activating the next cell you need determine if there is a path connecting the top and bottom rows of the matrix.

Week 2

• Stacks and Queues: as the name implies, these data structures and their practical implementation based on arrays and lists are considered, as well as an estimate of the time complexity of performing basic operations when implemented on these data structures. Separately, time is given to things like iterators and generics in Java.
• Elementary Sorts (simplest sort): consider sorting by selection, sorting Shell and sorting inserts, evaluation of their time complexity. Additionally, the problem of "mixing" elements is considered. The problem of constructing a convex closed polygon covering a set of points in a plane (Convex Hull) is considered.
• For practice, it was proposed to implement the data structures of decks and the “bag” (bag).

Week 3

• Mergesort (merge sorting): a lot of time is spent on merge sorting, or rather two ways to implement it and assess their time complexity. The concept of “stability of sorting” is considered as a bonus, as well as comparators in Java are considered separately.
• Quicksort (quick sort): here everything is repelled by quick sort. Practical implementation, assessment of its time complexity. Additionally, the problem of “sampling” of elements (for example, the largest element) from a variety of elements is considered, and attention is also paid to how embedded sorts are implemented in Java.
• In practice, they will be asked to solve the problem of finding collinear points on a plane.

Here is the first 3 weeks of study. I liked that all topics are considered not in a spherical vacuum, but with the implementation in Java, this makes the “Algorithms” course even more fun, it distracts from formulas (by the way, they are not very loaded). I liked the “interspersing” of small fragments about some features of Java (despite the experience of developing in Java, I still learn some new nuances). And still satisfied with a big plus, the need to regularly sit down at lectures: the deadlines and on practical tasks, and on the course as a whole, force us not to postpone the study of the material for “later”.

At the end I will add only that the lectures are in English, but with subtitles (I think there are Russian subtitles only in the first lecture), so it’s not necessary to understand English well by ear, but technical English is necessary.

And finally, I ask you once again to forgive for some “clumsiness” of the translation of those lectures, it is quite possible for some terms there are generally accepted Russian counterparts, which I do not know about. I will be glad to comment.

References:
Sourcesera website - www.coursera.org
Course "Algorim. Part 1 "- www.coursera.org/course/algs4partI