Lectures Technopark. The course "Algorithms and data structures" (autumn 2016)

Today we present to your attention one of the latest courses of Technopark - “Algorithms and data structures”. It is a study of the basic algorithms and data structures needed by programmers for the qualitative solution of daily tasks. The course provides algorithms for working with arrays, sorting. It tells about elementary data structures: stack, queue, lists, heap. The program also includes various search trees and hash tables. The course gives an idea of ​​how to evaluate the effectiveness of the algorithms, all the algorithms of the course are evaluated by the time of work and the amount of additional memory used. You are waiting for six lectures:

• “Introduction. Artists. Interface abstractions. Recursion;
• "Greedy Algorithms";
• "Sort";
• "Search. Lists;
• "Trees";
• Hash tables.

Four lectures of the course are given by Stepan Matskevich, the head of the ontological information extraction group at ABBYY. He was the lead programmer when writing the server part of the ABBYY InfoExtractor product based on the ABBYY Compreno technology (text analysis and translation).

Two more lectures are led by Georgy Ivanov, the developer of Mail.Ru Search, dealing with the tasks of processing search queries.

Lecture 1. “Introduction. Arrays "

Introduction to the course: the definition of the algorithm, data structure, efficiency of the algorithm. Algorithms for calculating the n-th Fibonacci number. The problem of checking whether a given positive integer n is simple is solved. It tells about the rapid construction of a number to an integer power.

Arrays, single-pass algorithms, linear and binary search are considered.

Part of the lecture is devoted to abstract data types, the Dynamic Array data structure. In conclusion, we will focus on the depreciated time of adding the item.

Lecture 2. “Lists, stack, queue, dek. Dynamic programming and greedy algorithms »

The second lecture is devoted to the basic data structures: unidirectional and bidirectional lists, abstract data types (stack, queue, decks) and methods for their implementation. The topics of dynamic programming and greedy algorithms (change of coins, covering with segments, the task of a backpack) will be touched upon.

Lecture 3. "Sorting"

Georgy Ivanov gives a lecture about sorting. We are talking about different simple types of sorting (selection, inserts, bubble and pyramidal), methods for their improvement, quality assessment. The second half of this lecture is devoted to merge sorting and quick sorting, ordinal statistics, sorting without comparisons.

Lecture 4. “Sorting (part 2). Ordinal statistics.

The second part of the lecture about sorting from George Ivanov. Quick sorting, sorting hoar, sorting by counting. In addition, a median search algorithm is considered. An answer is given to the question of how in real conditions they speed up the quick sort algorithm. A table of sorting comparison is given. George completes the lecture with a story about bit sorting algorithms.

Lecture 5. "Hash tables and Huffman code"

An explanation is given of what a hash function is, what a hash table is and how to build it. How to resolve collisions arising from the use of hash functions, and by what method (chains or open addressing, which uses double hashing). At the end, a dynamic hash table and a table for collision resolution comparison methods are considered.

Lecture 6. “Trees”

The last lecture on algorithms is devoted to several different types of trees at once: binary search trees (to create an associative array) and problems of their balancing, Cartesian trees, AVL-trees. Stepan Matskevich ends the lecture with examples of implementing the “Associative array” data type using trees and hash tables comparing the advantages of each option.

Playlist of all lectures is on the link . Recall that current lectures and master classes on programming from our IT specialists in Technopark, Technosphere and Tehnotrek projects are still published on Tekhnostrim channel.