THEORY OF ALGORITHMS

Abstract of the academic discipline

The purpose of studying the discipline "Theory of Algorithms": is the formation and development of competencies aimed at solving complex specialized tasks and practical problems in the field of computer science for adequate modeling of subject areas and the creation of software and information systems through the use of formal languages and models of algorithmic calculations, design, development and analysis of algorithms, evaluation of their efficiency and complexity, solvability and insolvability of algorithmic problems.
The practical value and use of the acquired knowledge of the discipline "Theory of Algorithms" - the acquisition of theoretical knowledge, special skills and practical skills for the analysis and evaluation of the effectiveness of existing basic algorithms by the students of basic higher education using the appropriate data structures, namely:
– to gain knowledge of basic concepts and definitions of the theory of algorithms, types of algorithms and basic data structures
– to gain knowledge of the mathematical foundations of algorithm analysis, namely: mastering the methods of asymptotic analysis of the complexity of algorithms; acquiring knowledge about the classification of algorithms according to complexity classes; acquiring skills in developing criteria for comparative evaluation of the quality of algorithms; mastering the skills to develop an algorithmic solution to a problem or formal proofs of algorithmic intractability of tasks
- to gain knowledge of the construction and operation of algorithms of the main classes, namely sorting algorithms, algorithms on graphs, linear and binary search, search algorithms on strings, etc.
Main learning outcomes
PRN#1. Apply knowledge of the basic forms and laws of abstract and logical thinking, the basics of the methodology of scientific knowledge, the forms and methods of extracting, analyzing, processing and synthesizing information in the subject area of computer science.
PRN#2. To use the modern mathematical apparatus of continuous and discrete analysis, linear algebra, analytical geometry, in professional activities to solve problems of a theoretical and applied nature in the process of designing and implementing informatization objects
PRN#5. Design, develop and analyze algorithms for solving computational and logical problems, evaluate the efficiency and complexity of algorithms based on the application of formal models of algorithms and calculated functions. Subjects and types of educational classes

1 week.
Lecture #1 
"Basic concepts and definitions of the theory of algorithms: the subject of the theory of algorithms." Obtaining a task for calculation and graphic work. Analysis and selection of literary sources.
Laboratory lesson #1 
"Quadratic sorting algorithms".
2 week
Lecture #2 
"Basic stages of algorithm design and analysis"
Performing calculation and graphic work. Part 1
3 week.
Lecture #3 
"Types of algorithms and main types of problems"
Laboratory lesson #2 
"Logarithmic sorting algorithms".
Performing calculation and graphic work. Part 1
4 week.
Lecture #4 
"Basic data structures: linear data structures, graphs, trees, sets, dictionaries, abstract data types"
Performing Calculation and graphic work. Part 1
5 week.
Lecture #5 
"Mathematical foundations of algorithm analysis"
Laboratory lesson # 3 
"Algorithm of pyramidal sorting".
Performing calculation and graphic work. Part 1
6 week.
Lecture #6 
"Examples of algorithm efficiency research, concepts of iteration and recursion"
Performing calculation and graphic work. Part 1
7 week.
Lecture #7 
"Quadratic sorting algorithms, exchange sorting algorithms, selection sorting".
Laboratory session #4 
"Construction of a minimal skeletal tree".
Performing calculation and graphic work. Part 1
8 week
Lecture #8 
"Logarithmic sorting algorithms: pyramid sort, merge sort, quick sort."
Performing calculation and graphic work. Part 1
Modular test (control work) #1
9 week.
Lecture # 9 
"Algorithms on graphs: examples of tasks, adjacency and incidence matrices, adjacency lists."
Laboratory lesson #5 
"Finding the shortest path in a graph."
Performing calculation and graphic work. Part 2
10 week.
Lecture #10 
"Systematic enumeration of graph vertices: traversals of graphs in depth and width"
Performing calculation and graphic work. Part 2
11 week.
Lecture #11 
"Weighted graphs: Prim and Kruskal's algorithm".
Laboratory lesson #6 
"Working with search trees".
Performing calculation and graphic work. Part 2
12 week. 
Lecture #12 
"Finding the shortest path in a graph using the algorithm of Bellman-Ford, Dijkstra, and Floyd."
Performing calculation and graphic work. Part 2
13 week.
Lecture #13 
"Linear and binary search algorithms, binary search tree."
Laboratory lesson #7 
"Working with hash tables"
Performing calculation and graphic work. Part 2
14 week.
Lecture # 14 
"Balancing methods of binary search trees: red-black trees"
Defense of calculation and graphic work
15 week.
Lecture #15 
"Hash Table Basics: Open and Closed Hashing"
Defense of calculation and graphic work
Modular test (control work) #2

Individual work of the applicant takes place during the semester and consists of preparation for classroom classes, control measures, individual tasks.
Consultations: are carried out by the teacher during the semester according to the schedule.

Assessment of learning outcomes

The evaluation of the results of studies in the discipline is carried out according to the cumulative system, which allows the student to receive a maximum of 100 points during the semester.
Module 1
Laboratory works # 1, 2, 3, 4 – perfect execution of each laboratory work in the established terms, maximum 5 points - 20 points in total.
Modular test (control work) #1 – 20 points in total.
Modular test 1 consists of a theoretical part (2 questions) and a practical part (2 problems). A perfect execution of one theoretical question is evaluated maximum 5 points. The correct solution of one problem is estimated at maximum 5 points.
Completion of the first part of the calculation and graphic work – 10 points
Module 2
Laboratory work # 5 (5 points), Laboratory work #6 (10 points), Laboratory work #7 (5 points) – 20 points in total.
Modular test (control work) #2 – 20 points in total.
Completion of the second part of calculation and graphic work – 5 points
Defense of calculation and graphic work - 5 points.
Module control work #2 consists of a theoretical part (2 questions) and a practical part (2 tasks). A perfect answer to one theoretical question is evaluated by 5 points. The correct solution of one task is estimated at 5 points.

Links to recommended sources of information

1.    Data Structures and Algorithms [Електронний ресурс], Автори: Alfred V. Aho, Bell Laboratories, Murray Hill, New Jersey John E. Hopcroft, Cornell University, Ithaca, New York, Jeffrey D. Ullman, Stanford University, Stanford, California, Режим доступу: https://dokumen.tips/documents/data-structures-and-algorithms-alfred-v-a...
2.    Горлова Т.М. Теорія алгоритмів. [Електронний ресурс]: конспект лекцій для студентів напряму підготовки 6.050101 «Комп'ютерні науки» денної та заочної форм навчання / Т.М. Горлова, К.Є. Бобрівник, Н.В. Ліманська – К.:НУХТ, 2015. – 95 с. Режим доступу: http://library.nuft.edu.ua/ebook/file/M51.21.pdf
3.    Коваль В.С., Струбицький П.Р. Алгоритми і структури даних. – Навчальний посібник Тернопіль: ФОП Шпак В. Б. – 2017. – 74 с. Режим доступу: http://dspace.wunu.edu.ua/bitstream/316497/41016/1/%D0%BD%D0%B0%D0%B2%D1...
4.    Algorithms and Data Structures by Niklaus Wirth  [Електронний ресурс] Автор Вирт Н. Режим доступуhttps://people.inf.ethz.ch/wirth/AD.pdf