This course introduces the main strategies for designing algorithms and the tools for evaluating their correctness and performance. The objective is to develop the ability to formalize and solve problems algorithmically, as well as the capacity for analysis and evaluation of solutions.
Attendance and active participation in the proposed learning activities (lectures and exercises) and individual study will enable students to:
- Understand the theoretical foundations of computer science, understood as the automatic processing of formal languages through the computational model of finite state automata.
- Understand the relationship between computational models and formal languages and establish a correspondence between the type of language and the corresponding computational power required by the model.
- Understand the main issues related to algorithm development, both related to correctness and performance; understand simplified models for resource estimation.
- Know the main commonly used algorithms and data structures: their origins, structure, and performance in terms of computational resource consumption.
The course is primarily structured through lectures, with materials made available to students in advance on Aulaweb. For each topic, references to the textbooks listed in the bibliography will be provided.
The theoretical computer science part is taken from the text:
J.E. Hopcroft, R. Motwani, J.D. Ullman Automata Languages and Computability - Pearson
The algorithm design and analysis part is taken from the texts:
R. Sedgewick, K. Wayne - Algorithms (fourth edition) - Addison Wesley T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein - Introduction to Algorithms and Data Structures - 3rd Edition - McGraw-Hill
Other textbooks
The structure of the lectures follows the following text:
A. Levitin - Introduction to The Design and Analysis of Algorithms - 2nd edition - Addison-Wesley
Some of the contents of algorithm design and analysis have been taken from the following texts:
C. Demetrescu, I. Finocchi, G. F. Italiano - Algorithm and Data Structures - 2nd edition McGraw-Hill S. Skiena - The Algorithm Design Manual - 2nd edition - Springer D.E. Knuth - The Art of Computer Programming - Vol. 1,2,3 - Addison Wesley S. Dasgupta, C.H. Papadimitriou, U. Vazirani - Algorithms - McGraw-Hill G.J.E. Rawlins - Compared to What?: An Introduction to the Analysis of Algorithms - W. H. Freeman. U. Mamber - Introduction to Algorithms: A Creative Approach - Addison Wesley J. Bentley - Programming Pearls - 2nd edition - Addison Wesley J. Kleinberg, E. Tardos - Algorithm Design - Pearson International Edition
Note: It is not necessary to purchase the textbooks to achieve satisfactory preparation for passing the exam. If you wish to consult the texts and they are not available in the library, please contact the instructor.
The timetable for this course is available here: EasyAcademy
