Algorithms and Data Structures 2024/2025 (L.EIC011) - DCC/FCUP & DEI/FEUP

Information for the Written Exam


Date, Time and Place ("Normal Season", a.k.a. "Época Normal")


Valuation:

As you know as can be seen on the evaluation page or on Sigarra, the exam is worth 70% of the grade on this course (the other 30% come from the practical grade - check your grade here)


Exam Sample Questions:

The following PDF contains a sample of example exam questions (we want to give you an idea of some the types of questions we can ask on the exam). The number and difficulty of questions of the real exam will be calibrated for its duration.


Goals for the Final Exam

Items marked with an asterisk (*) are for valorization, that is, aimed at students who want to get a grade above 18.

Correctness

Correctness and Loop Invariants

Asymptotic Analysis

Notation for orders of Growth

Analysis of the Complexity of a Program

Sorting (and Searching)

Concepts and Applications

Algorithms

Sequential Search

  • Know and understand the concept of sequential search and its time complexity

    Binary Search


    Abstract Data Types (ADT)


    ADT: Lists, Stacks and Queues

    Linked List Basics

    Sequential (or linear) ADTs

    Some Applications (of sorting and ADTs) to Geometric Problems (*)


    ADT: Binary Trees

    Tree Basics

    Simple Binary Trees


    ADT: Balanced Binary Search Trees

    Concepts and applications

    AVL Trees

    Red-Black Trees


    ADT: Graphs

    Introduction and Terminology

    Graph Representation

    Concepts of Graph Traversal

    Simple DFS Applications

    More Advanced DFS Applications

    BFS Applications


    ADT: Hash Tables

    Concepts and Hash Functions

    Collision Strategies


    ADT: Priority Queues (and Heaps)

    Concepts

    Applications