Coursera Algorithms Course (4-6 weeks of study)

As promised, I am writing a continuation of an article on training in the Algorithms course.

Those who do not know the structure of the course, I ask in the first article, there I painted how the work goes. Here I will talk about the program of the final 3 weeks of study and the final exam.

Week 4

• Priority Queues. Priority queues, their basic operations are considered, the complexity of each of them is estimated. Considers the implementation of the queue through the binary heap (Binary Heap), as well as sorting based on this data structure (Heap Sort).
• Elementary Symbol Tables (symbol tables). This chapter is devoted to “symbol tables” (excuse me for such a direct translation), in other words, storing key-value pairs. The basic operations and their complexity in the implementation of symbol tables through a linked list and through a binary tree are considered. In my opinion, this chapter can also be considered as an excellent guide to binary trees and the operations performed on them. By and large, it’s not so important what we store in them, the chapter could very well be called Elementary Symbol Tables and BST.
• As a practical task, it will be proposed to implement a program for finding a solution to the game "tag."

Week 5

• Balanced Search Trees (balanced search trees, again I apologize for the direct translation, maybe not search trees, but binary trees). Probably one of the most useful chapters in the entire course. A red-black tree is considered, one of the fundamental data structures. It is considered in great detail and intelligibly, the analysis begins with 2-3 trees, and then, as their development, a red-black tree is considered. To his surprise, he learned that the author of the course, Robert Sedzhevik, had a direct hand in creating a red-black ebony in the form in which we know it.
• Geometric Applications of BSTs (application of binary trees for solving geometric problems). This section was a revelation for me, if everything that was considered earlier, I knew to one degree or another, then almost everything was new here, especially kd-trees - a very interesting data structure. In general, the possibility of using binary trees to find whether a set of points (or points) on the plane belongs to another set of points (segment or rectangle) is considered. Considers such varieties of binary trees as the KD tree and the Interval Search Tree.
• For a practical task, it is proposed to implement the search for the nearest point on the plane and the belonging of a point on the plane to a given rectangle using a kd-tree.

Week 6

• Hash Tables (hash tables). As the name suggests, the chapter focuses on hash tables. The first lecture is devoted to hash functions, as well as how to implement hash functions in java. Then the conversation goes about the hash tables themselves: their implementation is considered, an assessment of the complexity of the operations is performed. Much attention is paid to methods for resolving hash collisions in a hash table. One of the methods is known to all and is based on lists for each value of the hash function, the second method, for example, was also a discovery, I had never seen this before (one linked list is used to store all values).
• In the last week of the course there is no practical task, instead there is a final exam.

Final exam
I must say, the final exam is quite a difficult thing. 20 questions, many of which are open, i.e. no answer options (for example, write an array of numbers after the n-step of the specified sorting has been performed on it). Most of the questions were already in the previous exercises of the course, but there are several new types of tasks. For example, several statements or questions are given, as well as several answers are given, it is necessary to compare the answers with the corresponding statements. The task is complicated by the fact that each of the options can be used for 1 or more statements or not used at all. Or another example: 10 arrays of words are given and the initial array is indicated, it is necessary to determine the intermediate state of which sorting this or that array is (the task did it pretty well for me, and since I decided to do it last,

Three attempts are given for the final exam, the best will be counted (unfortunately, I had free time for the exam just before the final deadline, so I had only one attempt). In time, you need to focus on 2-3 hours of work in a calm environment, attentiveness and accuracy are very important. Two tasks were overwhelmed for me simply because I did not correctly transfer the final answer from the paper to the input field: in one task I did not add the last element of the array, in the other I wrote 92 instead of the number 90 instead of the number 90. You can type in the final exam maximum 20 points, I was able to score 14.77 out of 20, although, as I wrote above, just being a little more attentive, I could get 16-17 points. Unfortunately, after the final test, there was no calculation of the total grade for the course (or maybe I just did not find it?), although scoring for exercises and practical tasks suggested the existence of a final grade. If you take the entire course responsibly from beginning to end, then the final test will not cause difficulties.

On the whole, I liked the course very much, learned a lot of new things and brought my disparate knowledge into a single system. Already signed up for the second part of this course announced in November. For those who have not yet listened to the first part, I highly recommend it. Unfortunately, the site does not yet have an exact start date for the course, but you can subscribe and receive a notification of its start.

Links:
Сoursera website - www.coursera.org
Course "Algorithms. Part 1 "- www.coursera.org/course/algs4partI
Course" Algorithms. Part 2 ”- www.coursera.org/course/algs4partII