Data Structures and Algorithms

Recommended Prerequisites

Algorithmics and resolution of problems, procedural programming, object oriented programming, discrete structures  and complexity analysis.

Teaching Methods

The learning process is supported on the following instruments: theoretical classes, theoretical-practical classes, lab, demonstrators of data structures and sorting, and exercises for reinforcement of the formative and summing evaluation.

Written exam pretends to evaluate the Objectives of the curricular unit and competencies.  50% of the final score comes from this exam. Practical work, in the form of three projects, weights 50% in the final score.

Learning Outcomes

After conclusion of this unit, the student should exhibit knowledge and understanding on the following topics: complexity analysis; general techniques for algorithm design; data structures and sorting.

Application of knowledge and understanding: complexity analysis; understanding on the recursive nature of the various data structures and algorithms; comparative analysis.

Judgement and decision making: decision on data structures, sorting algorithms and algorithm design.

Communication skills: reinforcement on the competencies on written communication for elaboration of technical reports; oral communication of decisions in context.

Self-learning skills: self-learning and identification of credible sources..

Work Placement(s)

No

Syllabus

- Complexity analysis.

- Advanced techniques of algorithm design.

- Trees. AVL, VP, heaps, skip lists, B trees.

- Graph theory.

- Sorting algorithms: shell sort, merge sort, quick sort, radix sort, MSD, LSD.

- Hash tables.

- Selected topics (e.g. string matching).

Head Lecturer(s)

Luís Filipe dos Santos Coelho Paquete

Assessment Methods

Assessment
Exam: 50.0%
Project: 50.0%

Bibliography

 Introduction to Algorithms, (4th Edition): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, MIT Press Ltd, 2022

 

Algorithms (4th Edition): Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011

 

An Introduction to the Analysis of Algorithms (2nd Edition), Robert Sedgewick and Philippe Flajolet, Addison-Wesley Professional, 2013