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.

Provide students with fundamental knowledge efficiently and basic data structures as essential tools to solve problems efficiently.

After attending this course, each student is expected to:

• know different structures to store and manipulate data in memory;
• distinguish static structures from dynamic structures;
• know how to choose the most suitable data structure for each problem;
• know how to develop and implement algorithms to manipulate different data structures, in C.
• 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. Ingenuous: insertion sort; selection sort; bubble sort
   b. Efficient: heapsort; mergesort; quicksort

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.