Advanced Topics in Algorithms

Code:

CC4020

Acronym:

CC4020

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2022/2023 - 2S

Active?	No
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	0	Study plan since 2014/2015	1	-	6	42	162
M:ENM	0	Official Study Plan since 2013-2014	1	-	6	42	162
			2

Teaching language

Suitable for English-speaking students

Objectives

To improve background on techniques for designing algorithms and analysing their correctness and complexity.
To know and apply methods for finding exact and approximate solutions for hard problems.

Learning outcomes and competences

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 and identifying computational hard problems.

Working method

Presencial

Program

This unit is organized under modules and covers topics of the following list:
 - A - Graph and network algorithms: Shortest and longest paths; Flows (max flow, min cost); Matchings in bipartite and general graphs (maximum cardinality, weighted, under preferences); Graph morphisms (network motifs discovery); Small world networks;
- B - Geometric Algorithms: geometric primitives; Plane sweep techniques; Convex hulls; Intersections of planar decompositions; Triangulation; Visibility and Art Gallery Problems; Arrangements and duality; Point location; Voronoi diagrams and Delaunay triangulation; Range searching.
- C - Combinatorial optimization: Exact methods; Tree-search algorithms; Heuristics and Metaheuristics; Inapproximability. Applications: Traveling salesperson problem (TSP); Scheduling; Facility location; Vehicle routing; Bin packing and floorplan optimization; Set covering and coverage problems; Approximate counting and sampling.
- D - Advanced data structures: Self-adjusting data structures; Temporal data structures; Cache-aware and cache oblivious models; Succint data structures; Geometric data structures.
- E - Quantum Computing:  quantum view of classical probabilistic algorithms;  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.

======================================

Topics to be addressed in 2022/2023:
To be confirmed. They may depend in part on the interest and previous training of the enrolled students.

Most likely, (C) Some topics in Combinatorial Otimization (B) Geometric Algorithms and (E) Quantum Computing.

Mandatory literature

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk (T.H.Cormen, C.E. Leiserson, R.L.Rivest, C.Stein. Introduction to Algorithms. The MIT Press, 3rd ed, 2009)

Complementary Bibliography

Ronald de Wolf; Quantum Computing Lecture Notes, 2021 (http://homepages.cwi.nl/~rdewolf/qcnotes.pdf)
Mark de Berg; Computational geometry. ISBN: 978-3-540-65620-3 hbk ((module B))
Joseph O.Rourke; Computational geometry in C. ISBN: 0-521-64976-5 ((module B))
Laurence A. Wolsey; Integer programming. ISBN: 9780471283669
Vijay V. Vazirani; Approximation algorithms. ISBN: 978-3-540-65367-7
Holger H. Hoos; Stochastic local search. ISBN: 978-1-55860-872-6

Comments from the literature

Some suggested scientific papers (about particular topics).

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, either exactly or approximately.

Teaching methodologies: lectures; development of practical projects in group, and its oral presentation and written report; final written exam.

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 projects allow 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 (%)
Trabalho prático ou de projeto	40,00
Exame	60,00
Total:	100,00

Amount of time allocated to each course unit

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

Eligibility for exams

To have delivered the pratical projects.

Calculation formula of final grade

Practical projects (40%) - to study the problems and some related papers, design and implementation, do experimental work, and write final reports.

Written exam (60%) - closed book (a minimum grade of 9.5 out of 20 is required).

If possible, there will be tests during the semester to waive the final exam (to be confirmed).

Observations

It is recommended that students had attended CC2001 (Design and Analysis of Algorithms), or some equivalent couse unit, as well as Algorithms (CC4010), to improve potential of success.