Algorithms and Programming, Part 2

Major: Computer Science (Design and programming of intelligent systems and devices)
Code of subject: 6.122.12.O.010
Credits: 7.00
Department: Computer-Aided Design
Lecturer: Mykhailo I. Andriychuk, DSc., Professor of the CAD Department. Oksana V. Oborska, Ph.D., Lecturer of the CAD Department.
Semester: 2 семестр
Mode of study: денна
Learning outcomes: As a result of studying the discipline, the student must know: 1. the concept of algorithm and its properties, general schemes for building algorithmic systems; 2. basic methods of the composition of normal algorithms; 3. basic quantitative characteristics (signal functions) of algorithms; 4. definition of the algorithmic and computational complexity of a mass problem; 5. the concept and example of NP-complete problem; 6. principles of operation of peripheral devices. Be able: 1. use basic data structures; 2. use search trees; 3. build normal algorithms, algorithm compositions; 4. build programs for Post and Turing machines; 5. build sorting algorithms; 6. build algorithms of Floyd, Dijkstra, Prima, Kraskala; 7. to carry out clustering of images by means of recognition algorithms; 8. build search algorithms.
Required prior and related subjects: 1. Algorithmization and programming, part 1. 2. Basics of programming, part 1. 3. Innovative information technologies. co-requisites: 1. Object-oriented programming. 2. Computer graphics. 3. Operating systems.
Summary of the subject: Topic 1. Basic concepts of the theory of algorithms. The concept of algorithm and its properties. Examples of algorithms. The need to formalize the concept of algorithm. Algorithmic system (calculation model), the general scheme of its construction. Graph-schemes and block diagrams of algorithms. Alphabetical algorithms. Normal Markov algorithms. Examples of construction of normal algorithms. The principle of normalization. The main methods of the composition of normal algorithms. The concept of a universal normal algorithm. Theorem on the universal normal algorithm. Algorithmically unsolvable problems. Computed functions. Elementary arithmetic functions. Primitively recursive functions, their examples. Minimization operator. Partially recursive functions. Church Thesis. Post and Turing machines. The structure and operation of Post and Turing machines. The concept of command, program and configuration. Examples of building programs for the Turing machine. Universal Turing machine. Turing's thesis. Stop problem and its algorithmic unsolvability. Communication of recursive functions with Turing machines. Topic 2. Analysis of the efficiency and complexity of algorithms. CPU, memory, disk space, network usage. The concept of temporal complexity. Summation of the Fibonacci series by two types of algorithms. Comparison of complexity. Calculation of practical complexity of algorithms. Optimistic, pessimistic, and average cases. Notation of large O. Asymptotic complexity of algorithms. Polynomial algorithms vs. exponential algorithms. Topic 3. Elementary computational structures. Binary trees. Queues, stacks, decks. Related distribution. Binary trees. Initialization. Insert an item. Search. Delete. Topic 4. Binary search trees. Balanced binary trees. Binary search trees. Types of tree traversal. Balanced binary trees. 2-3 trees. Initialization. Insert an item. Search. Delete. Topic 5. Red and black trees. Rules for building red and black trees. Bypassing the trees. Initialization. Insert an item. Search. Delete. Topic 6. Table hash. Initialization. Insert an item. Search. Delete. Calculating hash functions. Requirements for hash functions. Collisions. Methods of linear sounding, double hashing, coupling. Topic 7. Sorting algorithms. Stable and unstable sorting. Bubble sorting. Sort by inserts. Sort by choice. Sorting Shell. Merge sort. Pyramid sorting. Quicksort. Topic 8. Graphs and algorithms on graphs. Representation of graphs. Reach in graphs, finding the shortest paths. Topic 9. Greedy algorithms on graphs. Finding the shortest paths. Algorithms of Floyd, Dijkstra, Prima, Kraskala. Bypass graphs. Topic 10. Greedy algorithms. Huffman's algorithm. Topic 11. Algorithms of the class divide and rule. Mergesort Quicksort sorting algorithm. Topic 12. Algorithms of the class divide and rule. Multiplication of numbers. Recurrent ratios. Multiplication of matrices. Topic 13. Search algorithms. Brute force algorithm, Knut-Morris-Pratt algorithms, Boyer Moore, Rabbi Carp Topic 14. Algorithms of artificial intelligence. Image recognition algorithms. Threshold value algorithm. Algorithm of K-internal group means. Maximum algorithm. Alpha-beta algorithm.
Assessment methods and criteria: laboratory work - 40 points, calculation work - 8 points. Exam-52 points.
Recommended books: 1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009. 2. Donald E. Knuth. The art of computer programming. Vol. 3: Sorting and Searching. Addison-Wesley, Upper Saddle River, NJ, 1998. 3. Algorithms, 4th Edition by Robert Sedgewick, Kevin Wayne 4. Narasimha Karumanchi. Data Structures and Algorithms Made Easy 2016 CareerMonk Publications and others 5. The Algorithm Design Manual, 2nd Edition by Steven S Skiena 6. Yavorsky BI Theory of algorithms / Lecture notes.— Ternopil: TSTU named after Ivan Pulyuy, 2000.— 36 p.