Algorithms and data structures

There is no recommended basic knowledge.

According to the objectives of the course, its target public, and goals, certain methodologies and strategies are used in order to allow the proper comprehension of the taught content:

1. Expository method: oral presentation of theoretical content using multimedia presentations, as well as the use of specific programs and resources;

2. Interrogative method: through individual questions or questions directed to the group during the classes, allowing immediate feedback on the content covered;

3. Active method: by using several techniques, such as conducting discussions/debates on the themes developed, case studies regarding important facts in the area of ​​the matter, problem-solving and development of individual works;

4. Demonstrative method.

After attending the course, each student is expected to be able to

• recognise different structures to store and manipulate data in memory;
• distinguish static structures from dynamic structures;
• choose, define, and use the most adequate data structure for each problem;
• develop and implement algorithms that allow manipulating different data structures, in C;
• implement iterative and recursive algorithms for problem solving;
• understand the notion of complexity for, when analysing a problem, choose the most efficient algorithms to solve the problem (considering the computational effort of each one).

1. Abstract Data Types
   a. Stack (LIFO discipline)
   b. Queue (FIFO discipline)
   c. List (access by position)
   d. Dictionary (key access): unordered and sorted
2. Data Structures
   a. Circular lists
   b. Single and doubly linked lists
   c. Scatter tables
   d. Generic trees
   e. Binary trees
   f. Binary search trees: unconstrained trees, AVL trees
   g. Heaps
3. Introduction to the study of algorithm efficiency
   a. Temporal and spatial complexity
   b. Complexity in the best case, in the worst case and in the expected case
4. Introduction to Recursion
   a. Divide and conquer
   b. Memory function
5. Sorting (and Searching) Algorithms
   a. Naive
   b. Efficient

NAO

Damas, L. (2019). Linguagem C. 24ª edição. FCA.

Rocha, A. A. (2014). Análise da complexidade de algoritmos. FCA.

Rocha, A. A. (2014). Estruturas de dados e algoritmos em C. 3ª edição. FCA.

Vasconcelos, J. & Carvalho, A. (2005). Algoritmia e estruturas de dados: Programação nas linguagens C e java. Edições Centro Atlântico.