Алгоритмы и структуры данных

2024/2025

Статус: Маго-лего

Кто читает: Департамент больших данных и информационного поиска

Когда читается: 3, 4 модуль

Охват аудитории: для своего кампуса

Язык: русский

Кредиты: 6

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

The course is dedicated to the basics of design and analysis of algorithms. It also involves learning advanced algorithms, data structures and basics of the automata theory.

Цель освоения дисциплины

Learning basic algorithms and data structures
Development of skills in substantiating the correctness of algorithms, their practical implementation, theoretical and experimental assessment of their time complexity

Планируемые результаты обучения

You will learn how to characterize the complexity of algorithms using the notion of theoretical complexity, how it is related to actual performance. The basic techniques for reducing complexity will be introduced, and you will practice them.
You will learn how to implement and use fundamental data structures such as stack and queue, and practice how to choose an appropriate data structure for a problem at hand.
You will learn how to split complex problems into smaller pieces using recursion. You will explore applications to combinatorial search and optimization problems.
You will learn how to make a recursive program dramatically more efficient (and much less recursive) by adding "memory" to it. This is called dynamic programming, we will illustrate this paradigm on several classical problems such as text justification, knapsack, and edit distance.
You will study divide-and-conquer techniques and efficient algorithms and data structures for operating with data based on these techniques (such as binary search, merge sort, and binary search trees).
You develop your basic algorithmic skills: justifying your solution and testing your code. Then you will have the final project: a nontrivial coding interview question.
You will learn 3 ways to store a graph in computer memory, 2 types of graph traversal algorithms: DFS and BFS and their various applications.
You will learn the 3 common solutions to the shortest path problem: the Bellman-Ford algorithm, the Dijkstra's algorithm and Floyd-Warshall algorithm.
You will learn 3 common solutions to the substring search problem: Knuth-Morris-Pratt algorithm, Z-algorithm and the Rabin-Karp algorithm. You will also discuss the polynomial string hashing approach.
You will talk about the pinnacle of algorithms: the sorting algorithms. You will discuss the most basic algorithms, such as Bubble sort, as well as more optimal and advanced, such as Quicksort.
You will shift our attention from the algorithms and focus more on Data Structures instead. You will talk about Linked Lists, Hash Tables and Binary heaps.
You will focus on technical interviews and how to prepare and survive them.