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

Course Syllabus

Bachelor 2018/2019

Algorithms and Data Structures 1

Type: Compulsory course (HSE and University of London Double Degree Programme in Data Science and Business Analytics)
Area of studies: Applied Mathematics and Information Science
Delivered by: Big Data and Information Retrieval School
When: 1 year, 2, 4 module
Mode of studies: Full time
Instructors: Рудаков Кирилл Александрович, Georgy Pyatsky, Sergey Shershakov, Andrei Tatarnikov, Rostislav Yavorskiy
Language: English
ECTS credits: 9

Course Syllabus

Full Syllabus

Abstract

The training course “Algorithms and Data Structures” is offered to students of Bachelor Program “HSE and University of London Double Degree Programme in Data Science and Business Analytics” (area code 01.03.02) at the Faculty of Computer Science of the National Research University — Higher School of Economics (HSE). The course is classified as an compulsory subject (Б.Пр.Б unit / base module,Б.Пр. – Major disciplines of 2019–2020 academic year working сurriculum); it is a two-module course (semester B quartiles 3 and 4). The syllabus is prepared for teachers responsible for the course (closely related disciplines), teaching assistants, students enrolled in the course as well as experts and statutory bodies carrying out assigned or regular accreditations. The course is dedicated to the basics of design and analysis of algorithms. It also involves learning fundamental data structures implemented by the C++ Standard Library (STL). 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++. Successful completion of “Introduction to Programming” course is the sole prerequisite for being enrolled in this course.
Learning Objectives

Learning Objectives

  • Students will study algorithm design principles.
  • Students will learn how to analyze the complexity of an algorithm in terms of time and space.
  • Students will study design principles of basic data structures.
  • Students will practice implementing algorithms and data structures as C++ applications.
Expected Learning Outcomes

Expected Learning Outcomes

  • Students will learn basic concepts and methods of designing algorithms.
  • Students will acquire skills in designing data structures by using C++.
  • 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 presentation skills.
  • 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.
Course Contents

Course Contents

  • MergeSort, Recurrences, and Asymptotics.
  • Solving recurrences and the master theorem.
  • Recurrence relations (substitution method, recursion trees). The Selection problem.
  • Heaps.
  • Quicksort, Probability and Randomized Algorithms.
  • Sorting Lower Bounds, BucketSort, RadixSort.
  • Tree. Binary tree. Red-Black Trees.
  • Hashing.
  • More on Graphs. Topological Sort.
  • Strongly connected components, Dijkstra’s algorithm.
  • Dynamic Programming and shortest paths: Bellman-Ford and Floyd-Warshall.
  • Examples of dynamic programming: Longest common subsequence, Knapsack, Independent Set.
  • Greedy algorithms, activity selection problem.
  • Minimum spanning tree: Boruvka, Kruskal, Prim.
  • Minimum Cut: Karger’s Algorithm.
  • Max Flow and the Ford-Fulkerson Algorithm.
Assessment Elements

Assessment Elements

  • non-blocking Homework
    Students’ skills in programming are tested using automated testing. This way, a student is assigned an individual task, prepares it by using a personal computer and, then, submits it by using a special service, such as Yandex.Contest or a repository-based tool. The specific solution is subject to further clarification.
  • non-blocking In-Class tasks
    Students’ skills in programming are tested using automated testing. This way, a student is assigned an individual task, prepares it by using a personal computer and, then, submits it by using a special service, such as Yandex.Contest or a repository-based tool. The specific solution is subject to further clarification.
  • non-blocking Bonus Points
  • non-blocking Ongoing Assessment
    The ongoing assessment grade is accumulated throughout all the classes and is related to a participant’s activity.
  • non-blocking Final Exam
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.4 * Final Exam + 0.6 * Ongoing Assessment
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.

Recommended Additional Bibliography

  • Davis, S. R. (2014). C++ For Dummies (Vol. 7th ed). Hoboken: For Dummies. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=784132
  • Gregoire, M. (2018). Professional C++ (Vol. Fourth edition). Indianapolis, IN: Wrox. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1729638