Course Algorithms from Coursera (4-6 weeks of study)

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

Those who do not know the structure of the course, please in the first article, there I described 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. Queues with priority, their basic operations are considered, the complexity of each of them is evaluated. It considers the implementation of a queue through a binary heap (Binary Heap), as well as sorting based on this data structure (Heap Sort).
• Elementary Symbol Tables (symbolic tables). This chapter is devoted to "character tables" (sorry for such a direct translation), in other words the storage of key-value pairs. The basic operations and their complexity in the implementation of symbolic tables through a linked list and through a binary tree are considered. In my opinion, this chapter can also be viewed as an excellent guide to binary trees and operations performed on them. By and large, it is not so important that we store in them, the chapter could well have been 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, it is possible that binary trees are not the correct ones). Probably one of the most useful chapters for the entire course. Considered a red-black tree, one of the fundamental data structures. It is considered in great detail and intelligibly, analysis begins with 2-3 trees, and then, as their development, the red-ebony tree is viewed. To my surprise, I learned that the author of the course, Robert Sejevik, had directly put his hand to creating a red-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 to me, if I knew everything that was previously considered, to some extent, then here everything was new, especially kd-trees - a very interesting data structure. In general, the possibility of using binary trees to search for belonging of a set of points (or points) on a plane to another set of points (a segment or a rectangle) is considered. Considers such varieties of binary trees as the KD-tree and the Interval Search Tree.
• For the practical task, it was proposed to search for the nearest point on the plane and the point on the plane to belong to a given rectangle using the kd-tree.

')
Week 6

• Hash Tables (hash tables). As the name implies, the chapter is devoted to 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, the complexity assessment is performed, and we perform operations. Much attention is paid to how to resolve the hash collisions in the 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 for me, was also a discovery, I have not seen such a thing before (one linked list is used to store all values).
• There is no practical assignment for the last week of the course, there is a final exam instead.

Final exam
I must say, the final exam is quite a difficult thing. 20 questions, many of which are open, i.e. no answer choices (for example, write an array of numbers after performing an n-step on the specified sorting). 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, several answers are also 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 at all. Or another example: 10 arrays of words are given and the original array is indicated, it is necessary to determine the intermediate state of which sorting is one or another array (the task is pretty tense for me, and since I decided to do it last, I didn’t have enough time to spit and put some options at random).

Three attempts are given for the final exam, the best will be credited (unfortunately, I had free time for the exam just before the final deadline, so I had only one attempt). By the time you need to focus on 2-3 hours of work in a relaxed atmosphere, attentiveness and accuracy are very important. I had two tasks filled up simply because I did not correctly transfer the final answer from the paper to the input field: I didn’t add the last element of the array in one task, and wrote 92 in the other because of several corrections on paper. a maximum of 20 points, I managed to score 14.77 out of 20, although, as I wrote above, just being a little more attentive could get 16-17 points. Unfortunately, after the final test, the calculation of the overall grade for the course was not made (or maybe I just did not find it?), Although scoring for the exercises and practical tasks suggested that there was a final grade. If you responsibly take the whole course from the beginning to the end, then the final test will not cause difficulties.

In general, I liked the course very much, learned a lot of new things and brought together my scattered knowledge to a single system. Already enrolled in the second part of this course announced for November. For those who have not listened to the first part, I highly recommend. Unfortunately, the site does not have the exact start date of the course, but you can subscribe and get a notification about its beginning.

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