Lectures of the Technosphere. Preparatory course "Algorithms and data structures" (spring 2016)

The purpose of this course is to introduce students to the basic algorithms used for software development. You will learn how to choose the appropriate data structures and algorithms for the implementation of emerging problems, and learn how to use C / C ++ languages ​​for the implementation of algorithms.

The course is taught by Sergei Babichev, an associate professor of the departments of computer science and computational mathematics, as well as theoretical and applied computer science at the Moscow Institute of Physics and Technology. Under the cut, you will find eight lectures:
')

• Lecture 1. “Introduction. Artists. Interface abstractions. Recursion
• Lecture 2. "Greedy algorithms"
• Lecture 3. "Sorting"
• Lecture 4. “Search. Lists
• Lecture 5. "Trees"
• Lecture 6. "Hash tables"
• Lecture 7. "Dynamic programming"
• Lecture 8. "Algorithms on graphs"

Lecture 1. “Introduction. Artists. Interface abstractions. Recursion



In the first lecture, we recall the basics of the algorithms and see how they can be used in practice. Let's talk about the properties of algorithms, performers, notations, parameters and complexity classes. Let us analyze the non-polynomial problem (how many items will fit in a backpack). In addition, let's talk about abstractions (array, stack, set) and recursion (main theorem).

Lecture 2. "Greedy algorithms"



The lecture is dedicated to different algorithms for finding optimal (or close to optimal) solutions for a wide variety of tasks. Let's look at an approximate solution of the problem of finding optimal values. Let us analyze the abstraction of a character string, a prefix function, dynamic data structures.

Lecture 3. "Sorting"



Information about different sorting and about sorting activities. Several sorting technologies will be considered: comparison, fast, using the properties of elements, external and others. A comparison of the sorts when and which method should be used is also given.

Lecture 4. “Search. Lists



We are engaged in search, work with dynamic data structures, work with lists and trees. We carry out a comparative analysis of search methods: a simple sequential search, distributing a search, a search with a narrowing of the zone. In addition, let's talk about the “list” data structure, which is also used for searching, and the “tree” data structure, which is considered a generalization of the “list”.

Lecture 5. "Trees"



Continuing the theme of "trees", touched upon in the second lecture. Two abstractions are considered (set and mapping), from them we go to balanced search trees, red-black trees (binary search tree), and then touch the interface of the priority queue abstraction (based on trees).

Lecture 6. "Hash tables"



How to perform an external search (on external media) using B-trees, what is a generalized quick search, hash functions, different types of hash tables. You will also learn about another type of search, which is well suited to parallel algorithms - lists with gaps. Finally, an example of solving a problem is considered, which requires several different data structures.

Lecture 7. "Dynamic programming"



Here we will talk about how to solve large problems, which themselves are divided into subtasks. You will learn how using data structures you can solve peculiar problems (about the number of routes, about the increasing subsequence of the greatest length), the solution of which we will try to generalize. There will be an analysis of the stages of solving the problem by the method of dynamic programming.

Lecture 8. "Algorithms on graphs"



The last lecture in which there will be different types of graph representation, the concept of relaxation, several search modes (BFS, DFS), topological sorting, search for spanning trees in a graph, Dijkstra's algorithm (its connection with greedy algorithms) and the Floyd-Worshall algorithm (and its connection with dynamic programming).

Upon completion of the course you will learn the basic concepts: performer, abstraction, objects, methods, iteration, recursion, greedy algorithms, dynamic programming, sorting, searching, graphs. Get the skill to analyze the basic properties of algorithms, learn how to choose the necessary data structures for solving problems and justify your choice. You will be able to effectively implement algorithms in C and C ++ languages.

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.