• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedFor visually-impairedUser profile (HSE staff only)Search
Advanced search
Menu
HSE University
User profile (HSE staff only)Search
Advanced search

Course Syllabus

Bachelor 2024/2025

Algorithms and Data Structures

Type: Compulsory course (Data Science and Business Analytics)
Area of studies: Applied Mathematics and Information Science
Delivered by: Big Data and Information Retrieval School
Where: Faculty of Computer Science
When: 2 year, 1-4 module
Mode of studies: offline
Open to: students of one campus
Instructors: Borevskiy Andrey, Vladimir Kurenkov
Language: English
ECTS credits: 8

Course Syllabus

Full Syllabus

Abstract

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. The lectures and practical classes are closely inter-related. The lectures are primarily intended to introduce new topics, whereas the practical classes are intended for solving specific problems by coding programs in C++ or Python. Successful completion of “Introduction to Programming” course is the sole prerequisite for being enrolled in this course.
Learning Objectives

Learning Objectives

  • Students will continue to study algorithm design principles.
  • Students will elaborate important concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.
  • Students will study design principles of selected advanced data structures.
  • Students will practice efficiently implementing algorithms and data structures as C++ applications.
  • Students will concern selected algorithms on strings.
  • Students will concern selected graph algorithms.
  • Students will study basic concepts on theory of automata.
  • Students will learn basic concepts and methods of designing algorithms.
  • Students will acquire skills in designing data structures by using C++ or Python.
  • Students will learn approaches to analysis of algorithms complexity in terms of time and space.
  • Students will improve team-working skills by using collaborative working tools.
  • Students will improve self- and peer-review skills.
  • Students will improve skills in writing reports and technical documentation, including rapidly changing documentation using wiki and other specific tools.
Expected Learning Outcomes

Expected Learning Outcomes

  • Students will concern selected algorithms on strings.
  • Students will concern selected graph algorithms.
  • Students will elaborate important concepts of computational complexities for problems and algorithms (both exact and heuristic), which are necessary for further learning computational methods, algorithms for big data, algorithms and computational complexity, machine learning, operations research, game theory, and combinatorial optimization.
  • Students will learn how to analyze the complexity of an algorithm in terms of time and space.
  • Students will practice efficiently implementing algorithms and data structures using C++ or Python programming languages.
  • Students will study algorithm design principles.
  • Students will study basic concepts on theory of automata.
  • Students will study design principles of basic and advanced data structures.
Course Contents

Course Contents

  • Asymptotic Notation, Divide-and-Conquer Paradigm, Recurrences
  • Sorting Algorithms: Insertion Sort, Merge Sort, Heap Sort, Quick Sort
  • Sorting Lower Bounds, BucketSort, RadixSort.
  • Trees, Binary Search Trees, AVL Trees, Red-Black Trees, Treaps
  • Tries, Compact Tries
  • Hashing.
  • String Matching: Knuth-Morris-Pratt Algorithm, Boyer-Moore Algorithm, Aho-Corasick Algorithm
  • Suffix Trees, Ukkonen’s Algorithm, Suffix Arrays
  • Dynamic Programming with Samples: Knapsack Problem, Levenshtein Distance (LCS Problem)
  • Greedy Algorithms with Samples: Huffman Coding, Activity Selection Problem, LCS Problem via Greedy Algorithm
  • Graphs. Topological Sort, Strongly Connected Components, Minimum Spanning Trees.
  • Single-Source and All-Pairs Shortest Paths in Graphs. Dijkstra’s Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm
  • Maximum Flow, Ford-Fulkerson Method
  • Introduction to Automata. Deterministic Finite Automata. Nondeterministic Finite Automata
  • Regular Expressions
  • Decision and Closure Properties of Regular Languages
  • Context-Free Languages. Properties of Context-Free Languages
  • Parse Trees. Normal Forms for Context-Free Grammars
  • Pushdown Automata. Equivalence of CFG’s and PDA’s
  • Range Minimum Queries (RMQ).
  • Cartesian Trees and RMQ.
Assessment Elements

Assessment Elements

  • non-blocking Practice tests
    Contest with set of problems in practice classes. It contains no more than 10 problems, where students need to write code and pass all tests.
  • non-blocking Exam
    Consists of two parts: written and oral. Written part is a test with set of questions about past topics. It contains no more than 30 questions, where students need to choose answers from given list of variants or calculate them. In several cases students need to write a code. Oral part is a discussion with students about past topics from selected modules.
  • non-blocking Homework
    Contest with set of problems. It contains no more than 15 problems, where students need to write code and pass all tests.
  • non-blocking Practice tests
    Contest with set of problems in practice classes. It contains no more than 10 problems, where students need to write code and pass all tests.
  • non-blocking Homework
    Contest with set of problems. It contains no more than 15 problems, where students need to write code and pass all tests.
  • non-blocking Lecture's tests
    Written test with set of questions about past topics. It contains no more than 30 questions, where students need to choose answers from given list of variants or calculate them. In several cases students need to write a code.
  • non-blocking Lecture's tests
    Written test with set of questions about past topics. It contains no more than 30 questions, where students need to choose answers from given list of variants or calculate them. In several cases students need to write a code.
  • non-blocking Exam
    Consists of two parts: written and oral. Written part is a test with set of questions about past topics. It contains no more than 30 questions, where students need to choose answers from given list of variants or calculate them. In several cases students need to write a code. Oral part is a discussion with students about past topics from selected modules.
Interim Assessment

Interim Assessment

  • 2024/2025 1st module
    0.4 * Exam + 0.2 * Homework + 0.2 * Lecture's tests + 0.2 * Practice tests
  • 2024/2025 4th module
    0.4 * Exam + 0.2 * Homework + 0.2 * Lecture's tests + 0.2 * Practice tests
Bibliography

Bibliography

Recommended Core Bibliography

  • Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
  • Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2014). Introduction to Automata Theory, Languages, and Computation: Pearson New International Edition: Vol. 3rd ed. Pearson.
  • Michael Sipser. (2005). Introduction to the Theory of Computation, Second Edition.

Recommended Additional Bibliography

  • Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences : Computer Science and Computational Biology. Cambridge University Press.

Authors

  • MAKAROV NIKITA KONSTANTINOVICH