Advanced Topics in Algorithms

Code:

CC4020

Acronym:

CC4020

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/taa1819/
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	10	Study plan since 2014/2015	1	-	6	42	162
M:ENM	1	Official Study Plan since 2013-2014	1	-	6	42	162
			2
MI:ERS	3	Plano Oficial desde ano letivo 2014	4	-	6	42	162

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 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 four 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: 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.

Topics to be addressed 2017/2018:
 B - Plane-sweep techniques. Convex-hulls in 2D. Polygon decomposition, triangulations and guarding problems (Art Gallery). Line segment intersections. Proximity problems: Closest-pair problem; Voronoi diagrams and Delaunay triangulations finite sets.
 C - Approximation algorithms for NP-hard optimization problems (e.g., vertex cover; set cover; metric and euclidean TSP, bin packing).  Minimum vertex guarding problems in polygons (MVG): exact algorithms and heuristics. Hardness of approximation (e.g., MVG, generic TSP).
 A - Introduction to bipartite matching problems with preferences; complex networks, their properties (e.g., small world and power laws) and generation models (e.g., Erdős–Rényi, Watts–Strogatz and Barabási–Albert); graph and subgraph isomorphism; community discovery (e.g., modularity); patterns in networks (e.g., motifs and graphlets).
 D - Geometric data structures: the doubly-connected edge list  (DCEL) for planar subdivisions; self-adjusting data structures (e.g., red-black trees and splay trees); range search (e.g., quadtrees, kd-trees, segment trees and fenwick trees); priority queues (e.g., binomial heaps and pairing heaps); probabilistic data structures (e.g., skip lists, treaps and bloom filters).

Disclaimer: considering the actual background and interests of the students enrolled for the course, we may cover some of the remaining topics instead.

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

J. Kleinberg, E. Tardos.; Algorithm Design., Addison-Wesley, 2005. ISBN: 978-0321295354 ((Ch 11, approximation algorithms) slides available at http://www.cs.princeton.edu/~wayne/kleinberg-tardos/))
Berg Mark de 070; Computational geometry. ISBN: 978-3-540-65620-3 hbk ( Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, "Computational Geometry: Algorithms and Applications", 3rd Edition, Springer-Verlag, 2008 (or 2nd Edition). )
O.Rourke Joseph; Computational geometry in C. ISBN: 0-521-64976-5 (J.O'Rourke. Computational Geometry in C. 2nd edition, Cambridge University Press, 2001)
Vazirani Vijay V.; Approximation algorithms. ISBN: 9783540653677 (Vijay V. Vazirani. Approximation Algorithms. Springer, 2001)
Garey Michael R.; Computers and intractability. ISBN: 0-7167-1045-5 (M.R.Garey, D.S.Johnson. Computers and Intractability: a guide to the theory of NP-completeness, W.H. Freeman, 1979)
S. Halim and F. Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (1st version PDF is available online: https://sites.google.com/site/stevenhalim/)
Hoos Holger H.; Stochastic local search. ISBN: 1-55860-872-9 (Stochastic local search : foundations and applications / Holger H. Hoos, Thomas Stützle))
Wolsey Laurence A.; Integer programming. ISBN: 9780471283669 (Integer Programming / L.Wolsey))

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. The topics can be treated in an independent way so that the selection of topics to be covered can be more focused on a couple of areas or more diversified. The content topics and main areas are related to research work led at the department.

Teaching methodologies: lectures; development of a practical project in group, and its oral presentation and written report; final written exam (closed book).

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 will 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.

The final exam provides a means for the overall assessment of generic knowledge on the subjects taught as the specific theme of the practical project may be too focused preventing a more comprehensive or more individualized assessment.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	60,00
Trabalho laboratorial	40,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Elaboração de relatório/dissertação/tese
Estudo autónomo
Frequência das aulas
Trabalho escrito
Trabalho laboratorial
Total:	0,00

Eligibility for exams

Deliver the pratical project.

Calculation formula of final grade

Practical project (40%) - to study the problem and some related papers, design and implementation, do experimental work, and write final report.

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

There will be two optional tests during the semester.  Required a minimum grade of 8.0/20.0 in both. 

 

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.