Lectures of the Technosphere. Preparatory course "Algorithms and Data Structures" (spring 2016)

The goal 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 tasks, and learn how to use C / C ++ languages ​​to implement algorithms.

The course is taught by Sergey Babichev, assistant professor of computer science and computational mathematics, as well as theoretical and applied computer science at MIPT. Under the cat you will find eight lectures:

• Lecture 1. “Introduction. Performers. 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. Performers. Interface abstractions. Recursion "



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

Lecture 2. “Greedy Algorithms”



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

Lecture 3. “Sorting”



Information about different sorting and sorting activities. Several sorting technologies will be considered: by comparison, fast, using the properties of elements, external and others. It also compares sorts when and which method should be applied.

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 the search, search with narrowing the zone. In addition, we’ll talk about the “list” data structure, which is also used for search, and the “tree” data structure, which is considered a generalization of the “list”.

Lecture 5. “Trees”



Continuation of the theme of “trees”, raised in the second lecture. Two abstractions are considered (set and mapping), from them we will move on to balanced search trees, red-black trees (binary search tree), after which we will touch on the interface of the priority queue abstraction (tree-based).

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 that works well with parallel algorithms - skipped lists. Finally, we consider an example of solving a problem that requires several different data structures.

Lecture 7. “Dynamic programming”



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

Lecture 8. “Algorithms on graphs”



The last lecture, which will include different types of graph representations, 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) and Floyd-Warshall's algorithm (and its connection with dynamic programming).

Upon completion of the course you will learn the basic concepts: executor, abstraction, objects, methods, iteration, recursion, greedy, dynamic programming, sorting, search, 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 can effectively implement algorithms in C and C ++.

The playlist of all lectures is located at the link. Recall that current lectures and master classes on programming from our IT specialists in the Technopark, Technosphere and Technotrack projects are still published on the Technostream channel .