CS405
Advanced Algorithms and Data Structures
Faculty Profiles
Mikhail Mirzayanov
Founder & CEO of Codeforces, ICPC 2006 World Champions Coach
Nikolay Kalinin
Codeforces Chief Problem Coordinator,Postdoc at Max Planck Institute, Germany
Course length
Duration
Total hours
Credits
Language
Course type
Fee for single course
Fee for degree students
Skills you’ll learn
Overview
This course focuses on key and in-depth algorithms and data structures that form a modern computer specialist’s toolkit. The computational complexity of algorithms and their comparative analysis will also be discussed. Students will be extensively trained in implementing data structures and algorithms on many problems reducible to the discussed data structures and techniques. The programs will be tested against carefully prepared test cases using an automated testing system.
Learning highlights
- Get acquainted with in-depth algorithms and data structures
- To some extent, be able to apply in-depth algorithms and data structures to solve new problems that may arise in various applications
- Gain practice in problem-solving and programming on the topics of the discussed algorithms data structures
Course outline
15 classes
Session 1
Advanced Algorithms and Data Structures: Introductory Contest.
Session 2
Binary and ternary searches. Idea. C++ standard library functions. Binary search the answer. Binary search on real values.
Session 3
Heap data structure, heap properties and operations. Heap sort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomized meldable heap.
Session 4
Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees.
Session 5
Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalization for higher dimensions.
Session 6
Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm.
Session 7
Shortest paths. Breadth-first search. Its properties. State graphs. Breadth-first search on 0-1 graphs. Map of shortest paths. Related problems.
Session 8
Practice day. Help and advice in solving practical problems.
Session 9
SSSP. Non-negative weights. Dijkstra's algorithm. Negative weights. Bellman-Ford algorithm. SPFA. Negative Cycle Detection. All-pairs shortest path problem. Floyd–Warshall algorithm. Johnson's algorithm.
Session 10
Practice day. Help and advice in solving practical problems.
Session 11
Minimum spanning trees. Tarjan's criterion. Kruskal's algorithm. Disjoin-Set-Union data structure, applications. Prim's algorithm.
Session 12
Bipartite graphs. König’s criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG with minimal number of paths.
Session 13
Practice day. Help and advice in solving practical problems.
Session 14
Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine.
Session 15
Practice day. Help and advice in solving practical problems.
Prerequisites
A firm grasp of one programming language and a background in discrete mathematics are necessary prerequisites to this course. Examples will be given mainly in C++ and Python.
Methodology
Programming assignments and lectures
Grading
Mikhail graduated from Saratov State University in 2004. During his study at the university, Mikhail took part in programming contests: he won two silver medals at the ACM-ICPC World Finals and many times advanced to the finals of prestigious world programming contests. As a coach of Saratov State University ACM-ICPC, his teams won ACM-ICPC World Cup in 2006, All-Russia Cup in 2008, gold and silver medals at ACM-ICPC World Finals. His high-school students won medals at IOI. He teached Algorithms and Data Structures at Saratov State University for 5 years. He was the head of the Programming Competitions Training Center at Saratov State University. He was chairman and jury member of many programming competitions. In 2010 Mikhail founded the website Codeforces, now it is the world’s largest competitive programming community.
See full profileAwards
- ICPC 2020 World Champion
Nikolay graduated from Nizhny Novgorod State University in 2020 and earned his PhD from Friedrich-Alexander University Erlangen-Nuremberg in 2024. During his school and university years, he successfully participated in various programming competitions, winning two gold medals at the International Olympiad in Informatics (IOI) and becoming the World Champion in the International Collegiate Programming Contest in 2020.
Nikolay's primary research interests lie in the fields of nonlinear laser optics and quantum light. His work spans both experimental and theoretical research. Since 2016, he has also been a Coordinator at Codeforces, the world’s largest competitive programming community.
See full profileApply for this course
Advanced Algorithms and Data Structures
by Mikhail Mirzayanov, Nikolay Kalinin
Total hours
45 Hours
Dates
Jan 31 - Feb 18, 2022
Fee for single course
€1500
Fee for degree students
€750
Explore related courses
How to secure your spot
Complete the form below to kickstart your application
Schedule your Harbour.Space interview
If successful, get ready to join us on campus
FAQ
Will I receive a certificate after completion?
Yes. Upon completion of the course, you will receive a certificate signed by the director of the program your course belonged to.
Do I need a visa?
This depends on your case. Please check with the Spanish or Thai consulate in your country of residence about visa requirements. We will do our part to provide you with the necessary documents, such as the Certificate of Enrollment.
Can I get a discount?
Yes. The easiest way to enroll in a course at a discounted price is to register for multiple courses. Registering for multiple courses will reduce the cost per individual course. Please ask the Admissions Office for more information about the other kinds of discounts we offer and what you can do to receive one.