Algorithms and data structures 2

Lectures:
1. Computational complexity of algorithms: motivation, asymptotic notation with definitions and examples.
2. Divide and conquer: master theorem with a proof, quickselect, Karatsuba's fast multiplication algorithm, Strassen's matrix multiplication algorithm.
3. Dynamic programming: a review of the fundamental approaches, examples featuring a more complex description of state (traveling salesman problem, graph coloring), examples featuring a more advanced computation of (partial) results (longest increasing subsequence, egg dropping).
4. Maximum-flow problem: definition, Ford-Fulkerson method, Edmonds-Karp algorithm, applications (e.g., in bipartite graph matching).
5. Searching in strings: the naive method, Rabin-Karp algorithm, Knuth-Morris-Pratt algorithm.
6. Text indexing: trie, suffix array, suffix tree.
7. Computational geometry: fundamental geometric object (points, lines, polygons ...), distances, intersections, areas, convex hull, geometric data structures (e.g., k-d trees).
8. Linear programming: formulation with a system of linear inequalities, representing optimization problems as linear programs, simplex algorithm.

Tutorial: In tutorial sessions, the students will deepen their understanding of the material presented during the lectures. They will use their knowledge to solve practical problems.

Homework assignments:
To complete their (weekly) homework assignments, the students will solve programming problems associated with the material covered by lectures and tutorial courses. The solutions submitted by the students will be evaluated using test cases. The scoring of the submitted solutions will be based on their correctness, as well as their ability to respect temporal and spatial constraints.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022.

Dodatna literatura:
Adam Jones. Advanced Techniques in Dynamic Programming: A Comprehensive Guide for Java Developers. 2024.
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer, 2008.
Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997.

The students will gain deeper knowledge of algorithm design methods, analysis of algorithms, use of data structures , and selected problems and algorithms. At the same time, they will improve and deepen their programming skills.

After completing the course, the students will:

• know how to estimate the computational complexity of algorithms;
• be able to solve problems using the divide-and-conquer approach and estimate the computational complexity of the relevant algorithms;
• be able to use advanced techniques when designing algorithms using the dynamic programming method;
• be familiar with efficient algorithms for solving the maximum-flow problem and be able to recognize real-world problems that can be tackled this way;
• be familiar with efficient algorithms for substring search;
• know efficient algorithms for text indexing;
• master the basic concepts and selected algorithms and data structures in the field of computational geometry;
• be familiar with the concept of linear programming and be able to formulate relevant optimization problems as linear programs.

Application:
Use of the principles and methods in algorithm design and implementation.

Reflection:
Understanding the basic principles of algorithm design and their role in solving computational problems efficiently.

Transferable skills:
The ability to plan and design appropriate and efficient algorithmic solutions to various problems, as well as the ability to implement the designed algorithms regardless of the programming language used.

Lectures, tutorial, homework assignments.

Ongoing: homework assignments
Final: written and oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

ČIBEJ, U., FÜRST, L., MIHELIČ, J. A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms. Symmetry, 11(10): 1–26, 2019.
FÜRST, L. Neighborhood-based pseudo-canonical representation of graphs. The IPSI BgD Transactions on Internet Research, 15(2): 59–68, 2019.
FÜRST, L., ČIBEJ, U., MIHELIČ, J. Maximum ex'ploratory equivalence in trees. V: Proceedings of the 2015 Federated Conference on Computer Science and Information Systems (FedCSIS 2015), Łódź, Poljska, str. 507–518, 2015.
MIHELIČ, J, FÜRST, L., ČIBEJ, U. Exploratory equivalence in graphs: definition and algorithms. V: Proceedings of the 2014 Federated Conference on Computer Science and Information Systems (FedCSIS 2014), Varšava, Poljska, str. 447–456, 2014.
MIHELIČ, J., ČIBEJ, U., FÜRST, L. A backtracking algorithmic toolbox for solving the subgraph isomorphism problem. V: Handbook of research on methodologies and applications of supercomputing, IGI Global, str. 208–246, 2021.

Celotna bibliografija je dostopna v sistemu Cobiss.