Algorithms and Data Structures DSBA 2024/25 — различия между версиями
Aspronina (обсуждение | вклад) м |
Aspronina (обсуждение | вклад) м |
||
(не показано 15 промежуточных версии 3 участников) | |||
Строка 22: | Строка 22: | ||
|| Teaching Assistant | || Teaching Assistant | ||
|| Belikov Daniil <br> tg: [https://t.me/DanBel1kov @DanBel1kov] | || Belikov Daniil <br> tg: [https://t.me/DanBel1kov @DanBel1kov] | ||
− | || Latyshev Ivan <br> tg: [https://t.me/ | + | || Latyshev Ivan <br> tg: [https://t.me/ivan_latysh @ivan_latysh] |
|| Gadaev Isa <br> tg: [https://t.me/elohimapproximation @elohimapproximation] | || Gadaev Isa <br> tg: [https://t.me/elohimapproximation @elohimapproximation] | ||
|| Pavlov Leonid <br> tg: [https://t.me/leon1dl @leon1dl] | || Pavlov Leonid <br> tg: [https://t.me/leon1dl @leon1dl] | ||
Строка 53: | Строка 53: | ||
If the student is suspected of preparing the task not on his own, the teacher has the right to initiate additional verification or defense of this particular assessment element. Then such an assessment element will be graded based on the additional verification or the defense. | If the student is suspected of preparing the task not on his own, the teacher has the right to initiate additional verification or defense of this particular assessment element. Then such an assessment element will be graded based on the additional verification or the defense. | ||
− | = Home assignments = | + | = Home assignments = |
+ | |||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |- | ||
+ | ! Contest !! Deadline !! Topic | ||
+ | |- | ||
+ | || [https://official.contest.yandex.ru/contest/68732/enter/ Contest 1] || 16 oct 2024, 23:59:59 || Sorting Algorithms | ||
+ | |- | ||
+ | || [https://official.contest.yandex.ru/contest/69563/enter/ Contest 2] || 25 oct 2024, 23:59:59 || Trees | ||
+ | |- | ||
+ | || [https://official.contest.yandex.ru/contest/70462/enter/ Contest 3] || 15 nov 2024, 23:59:59 || String Algorithms I | ||
+ | |- | ||
+ | || [https://official.contest.yandex.ru/contest/70464/enter/ Contest 4] || 22 nov 2024, 23:59:59 || String Algorithms II | ||
+ | |- | ||
+ | || [https://official.contest.yandex.ru/contest/71931/enter/ Contest 5] || 8 dec 2024, 23:59:59 || Dynamic Programming | ||
+ | |} | ||
= Lectures = | = Lectures = | ||
Строка 67: | Строка 82: | ||
* Radix sort | * Radix sort | ||
''Bibliography'': Cormen, ch. 2, 3, 6, 8 | ''Bibliography'': Cormen, ch. 2, 3, 6, 8 | ||
+ | |||
+ | '''Sep 14''' | ||
+ | * Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete | ||
+ | * Binary search trees, main operations (insert, delete, rotate) | ||
+ | * AVL-trees, main operations | ||
+ | * Red-black trees, main definitions | ||
+ | ''Bibliography'': Cormen, ch. 12, 13 | ||
+ | |||
+ | '''Sep 21''' | ||
+ | * Red-black trees, main operations | ||
+ | * Treaps, main operations | ||
+ | * Tries, main operations | ||
+ | ''Bibliography'': Cormen, ch. 13, Mehta, ch. 28 | ||
+ | |||
+ | '''Sep 28''' | ||
+ | * Tries, compact tries, PATRICIA trie, main operations | ||
+ | * 2-3-4 trees, main operations | ||
+ | * B-trees, main operations | ||
+ | ''Bibliography'': Mehta, ch. 28, Cormen, ch. 18 | ||
+ | |||
+ | '''Oct 5''' | ||
+ | * Quiz #1 | ||
+ | * Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm | ||
+ | ''Bibliography'': Gusfield, ch. 1, 2 | ||
+ | |||
+ | '''Oct 12''' | ||
+ | * Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm | ||
+ | ''Bibliography'': Gusfield, ch. 2 | ||
+ | |||
+ | '''Oct 19''' | ||
+ | * Exact matching with a set of patterns: Aho-Corasick algorithm | ||
+ | * Exact string matching: Apostolico-Giancarlo algorithm | ||
+ | * Suffix trees: basic definition, naive algorithm to build | ||
+ | ''Bibliography'': Gusfield, ch. 3, 5 | ||
+ | |||
+ | '''Oct 26''' | ||
+ | * Module 1 Exam | ||
+ | |||
+ | '''Nov 9''' | ||
+ | * Suffix trees: basic definition, naive algorithm to build | ||
+ | * Suffix trees: Ukkonen's algorithm, applications | ||
+ | * Suffix arrays: building using suffix tree, exact string matching | ||
+ | ''Bibliography'': Gusfield, ch. 5, 6, 7 | ||
+ | |||
+ | '''Nov 16''' | ||
+ | * Suffix arrays: building without suffix tree | ||
+ | * Dynamic programming: longest common subsequence, Levenstein distance | ||
+ | ''Bibliography'': Cormen, ch. 15 | ||
+ | |||
+ | '''Nov 23''' | ||
+ | * Dynamic programming: two conveyors problem, 0-1 knapsack problem | ||
+ | * Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes | ||
+ | ''Bibliography'': Cormen, ch. 15, 16 | ||
+ | |||
+ | |||
+ | |||
==List of topics for exam in module 1== | ==List of topics for exam in module 1== | ||
+ | * Asymptotic notation | ||
+ | * Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort | ||
+ | * Lower bounds of sorting using comparisons | ||
+ | * Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete | ||
+ | * Binary search trees, main operations (search, insert, delete, rotate) | ||
+ | * AVL-trees, main operations (search, insert, delete) | ||
+ | * Red-black trees, main operations (search, insert) | ||
+ | * Treaps, main operations (search, insert, delete, split, merge) | ||
+ | * Tries, compact tries, main operations (search, insert, delete) | ||
+ | * 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree | ||
+ | * B-trees, main operations (search, insert, delete) | ||
+ | * Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm | ||
+ | * Exact matching with a set of patterns: Aho-Corasick algorithm | ||
+ | |||
==List of topics for exam in module 4== | ==List of topics for exam in module 4== |
Текущая версия на 11:56, 27 ноября 2024
Содержание
About
This page contains basic information for the course Algorithms and Data Structures in 2024/2025 academic year at Bachelor’s Programme in Data Science and Business Analytics (DSBA).
The full syllabus can be accessed at this page.
In case you find any inconsistencies on this page, please, contact @l_AnnaPronina_l.
Teachers and assistants
Group | 231 | 232 | 233 | 234 | |
---|---|---|---|---|---|
Lecturer | Nikita Makarov | ||||
Seminar Instructor | Andrey Borevskiy | Vladimir Kurenkov | |||
Teaching Assistant | Belikov Daniil tg: @DanBel1kov |
Latyshev Ivan tg: @ivan_latysh |
Gadaev Isa tg: @elohimapproximation |
Pavlov Leonid tg: @leon1dl | |
Head TA | Pronina Anna tg: @l_AnnaPronina_l |
Grading
You may find your grades here.
Formula
Final Grade = M1 * 0.3 + M4 * 0.7
Mi = E * 0.4 + HW * 0.2 + Q * 0.2 + S * 0.2
- E - exam grade: rational number [0, 10] = sum of the grade for the oral and written parts, out of 5 each
- HW - homework grade: rational number [0, 10]
- Q - lecture quizzes grade: rational number [0, 10]
- S - seminar practice grade: rational number [0, 10]
rounding: each element in the formulae is rounded up
Plagiarism policy
If plagiarism is detected, the assessment element will be assigned a score of 0.
If the student is suspected of preparing the task not on his own, the teacher has the right to initiate additional verification or defense of this particular assessment element. Then such an assessment element will be graded based on the additional verification or the defense.
Home assignments
Contest | Deadline | Topic |
---|---|---|
Contest 1 | 16 oct 2024, 23:59:59 | Sorting Algorithms |
Contest 2 | 25 oct 2024, 23:59:59 | Trees |
Contest 3 | 15 nov 2024, 23:59:59 | String Algorithms I |
Contest 4 | 22 nov 2024, 23:59:59 | String Algorithms II |
Contest 5 | 8 dec 2024, 23:59:59 | Dynamic Programming |
Lectures
Lectures are held on Saturdays from 14:40 till 17:40.
Lecture Materials
Sep 7
- Introduction to the course
- Asymptotic notation
- Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap)
- Lower bounds of sorting
- Counting sort
- Radix sort
Bibliography: Cormen, ch. 2, 3, 6, 8
Sep 14
- Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
- Binary search trees, main operations (insert, delete, rotate)
- AVL-trees, main operations
- Red-black trees, main definitions
Bibliography: Cormen, ch. 12, 13
Sep 21
- Red-black trees, main operations
- Treaps, main operations
- Tries, main operations
Bibliography: Cormen, ch. 13, Mehta, ch. 28
Sep 28
- Tries, compact tries, PATRICIA trie, main operations
- 2-3-4 trees, main operations
- B-trees, main operations
Bibliography: Mehta, ch. 28, Cormen, ch. 18
Oct 5
- Quiz #1
- Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm
Bibliography: Gusfield, ch. 1, 2
Oct 12
- Exact string matching: Knuth-Morris-Pratt algorithm, preprocessing for real-time string matching, Boyer-Moore algorithm
Bibliography: Gusfield, ch. 2
Oct 19
- Exact matching with a set of patterns: Aho-Corasick algorithm
- Exact string matching: Apostolico-Giancarlo algorithm
- Suffix trees: basic definition, naive algorithm to build
Bibliography: Gusfield, ch. 3, 5
Oct 26
- Module 1 Exam
Nov 9
- Suffix trees: basic definition, naive algorithm to build
- Suffix trees: Ukkonen's algorithm, applications
- Suffix arrays: building using suffix tree, exact string matching
Bibliography: Gusfield, ch. 5, 6, 7
Nov 16
- Suffix arrays: building without suffix tree
- Dynamic programming: longest common subsequence, Levenstein distance
Bibliography: Cormen, ch. 15
Nov 23
- Dynamic programming: two conveyors problem, 0-1 knapsack problem
- Greedy algorithm: activity selection problem, fraction knapsack problem, longest increasing subsequence, Huffman codes
Bibliography: Cormen, ch. 15, 16
List of topics for exam in module 1
- Asymptotic notation
- Sorting algorithms: insertion sort, merge sort, heap sort (including building a heap), counting sort, radix sort
- Lower bounds of sorting using comparisons
- Basic data structures: array, stack, queue, deque, linked list, tree; basic operations: search, insert, delete
- Binary search trees, main operations (search, insert, delete, rotate)
- AVL-trees, main operations (search, insert, delete)
- Red-black trees, main operations (search, insert)
- Treaps, main operations (search, insert, delete, split, merge)
- Tries, compact tries, main operations (search, insert, delete)
- 2-3-4 trees, main operations (search, insert, delete), transformation into red-black tree
- B-trees, main operations (search, insert, delete)
- Exact string matching: naive method, Z algorithm, Knuth-Morris-Pratt algorithm, Boyer-Moore algorithm
- Exact matching with a set of patterns: Aho-Corasick algorithm