Algorithms

Code:

CC4010

Acronym:

CC4010

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2016/2017 - 1S

Active?	Yes
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	28	Study plan since 2014/2015	1	-	6	42	162
MI:ERS	5	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

Suitable for English-speaking students

Objectives

This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future.

Learning outcomes and competences

Students should be able to understand the relationship between algorithm design, correctness proof and complexity analysis. Students should learn algorithmic techniques of general applicability and get to know some major algorithms in a few common domains. They will also obtain practical experience in applying generic algorithms to specific problems.

Working method

Presencial

Program

Mandatory literature

Cormen Thomas H. 070; Introduction to algorithms. ISBN: 9780262033848 hbk

Complementary Bibliography

Armando Matos; Tópicos Avançados em Algoritmos, DCC/FCUP, 2008 (In Portuguese - some lecture notes (http://www.dcc.fc.up.pt/~acm/aulas/aa/t1.pdf))
Steven Halim and Felix Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (https://sites.google.com/site/stevenhalim/)
Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
Sedgewick Robert; Algorithms. ISBN: 0-201-06673-4
Jon Kleinberg and Éva Tardos; Algorithm Design, 2005. ISBN: 978-0321295354 (http://www.cs.princeton.edu/~wayne/kleinberg-tardos/)
Ana Paula Tomás; Desenho e Análise de Algoritmos – Alguns Apontamentos, DCC/FCUP, 2013 ((Some additional notes: http://www.dcc.fc.up.pt/~apt/aulas/DAA/1314/ApontamentosDAA.pdf))

Teaching methods and learning activities

Lectures; homework (exercises and paper reading); oral presentation of homework in class; intermediate tests or final exam.

The lectures mix the presentation of new material (introducing concepts, main algorithms and some results) with interactive discussion of their application when solving real problems.

The homework focus is on practical application of algorithmic concepts, consolidating the learned material.

The final exam and intermediate tests (closed book), globally evaluates the knowledge acquired by the students.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	80,00
Prova oral	20,00
Total:	100,00

Calculation formula of final grade

- (H1+H2) Two assignments (oral presentation of a topic): 20%
- (E) Final Exam: 80% of your final grade
- (T) Multiple "smaller" tests: Two tests, T1 and T2 will be offered during the semester (one midterm and one near the end). You can use them to get exemption from the final exam. T = 0.5*T1 + 0.5*T2. Required T1,T2 >= 8.

1st Exam ("Normal") classification: C = max(E,T)*0.8 + H1+H2 >= 9.5
2nd Exam ("Recurso") classification: C = E*0.8 + H1+H2 >= 9.5