2023
Data Structures and Algorithms I
Name: Data Structures and Algorithms I
Code: INF13188L
6 ECTS
Duration: 15 weeks/156 hours
Scientific Area:
Informatics
Teaching languages: Portuguese
Languages of tutoring support: Portuguese, English
Regime de Frequência: Presencial
Sustainable Development Goals
Learning Goals
To introduce the main concepts of data structures and algorithm analysis. Define and analyze the complexity of elementary abstract data types such as lists, stacks, queues, trees, hash tables, and heaps. Understanding and analyze the main sorting algorithms.
Contents
I- Introduction to algorithms analysis: Spatial and Temporal Complexity; Best case, worst case and expected case; Notations Big-O, Omega and Theta; Analysis of iterative and recursive algorithms
II- Abstract data types:
1. Lists, Stacks and Queues Trees
2. Binary trees: binary trees traversals; Binary search trees; Balanced trees; AVL Trees.
III- Priority queues: binary heaps, construction of a heap from a vector
IV- Hashing: Hash function; Separate chaining; Collision resolution strategies: Linear probing, Quadratic probing and Double Hashing; Rehashing
V- The sorting problem: Presentation, analysis and comparison of the behaviour of some sorting algorithms: BubbleSort, Insertion sort, Mergesort, Heapsort, Quicksort, Bucketsort
II- Abstract data types:
1. Lists, Stacks and Queues Trees
2. Binary trees: binary trees traversals; Binary search trees; Balanced trees; AVL Trees.
III- Priority queues: binary heaps, construction of a heap from a vector
IV- Hashing: Hash function; Separate chaining; Collision resolution strategies: Linear probing, Quadratic probing and Double Hashing; Rehashing
V- The sorting problem: Presentation, analysis and comparison of the behaviour of some sorting algorithms: BubbleSort, Insertion sort, Mergesort, Heapsort, Quicksort, Bucketsort
Teaching Methods
Lectures and practical classes that follow the subjects taught in the lectures.
We provide a large set of exercises, covering the topics of the course and with increasing degree of difficulty, so that the students can practice their skills.
We provide a large set of exercises, covering the topics of the course and with increasing degree of difficulty, so that the students can practice their skills.
Assessment
The evaluation has a theoretical component (70%) and a practical component (30%).
The theoretical component consists of two tests (35% each) or alternatively, an exam (70%). Students may also take an appeal exam in order to improve the grade of the theoretical component or to obtain the evaluation for this component.
The practical component is accomplished through practical projects carried out during the semester.
The theoretical component consists of two tests (35% each) or alternatively, an exam (70%). Students may also take an appeal exam in order to improve the grade of the theoretical component or to obtain the evaluation for this component.
The practical component is accomplished through practical projects carried out during the semester.
Teaching Staff
