Theory: 50 %

Practice: 50 %

Recommended semester: 2

Study mode: full-time

Prerequisites: -

Evaluation type: term mark

Course category: compulsory

Language: english

Responsible instructor: Dr. Pásztor Attila

Responsible department: Department of Information Technologies

Instructor(s): Dr. Pásztor Attila , Kovács Márk

Course objectives:
Introduce the most important concepts in the field of algorithms and data structures. At the end of the course, the student should be able to apply the knowledge acquired in solving computer tasks and in software development.

Course content - lectures:

1. The concept of algorithm. Algorithm description tools. Elementary algorithms: Summation, Decision, Selection, Linear search, Binary search. 2. Elementary algorithms: Counting, Multiple selection, Minimum and maximum, Intersection, Union, Merge. 3. Sorting algorithms: Direct selection, Minimum selection, Bubble sort, Insertion sort. 4. Sorting algorithms: Shell sort, Quick sort, Merge sort. 5. Algorithms' time complexity. Asymptotic comparison of functions. Determining the time complexity of algorithms. Time complexity of the studied algorithms. 6. Data structures: Stack, Queue, Circular queue, List. 7. Data structures: Doubly linked list, Circular list, Circular doubly linked list. Memory manipulation for insertion and deletion, requesting and releasing memory. 8. Data structures: Tree, binary tree, binary search tree. Implementation of trees with unknown number of branches. 9. Graphs. Directed graphs. Representation of graphs: Adjacency Matrix, Adjacency List. Graphs traversal algorithms: Depth-first search, Breadth-first search. 10. Graph algorithms: Shortest path (Dijkstra's algorithm), Minimum spanning tree (Prim's algorithm). 11. Graph algorithms: Maximum flow problem. Ford-Fulkerson algorithm. Heap. Heap operations. 12. Theoretical test. 13. Retake of the theoretical test.

Course content - labs:

1. Elementary algorithms: Summation, Decision, Selection, Linear search, Binary search. 2. Counting, Multiple selection, Minimum and maximum, Intersection, Union, Merge. 3. Sorting algorithms: Direct selection, Minimum selection, Bubble sort, Insertion sort. 4. Sorting algorithms: Shell sort, Quick sort, Merge sort. 5. Comparison of execution times of search and sort algorithms. 6. First practical test. 7. Stack. Queue. Examples of its applications. 8. Lists. Circular lists. Examples with lists. 9. Doubly linked lists. Circular doubly linked lists. Examples with doubly linked lists. 10. Binary trees. Binary search trees. 11. Graph algorithms. Shortest path. Spanned tree. Maximum flow. 12. Second practical test. 13. Retake of the second practical test.

Acquired competences:
Knowledge:

- He/she knows the operations of hardware and software elements, the technology of their implementation, how to solve problems related to their operation and the possibilities of the interconnection of IT and other technical systems. - He knows the vocabulary and special terms of the engineering profession in the Hungarian and English languages at least on the basic level.

Skills:

- He/she uses the principles and methods of natural sciences (mathematics, physics, other natural sciences) relevant to the field of information technology in his/her engineering work for the design of information systems. He/she can apply his/her knowledge acquired during his/her study to acquire deeper knowledge in the field of information engineering and to process special literature and solve problems related to information technology. - He/she constantly improves his/her knowledge and keeps up with the development of the computer engineering profession.

Attitude:

- He/she is open to acquire new methods, programming languages and develop skills to use them. - He/she is open to get to know other fields which employ information technology tools, and open to work out information technology soultions in cooperation with the experts of other areas. - He/she makes an effort to work efficiently and to high standards.

Autonomy and responsibilities:

Additional professional competences:

Requirements, evaluation, grading:
Mid-term study requirements:
Participation at lecture and laboratory classes. Complementation of the classes' contents at home from the oriented bibliographical sources. Solving tasks in computer at home in addition to the laboratory sessions. During the semester, students take a 40-point theoretical test and two 30-point practical tests. Conditions for a successful semester: the student has to achieve at least 20 points in the theoretical exam and at least 30 points in the practical exams.
Exam requirements:

Study aids, laboratory background:

Students have individual access to modern computers connected to the Internet in the laboratories. Educational materials uploaded to the Internet.

Compulsory readings:

[1] Lee Wittenberg: Data Structures and Algorithms in C++, Pocket Primer, Mercury Learning and Information, 2018, ISBN 9781683920847 [2] Paul W. Bible and Lucas Moser: An Open Guide to Data Structures and Algorithms, PALNI Press, 2023, ISBN 9781956390247 [3] Educational materials uploaded by the lecturer to the Internet.

Recommended readings:

[1] Michael McMillan: Data Structures and Algorithms Using C#, Cambridge University Press, 2007, ISBN 0521670152 [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, C. Stein: Introduction to Algorithms, Third Edition, MIT Press Ltd, 2009, ISBN 0262033844 [3] V. Aho, J. E. Hopcroft, J. D. Ullman: Data Structures and Algorithms, Pearson, 1983, ISBN 0201000237. [4] Knuth, D. E.: The Art of Computer Programming I., II. and III. vols., Addison-Wesley, 1997-1998, ISBN 0201853922, 0201896842 and 0201896850