Lectures Technopark. 1 semester Algorithms and data structures
Another post within our series of lectures Technopark . This time we offer you a course dedicated to algorithms and data structures. The author of the course is Stepan Matskevich, an employee of ABBYY.
The beginning of the first lecture is devoted to the discussion of the basic concepts on which the whole further course program is built: what is the algorithm and data structure. The basic types of algorithms, their characteristics and methods of analysis are described. The following are examples of creating algorithms for calculating Fibonacci numbers, checking the number for simplicity, quickly raising the number to an integer power. At the end of the lecture, the features of using algorithms for working with arrays are described: the creation of single-pass algorithms, the search for the minimum element, and the binary search.
The second lecture is devoted to the study of elementary data structures. The beginning of the definition of the concept of "abstract data type." Further, the lecturer tells about the depreciation analysis and what are its features.
')
The following types of structures and abstract data types are considered:
The drawbacks and advantages of each type of structures, as well as their implementation in the form of program code, are analyzed.
The topic of sorting was so voluminous that it had to be divided into two lectures. In the first part, the following types of algorithms are discussed in detail:
It describes how to estimate the speed of a particular sorting algorithm, how to analyze the algorithms by the number of comparisons, etc.
This lecture discusses other types of algorithms and their applications:
Finally, a comparative analysis of different algorithms.
In this lecture, you will first learn what a search method is hashing, which hash functions are (including hash functions of strings). Then there is a detailed review of hash tables and methods of their use: what they are, what are the main methods for resolving collisions (the chaining method and the open addressing method), as well as methods for inserting, deleting and searching for elements. Finally, a comparison of hash tables for time and memory costs.
The last lecture in the course of the course is devoted to data structures such as trees. Of course, at the beginning of the lecture, the definition of the notion “trees” is given, their characteristics are considered and examples are given. Then you will learn how trees are represented in memory, what are the ways to bypass the tree. Further, the so-called binary search trees and a group of self-balancing trees are considered: Cartesian and AVL-trees. And at the end of the lecture, the abstract data type “associative array” is described.
Lecture 1. Basics
The beginning of the first lecture is devoted to the discussion of the basic concepts on which the whole further course program is built: what is the algorithm and data structure. The basic types of algorithms, their characteristics and methods of analysis are described. The following are examples of creating algorithms for calculating Fibonacci numbers, checking the number for simplicity, quickly raising the number to an integer power. At the end of the lecture, the features of using algorithms for working with arrays are described: the creation of single-pass algorithms, the search for the minimum element, and the binary search.
Lecture 2. Elementary data structures
The second lecture is devoted to the study of elementary data structures. The beginning of the definition of the concept of "abstract data type." Further, the lecturer tells about the depreciation analysis and what are its features.
')
The following types of structures and abstract data types are considered:
- array and dynamic array;
- stack, queue and deck;
- priority queue;
- linked lists: unidirectional and bidirectional;
- binary heap.
The drawbacks and advantages of each type of structures, as well as their implementation in the form of program code, are analyzed.
Lecture 3. Sorting (part 1)
The topic of sorting was so voluminous that it had to be divided into two lectures. In the first part, the following types of algorithms are discussed in detail:
- sorting of one, two and three elements;
- sort by choice;
- sorting inserts;
- bubble sorting;
- quick sort of hoar.
It describes how to estimate the speed of a particular sorting algorithm, how to analyze the algorithms by the number of comparisons, etc.
Lecture 4. Sorting (part 2)
This lecture discusses other types of algorithms and their applications:
- merge sorting, including two ordered arrays;
- sorting by count;
- bitwise sorting;
- pyramidal sorting and a number of others.
Finally, a comparative analysis of different algorithms.
Lecture 5. Hash tables
In this lecture, you will first learn what a search method is hashing, which hash functions are (including hash functions of strings). Then there is a detailed review of hash tables and methods of their use: what they are, what are the main methods for resolving collisions (the chaining method and the open addressing method), as well as methods for inserting, deleting and searching for elements. Finally, a comparison of hash tables for time and memory costs.
Lecture 6. Trees
The last lecture in the course of the course is devoted to data structures such as trees. Of course, at the beginning of the lecture, the definition of the notion “trees” is given, their characteristics are considered and examples are given. Then you will learn how trees are represented in memory, what are the ways to bypass the tree. Further, the so-called binary search trees and a group of self-balancing trees are considered: Cartesian and AVL-trees. And at the end of the lecture, the abstract data type “associative array” is described.
Source: https://habr.com/ru/post/251561/
All Articles