C++ Algorithms & Data Structures course

Chaos Camp 2021 - 2022

Program

Data types and their behavior. Some math algorithms. Dealing with the floating point numbers. Precision in floating point calculations. Specifics.
A high level look at computer architectures. Memory structure. Why do we need to know that? Access patterns and according data arrangement.
Recursion. Back tracking. Memoization.
Statistical and probabilistic algorithms. Randomized algorithms.
Introduction to parallel calculations and algorithms. Specifics and what to be aware of. A simple example with OpenMP. Examples with statistical algorithms.
Sorting algorithms. Types, specifics. Generic algorithms: Selection sort, insertion sort, bubble sort, shaker sort, Shell sort, merge sort. Quick sort.
Data dependent algorithms.
Counting sort, radix sort.
Geometric algorithms and calculations.
Searching - linear, binary, interpolation and parallel.
Heap, Heap sort. Hash functions and hash tables.

When we run out of memory - external searching and sorting. Indexing.
Mid-term exam.
Some special linear data structures - Chunk array, Skip list.
Non-linear data structures. Trees, DFS and BFS. Binary ordered tree. When we can use it and when to avoid it.
How to fix the broken tree? Balanced trees. SDW algorithm for balancing.
Self-balancing trees. Red-Black tree. AVL tree.
Shared access to the tree. Parallel building and searching in a BST.
B-trees.
More on trees - Prefix trees. Automata.
Interval trees. Dynamic Order Statistics.
Regular trees with higher dimension. KD-trees. BVH.
Introduction to GPGPU programming - how GPU works, thread divergence, dot product reduction, prefix sum.
More on probabilities and statistics. Monte Carlo and Las Vegas algorithms.

Mentors

Associate Professor Petar Armyanov, Ph.D.

Associate Professor Petar Armyanov, Ph.D. holds an MSC and Ph.D. degree in Informatics from Sofia University St. Kliment Ohridski. He joined the faculty in 2016 to teach 12 subjects all related to programming. He was also the assistant coach of the University’s programming team. His interests include algorithms, programming languages, computer graphics, and high-performance computing. Armyanov has more than 10 years of professional experience as a programmer.

Lyubomir Koev

Lyubomir Koev is a C++ developer at Chaos where he has worked for more than six years. His core strengths are C++ and algorithms (his weakness is gaming!). For the past seven years, he’s been a teaching assistant at FMI at Sofia University for courses in C++, data structures and algorithms — you can find his published materials on his GitHub profile.

Guest lecturers

Professor Krassimir Manev, Ph.D.

Krassimir Manev is a Bulgarian mathematician and computer scientist, professor in New Bulgarian University. He has years of experience in the Bulgarian National Olympic team in informatics and from 2014 to 2017 he is the President of the International Olympiad in Informatics. He is also а founder and President of of the European Junior Olympiad in Informatics.

Associate Professor Boyko Bantchev, Ph.D.

Associate Professor Boyko Bantchev is an alumnus of Sofia University and has been teaching there for many years. Being affiliated with the Institute of Mathematics and Informatics of the Bulgarian Academy of Sciences, he does some research, experimentation, computer programming, and teaching in the fields of programming languages, geometric computing, vector computer graphics, and programming in general.

< Go back to Chaos Camp