Home/ Majors directory/Software Engineering/Algorithms and Data Structures
Algorithms and Data Structures
Major: Software Engineering
Code of subject: 6.121.00.O.016
Credits: 4.00
Department: Software
Lecturer: Korotyeyeva Tatiana.
Semester: 3 семестр
Mode of study: денна
Завдання: The study of an educational discipline involves the formation of competencies in students of education:
general competences:
K01. Ability to abstract thinking, analysis and synthesis.
К20. Ability to apply and develop fundamental and interdisciplinary knowledge to successfully solve software engineering tasks.
К26. Ability to algorithmic and logical thinking.
Learning outcomes: 1. Be able to display a variety of real-world data with existing data structures.
2. Be able to present the selected structures in a form acceptable for processing on a computer.
3. Give the classification of data structures and their main advantages and disadvantages.
4. Explain the work of different sorting algorithms, compare their complexity.
5. Explain the work of different search algorithms, compare their complexity.
ПР05. To know and apply relevant mathematical concepts, methods of domain, system and object-oriented analysis and mathematical modeling for software development.
ПР07. To know and apply in practice the fundamental concepts, paradigms and basic principles of operation of language, instrumental and computational software engineering tools.
ПР13. To know and apply methods of algorithm development, software design and data and knowledge structures.
ПР15. To substantively choose programming languages and development technologies to solve the software development and maintenance problems.
ПР18. To know and apply information technologies for data processing, storage and transmission.
Required prior and related subjects: Computer discrete mathematics,
Object-oriented programming
Databases.
Application and data security.
Summary of the subject: The discipline involves the study of the main classes of data structures, their computer representation, examples of use, basic processing functions. Lectures of the discipline include material on a number of sorting and searching methods, tree algorithms, path building algorithms, their algorithmic complexity and comparative analysis. Laboratory and practical classes involve the practical assimilation of the material discussed in the lectures.
Part of the program results of the discipline can be evaluated through the presentation of the results of informal and informal education (certificates of the Coursera platform for Intro to Operating Systems, certificates of educational programs of IT companies, e.g. Linux Kernel GL BaseCamp, etc.).
Опис: 1. Basic definitions and concepts. Terminology. Images of algorithms. Algorithmic complexity. Polynomial and non-polynomial complexity of algorithms.
2. Classification of data structures. Basic operations on data structures.
3. Data sorting. Sort by sample. Simple sampling method. The bubble method. Quick sorting method. Comparison of algorithmic complexity of methods.
4. Sorting by inclusion. Sort by distribution. Sort by merging or merging. Comparison of algorithmic complexity of methods.
5. Trees. Basic definitions and concepts. Binary trees. Image in computer memory of graph-like structures. Tree Traversal Algorithms. Ascending, descending, mixed tree traversal algorithms.
6. Sorting on trees. Tree sampling method. Pyramidal sorting. Algorithmic complexity of methods.
7. Linear data structures. Stacks, queues, decks. Organization of stacks, queues and decks. Types of queues. Representation of linear structures in the computer. Operations of adding and removing elements from linear structures.
8. Arrays. Sets and tuples. Storage of sets and arrays. Storage of sparse matrices. Operations with arrays, sets and tuples.
9. Linear lists. Basic definitions and concepts. One-way lists. Bidirectional lists. Cyclic lists. Organization of lists.
10. Presentation of lists in the computer. Working with lists. List processing algorithms.
11. Non-linear data structures. Classification of non-linear data structures. Tables. Images of tables. Basic operations with tables.
12. List structures. Basic concepts. Hierarchical lists. Grid structures. Organization of list structures.
13. Data search. Sequential search. Binary search. Algorithm of Knuth, Maurice, Pratt. Boyer-Murr algorithm. Comparison of algorithmic complexity of methods.
14. Comparison trees on vector memory. Comparison trees on linked memory. Search in tables with calculated addresses. Tables with direct access. Hash tables. The collision problem.
15. Algorithm for building a collapsing tree. Analysis of algorithmic complexity. Application of the algorithm to the solution of combinatorial problems.
Assessment methods and criteria: 1. Control measures at practical classes.
2. Oral survey at practical classes.
3. Tests.
4. Protection of laboratory works.
5. Examination control (written component, oral component).
Критерії оцінювання результатів навчання: • current control includes the defense of 12 laboratory works with oral interviews and written reports (3+4+4+4+4+3+4+5+4+5+5= 45%). Deadlines are set for the protection of laboratory points. Outside the deadlines, the work is estimated at 0 points;
• final control - exam: written and oral form (50 + 5 = 55%)
Порядок та критерії виставляння балів та оцінок: 1. Points for current control are assigned before the beginning of the session. Students who have completed 100% of the work of the current control are admitted to the exam. A student who completed less than 50% of the work of the current control is considered uncertified and has the opportunity to re-study the discipline. A student who completed more than 50% of the work but not all 100% can complete the task and pass the exam at the commission.
2. Points for practical classes are given according to the written survey and general activity in the class.
3. Points for laboratory work are assigned according to successful defense. The defense is considered successful if the student demonstrated the performance of laboratory work on time in accordance with his version of the task, correctly prepared the report and defended it, and gave correct answers to oral questions; was able to make corrections in the laboratory at the teacher's request. If the defense of the laboratory work is delayed, the points for the laboratory work are reduced by 1 for each week of delay in the defense.
4. Responsibility for non-compliance with the principles of academic integrity during the performance and defense of laboratory work: if during the defense of the laboratory work the teacher found signs of violation of academic integrity, the work is not counted, the student receives a new version of the task and can defend the laboratory work again for a minimum number of points (1 point ).
Recommended books: 1. Krenevich AP Algorithms and data structures. Textbook. - K.: Kyiv University, 2021. - 200 p.
2. Meleshko EV, Yakimenko MS, Polishchuk LI Data algorithms and structures: a textbook for students of technical specialties of full -time and part -time education. - Kropyvnytskyi: Publisher - VF Lysenko, 2019. - 156 p.
3. V.M. Ilman, OP Ivanov, L.O. Panic. Algorithms, data and structures. Educ. a manual. / Dnipropet. Nat. Transp. Acad. V. Lazaran. - Dnipro, 2019. - 134 p.
4. T.O. Korotyeyeva Algorithms and Data Structures. - Tutorial. Lviv, Lviv Polytechnic National University Publishing House, 2014. 280 p.
Уніфікований додаток: Lviv Polytechnic National University ensures the realization of the right of persons with disabilities to obtain higher education. Inclusive educational services are provided by the Service of accessibility to learning opportunities "Without restrictions", the purpose of which is to provide permanent individual support for the educational process of students with disabilities and chronic diseases. An important tool for the implementation of the inclusive educational policy at the University is the Program for improving the qualifications of scientific and pedagogical workers and educational and support staff in the field of social inclusion and inclusive education. Contact at:
St. Karpinsky, 2/4, 1st floor, room 112
E-mail: nolimits@lpnu.ua
Websites: https://lpnu.ua/nolimits https://lpnu.ua/integration
Академічна доброчесність: The policy regarding the academic integrity of participants in the educational process is formed on the basis of compliance with the principles of academic integrity, taking into account the norms "Regulations on academic integrity at the Lviv Polytechnic National University" (approved by the academic council of the university on June 20, 2017, protocol No. 35)