Courses

Design & Analysis of Algorithms (10120)

Abstract:

Throughout the course, students will study fundamental techniques for solving algorithmic problems, including divide-and-conquer methods and recurrence relations, greedy algorithms, linear programming, and dynamic programming.

The second half of the course is devoted to graph theory, with graphs presented as a general and versatile model for representing computational problems and solving them using algorithmic techniques. Topics include graph representations, transitive closure, Eulerian and Hamiltonian paths, breadth-first search (BFS), depth-first search (DFS), strongly connected components, condensation graphs, and topological sorting. The course also covers algorithms for finding shortest paths, including shortest paths in directed acyclic graphs (DAGs), Dijkstra’s algorithm, the Bellman–Ford algorithm, and the Floyd–Warshall algorithm. Finally, minimum spanning trees are introduced, together with the classical algorithms of Kruskal and Prim.

Throughout the course, emphasis is placed on the relationship between problem formulation, the selection of an appropriate algorithmic technique, proof of correctness, and the analysis of computational efficiency.

Advanced Algorithm and Complexity (10121)

Abstract:

This course provides an introduction to advanced topics in the design and analysis of algorithms. It covers fundamental techniques and algorithms for network flows and matchings, string matching using the Knuth-Morris-Pratt (KMP) algorithm, online algorithms, and approximation algorithms.

The course also introduces core concepts in computational complexity theory, including the complexity classes P, NP, coNP, and PSPACE, polynomial-time reductions, Cook’s theorem, and the theory of NP-completeness.