Advanced Topics in Algorithms

Code:

CC4020

Acronym:

CC4020

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2021/2022 - 2S

Active?	Yes
Web Page:	https://www.dcc.fc.up.pt/~pribeiro/aulas/taa2122/
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Master in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
M:CC	17	Study plan since 2014/2015	1	-	6	42	162
M:ENM	1	Official Study Plan since 2013-2014	1	-	6	42	162
			2

Teaching language

English
Obs.: The course will be given in English, see the English description.

Objectives

Part I. Advanced data structures

To improve background on techniques for designing algorithms and analysing their correctness and complexity.

Part II. Quantum computing

The goal is to have basic knowledge of two theoretical models of quantum computing, namely quantum circuits and quantum query algorithms. Extra credit may be gained from learning about quantum communication, as well.

Learning outcomes and competences

Part I. Advanced data structures

To know some of the major algorithms and data structures for solving some problems in specific domains with practical utilility. To develop skills for understanding the computational complexity of practical problems.

Part II. Quantum computing

The student should have a basic understanding of quantum computing, namely: what the models are like, how they resemble and how they differ from classical computing, some algorithms that can (in theory) be run on a quantum computer, etc.

Working method

Presencial

Program

Part I. Advanced data structures

• Balanced binary search trees (AVL and Red-Black trees)


• Self-adjusting data structures (splay trees and amortized analysis)


• Probabilistic data structures (treaps, skip lists, bloom filters)


• Spatial data structures (quadtrees and variants, kd-trees, range trees

Part II. Quantum computing

• A quantum view of classical probabilistic algorithms


• What is a quantum state?


• Basic operations on quantum states.


• The circuit model


• The Deutch-Josza algorithm


• Simon's algorithm


• Quantum Fourier transform


• Shor's factoring algorithm


• Grover's search algorithm


• Other topics

Mandatory literature

Ronald de Wolf; Quantum Computing Lecture Notes, 2021 (http://homepages.cwi.nl/~rdewolf/qcnotes.pdf)
Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-03384-8

Teaching methods and learning activities

The syllabus allows the consolidation of background knowlegdge as well as the introduction of techniques and metods of specific areas which are important for solving problems in application areas efficiently.

Teaching methodologies: lectures; development of a practical project in group, and its oral presentation and written report; written tests.

The lectures are intended for presentation and explanation of the selected topics, introducing concepts, main results and algorithms, always establishing the relationship to a problem of practical interest.

The practical project allows students to deepen their knowledge about a problem in one of the listed areas, and may require some introductory research work, the overall focus being mainly on experimental work. It will give the opportunity for autonomous study, analysis and critical thinking and collaborative work, and for applying and adapting techniques and algorithms addressed.

Evaluation Type

Distributed evaluation without final exam

Assessment Components

designation	Weight (%)
Teste	80,00
Trabalho prático ou de projeto	20,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Apresentação/discussão de um trabalho científico	2,00
Elaboração de projeto	20,00
Elaboração de relatório/dissertação/tese	6,00
Estudo autónomo	92,00
Frequência das aulas	42,00
Total:	162,00

Eligibility for exams

To have delivered the pratical and project and to have made the two written tests

Calculation formula of final grade

• Pratical Project on Advanced Data Structures: 20%


• Test #1: 40% (roughly on the middle of semester)


• Test #2: 40% (at the end of semester)

At the end of the semester the sudents will have one chace to try to improve their grades on one or both of the tests.