Master
2022/2023
Advanced Algorithms
Type:
Elective course
Area of studies:
Applied Mathematics and Informatics
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
2 year, 2 module
Mode of studies:
distance learning
Online hours:
82
Open to:
students of one campus
Instructors:
Yaroslav Kischenko
Master’s programme:
Master of Data Science
Language:
English
ECTS credits:
4
Contact hours:
8
Course Syllabus
Abstract
Mastering algorithms is necessary to make your programs work faster and consume less memory. Sometimes, choosing a correct algorithm or data structure may reduce the execution time of your program from days to seconds! This is crucial to build efficient services, applications and data processing pipelines.
In many large software companies, algorithmic puzzles are prevalent among technical interviews for a software engineering position. You will solve these puzzles much more easily if you are familiar with some popular approaches and techniques that we will learn and practice in this course.
To complete the course, students are supposed to be familiar with the previous courses in the Algorithms series and the Python programming language. We expect students to know simple algorithms, be able to estimate time complexity of solutions, as well as code their solutions in Python.
Learning Objectives
- After taking this course, students should be able to: - Find efficient approaches to data processing problems; - Prove that a solution is correct; - Estimate the efficiency of a solution in terms of time and memory complexity; - Implement a solution in the Python programming language, debug, and test it; - Apply a number of general approaches and techniques to solve popular technical interview puzzles.
Expected Learning Outcomes
- Examine calculation of greatest common divisors (GCD), exponentiation by squaring, primality testing, sieve of Eratosthenes.
- Learn binary trees and various traversals, least common ancestor problem, tries and Aho-Corasick algorithm
- Be able to recognize problems where the technique can be applied and solve them
- Be able to analyze the time and memory complexity of the solutions
- Reiterate continuous knapsack and 0-1 knapsack problems
- Reiterate Huffman encoding, Dijkstra algorithm, job scheduling
- Reiterate traveling salesperson problem
- Learn the concept of greedy algorithms, limits of greedy algorithms, approximate greedy algorithms
- Learn the concept of backtracking
- Learn techniques to speed up backtracking
- Become familiar with approximate solutions
- Know the properties of the segment tree data structure (available queries and operations, time and memory complexity)
- Be able to recognize problems where the data structure can be applied and solve them
- Be able to extend segment trees for new queries and operations
Course Contents
- Arithmetics and Number Theory
- Trees, Tries, and Least Common Ancestors
- Two Pointers Technique
- Greedy Algorithms
- Backtracking
- Segment Trees
Interim Assessment
- 2022/2023 2nd module0.1 * Final Project + 0.05 * Quizz + 0.85 * Programming Assignments
Bibliography
Recommended Core Bibliography
- Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology. Cambridge University Press.
- Serge Lang. (2013). Algebraic Number Theory (Vol. 2nd ed. 1994). Springer.
Recommended Additional Bibliography
- Guy E., Dror R. Design and Analysis of Algorithms // Springer - https://link.springer.com/book/10.1007%2F978-3-642-34862-4