March 1, 2015 at 16:23Lectures of the Technopark. 1 semester. Algorithms and data structures
- Tutorial
Another post as part of our Technopark lecture series . This time we bring to your attention a course on algorithms and data structures. The course was written by Stepan Matskevich, an employee of ABBYY.
The beginning of the first lecture is devoted to a discussion of the basic concepts on which the entire further course program is built: what is an algorithm and data structure. The basic types of algorithms, their characteristics and analysis methods are described. The following are examples of creating algorithms for calculating Fibonacci numbers, checking the number for simplicity, quickly raising a number to an integer. At the end of the lecture, we talk about the features of using algorithms for working with arrays: the creation of single-pass algorithms, the search for a minimal element, and binary search.
The second lecture is devoted to the study of elementary data structures. At the beginning, a definition of the concept of "abstract data type" is given. Further, the lecturer talks about what depreciation analysis is and what its features are.
Such types of structures and abstract data types are considered as:
The disadvantages and advantages of each type of structure are analyzed, as well as their implementation in the form of program code.
The topic of sorting was so voluminous that it had to be divided into two lectures. The first part discusses in detail such types of algorithms as:
It describes how you can evaluate 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 application:
Finally, a comparative analysis of different algorithms is carried out.
In this lecture, you will first learn what a hash search method is and what hash functions are (including hash functions of strings). Then comes a detailed review of hash tables and how to use them: 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 the time and memory costs is made.
The last lecture in the course of A&D course is devoted to such data structures as trees. Of course, at the beginning of the lecture a definition of the concept of “trees” is given, their characteristics are considered and examples are given. Then you will learn how the trees are represented in memory, what are the ways to traverse the tree. Next, we consider the so-called binary search trees and a group of self-balancing trees: Cartesian and AVL trees. And at the end of the lecture, the “associative array” abstract data type is described.
Lecture 1. Fundamentals
The beginning of the first lecture is devoted to a discussion of the basic concepts on which the entire further course program is built: what is an algorithm and data structure. The basic types of algorithms, their characteristics and analysis methods are described. The following are examples of creating algorithms for calculating Fibonacci numbers, checking the number for simplicity, quickly raising a number to an integer. At the end of the lecture, we talk about the features of using algorithms for working with arrays: the creation of single-pass algorithms, the search for a minimal element, and binary search.
Lecture 2. Elementary data structures
The second lecture is devoted to the study of elementary data structures. At the beginning, a definition of the concept of "abstract data type" is given. Further, the lecturer talks about what depreciation analysis is and what its features are.
Such types of structures and abstract data types are considered as:
- array and dynamic array;
- stack, queue and deck;
- priority queue;
- linked lists: unidirectional and bidirectional;
- binary heap.
The disadvantages and advantages of each type of structure are analyzed, as well as their implementation in the form of program code.
Lecture 3. Sorting (part 1)
The topic of sorting was so voluminous that it had to be divided into two lectures. The first part discusses in detail such types of algorithms as:
- sorting of one, two and three elements;
- sort by selection;
- sorting by inserts;
- bubble sorting;
- quick sort Hoar.
It describes how you can evaluate 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 application:
- merge sort, including two ordered arrays;
- counting sorting;
- bitwise sorting;
- pyramidal sorting and a number of others.
Finally, a comparative analysis of different algorithms is carried out.
Lecture 5. Hash tables
In this lecture, you will first learn what a hash search method is and what hash functions are (including hash functions of strings). Then comes a detailed review of hash tables and how to use them: 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 the time and memory costs is made.
Lecture 6. Trees
The last lecture in the course of A&D course is devoted to such data structures as trees. Of course, at the beginning of the lecture a definition of the concept of “trees” is given, their characteristics are considered and examples are given. Then you will learn how the trees are represented in memory, what are the ways to traverse the tree. Next, we consider the so-called binary search trees and a group of self-balancing trees: Cartesian and AVL trees. And at the end of the lecture, the “associative array” abstract data type is described.