AIMS AND CONTENT

LEARNING OUTCOMES

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.

AIMS AND LEARNING OUTCOMES

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.

TEACHING METHODS

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.

SYLLABUS/CONTENT

• Prerequisites: Deductive logic and proofs
• Regular languages ​​and finite state automata
• Context-free languages ​​and push-down automata
• Models for analyzing algorithms: worst case, average case, amortized complexity
• Fundamental data structures
• Brute force strategy and backtracking
• Divide and Conquer strategy
• Dim and Conquer strategy
• Transform and Conquer strategy
• Space-time tradeoff
• Greedy algorithms

RECOMMENDED READING/BIBLIOGRAPHY

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.

TEACHERS AND EXAM BOARD

LESSONS

Class schedule

The timetable for this course is available here: Portale EasyAcademy