URL study guide
https://tue.osiris-student.nl/onderwijscatalogus/extern/cursus?cursuscode=2ILC0&collegejaar=2025&taal=enOmschrijving
The efficiency of algorithms is of crucial importance in many applications. In the course Data Structures (2IL50) you have learned how to mathematically analyze efficiency, how to use design techniques like divide-and-conquer, and you have seen efficient algorithms and data structures for basic problems such as sorting and searching. In the course Algorithms we will take this one step further, by studying more advanced design techniques and algorithms, and by studying other aspects of efficiency. Many of the topics that are covered concern optimization problems, where one wants to find not just some solution to a problem but an optimal solution. The course consists of three parts. In the first part we study three general techniques for solving optimization problems: backtracking, dynamic programming, and greedy algorithms. The second part of the course deals with algorithms for optimization problems on graphs: computing shortest paths, computing maximum flows, and finding so-called matchings. In the third part of the course we study computational complexity theory by looking at NP-completeness, which investigate the limits of what is efficiently computable.Doelstellingen
After completing the course, students ...… can solve simple optimization problems using techniques such as backtracking, greedy algorithms, and dynamic programming
… can analyze the running time of such algorithms and prove their correctness
... can explain standard algorithms for some important problems on graphs, such as shortest paths and maximum flows, and can explain their proofs of correctness
… can apply these graph algorithms to solve related problems such as bipartite matching
... have a basic understanding of complexity theory and can distinguish polynomial-time solvable from NP-hard problems.