Data Structures and Algorithms

Year
2
Academic year
2020-2021
Code
01000197
Subject Area
Computer Science
Language of Instruction
Portuguese
Mode of Delivery
Face-to-face
Duration
SEMESTRIAL
ECTS Credits
6.0
Type
Compulsory
Level
1st Cycle Studies

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, lab classes, demonstrators of data structures and sorting, platform Mooshak for submission of programs, and exercises for reinforcement of the formative and summing evaluation.
Theoretical-practical classes and laboratory practices to follow the practical work, and support to the Mooshak platform.
Assessment moments: Written test; Practical Work.

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)

Carlos Manuel Robalo Lisboa Bento

Assessment Methods

Assessment
Resolution Problems: 40.0%
Exam: 60.0%

Bibliography

Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3rd Edition) (Bundle) (Paperback) by Robert Sedgewick (Author)

Introduction to Algorithms (Hardcover)by Thomas H. Cormen (Author), Charles E. Leiserson (Author), Ronald L. Rivest (Author), Clifford Stein (Author)

An Introduction to the Analysis of Algorithms 1st Edition by Robert Sedgewick (Author), Philippe Flajolet (Author)