Course Instructors: Ştefan Trăuşan-Matu, Traian Rebedea, Costin Gabriel Chiru, Andrei Mogoș

Discussing the intrinsic properties of problems from the point of view of the different methods used to solve them and presenting the most important methods for solving a problem. The course also highlights the relationship between the characteristics of the problems, the strategies used to solve them and the quality of the solutions. Then we discuss the main methods for finding approximate solutions for difficult problems.

Syllabus:

• Characteristics of problems and associated techniques for problem solving: divide & conquer, greedy methods (Huffman trees), dynamic programming (Optimal binary search trees);
• Backtracking, improvements and heuristics;
• Constraint satisfaction problems;
• Graph algorithms: traversals, topological sorting, strongly connected components, articulation points, bridges, minimum spanning trees, shortest paths, transportation networks and maximum flow;
• Solving problems using heuristic search: A*, AO* (Best First Search)
• Completeness and optimality, characteristics of the heuristics;
• Algorithms for solving 2-player (and multi-layer) games: minimax and alpha-beta pruning;
• Approximation algorithms (using examples for graph connectivity, Steiner trees, graph coloring, shortest paths);
• Random algorithms: Las Vegas, Monte Carlo, probabilistic approximation.