Introducción a los esquemas algorítmicos: apuntes y colección de problemas.

Abstract

These notes have been prepared for the students of the Algorithm Design Techniques subject. This is a optional subject placed in the fourth level of the Computer Science degree of the Technical University of Catalonia. This subject has two linked goals. The first one is to achieve that the students know and use a new set of design techniques. And the second one, and most important, is to train them in analizing and selecting the right design technique to solve a problem.

The content of this work is divided in six parts. Chapter 1 is devoted to Divide Conquer algorithms. Chapter 2 groups the graph definition and the elementary graph algorithms Breadth-first and Depth-first search. In chapter 3 the Greedy Algorithms are introduced with a lot of examples. Chapter 4 and 5 explain two important search algorithms : Backtracking and Branch Bound. To compare the different techniques, the Knapsack problem is solved using Greedy, Backtracking and Branch Bound algorithms. The last part is an Appendix that contains a large exercise collection.

Postprint (published version)