Advanced Data Structures and Algorithms

Code:

M.EIC015

Acronym:

EDAA

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2022/2023 - 2S

Active?	Yes
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M.EIC	26	Syllabus	1	-	6	39	162

Teaching language

Suitable for English-speaking students

Objectives

This curricular unit (UC) aims to complement and deepen previously assimilated knowledge in 1st cycle UCs on the design and analysis of algorithms and data structures, covering an additional spectrum of data structures and algorithm design and analysis techniques, appropriate to more complex problems.

Learning outcomes and competences

At the end of the curricular unit, students should be able to:

• Understand the mapping of complex real-world problems to algorithmic solutions (e.g., as graph problems, geometric problems, linear programs, etc.);


• Select and apply advanced data structures (e.g., kd-trees) and algorithmic techniques (e.g., randomization, approximation, parallelization) to solve complex real world problems;


• Conceive efficient algorithms to solve a problem at hand;


• Recognize some classes of intractable problems and apply approximation algorithms to solve them;


• Select and apply advanced analysis techniques (e.g., amortized, probabilistic, etc.) to algorithms;


• Evaluate algorithms from the point of view of efficiency and correctness, both analytically and experimentally.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

There is no mandatory prerequisite. However, consolidated knowledge of course units on Algorithms and Data Structures and Algorithm Design will be useful.

Program

1. Advanced data structures (e.g., B trees);


2. Probabilistic analysis and randomized algorithms;


3. Parallel algorithms (approximation, divide-and-conquer, balancing, geometric division);


4. Geometric algorithms and data structures (voronoi, quad/octree, kd-tree);


5. Combinatorial optimisation and linear programming;


6. Approximation algorithms and heuristics;


7. Amortized analysis.

Mandatory literature

Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-53305-8

Complementary Bibliography

Steven S. Skiena; The algorithm design manual. ISBN: 0-387-94860-0
M. E. Newman; Networks. ISBN: 978-0-19-920665-0
Robert Sedgewick; Algorithms in C++. ISBN: 0-201-35088-2
Robert Sedgewick; Algorithms in C++. ISBN: 978-0-201-36118-6
Suman Saha, Shailendra Shukla; Advanced Data Structures: Theory and Applications, Chapman and Hall/CRC, 2019. ISBN: 9781138592605
Peter Brass; Advanced Data Structures, Cambridge University Press, 2008. ISBN: 9780511800191
Martin Grötschel, László Lovász, Alexander Schrijver; Geometric Algorithms and Combinatorial Optimization, Springer Verlag, 1993
Christos H. Papadimitriou; Combinatorial optimization. ISBN: 0-13-152462-3

Comments from the literature

Scientific articles published in conferences and journals will also be consulted.

Teaching methods and learning activities

The teaching methodology combines theoretical and practical components. The theoretical component is used for the formal exposition of the subject, presentation of examples, and their discussion. In the practical component, students solve programming challenges using advanced algorithms and data structures with tutorial accompaniment. The UC is agnostic to the programming language, allowing students to choose in which language they write their programs.

In addition, students will undertake two practical projects in groups.
In the 1st practical project, each group should study a concrete data structure of real-life interest, about which a presentation to be delivered to the colleagues and class should be prepared.
In the 2nd practical project, each group should present solutions to real-world problems based on the data structures presented in the context of the 1st practical project, bearing in mind that groups can not work over the data structure they studied before.
The 2nd practical project will be subject to an intermediate presentation, a final presentation, and a final report.

keywords

Physical sciences > Computer science > Programming
Physical sciences > Mathematics > Algorithms

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Trabalho prático ou de projeto	60,00
Trabalho escrito	20,00
Participação presencial	20,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Elaboração de projeto	76,00
Estudo autónomo	47,00
Frequência das aulas	39,00
Total:	162,00

Eligibility for exams

To be admitted in the assessment process, students have to reach markings >=8.0 in all five distributed assessment components (DA), individually.

Calculation formula of final grade

• Practical project 1 (P1): 20%;




• Deliverable: one presentation (20%)




• Practical project 2 (P2): 60%;




• Deliverables: two presentations (20%+20%) and a final report (20%)




• Individual assessment (I): 20%.

Final Mark: 0.2*P1 + 0.6*P2 + 0.20*I.

Examinations or Special Assignments

Two practical projects, to be implemented in groups of students.
Individual presentations.

Special assessment (TE, DA, ...)

Students with special statuses must submit projects according to the curricular unit's assessment system.

Classification improvement

Improvements in classification require improvements in the project and individual test components.

Observations

To be approved in the course unit, all assessment components should have marks >= 8.0, and the Final Grade should be >= 9.5.