Algorithms

Code:

CC4010

Acronym:

CC4010

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2023/2024 - 1S

Active?	Yes
Web Page:	http://cister-labs.github.io/alg2324
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:A_ASTR	1	Study plan since academic year 2023/2024	1	-	6	42	162
			2
M:CC	40	Study plan since 2014/2015	1	-	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

• Algorithm correctness


• Complexity: worst/best-case analysis


• Fundamentals of asymptotic analysis


• Average-case analysis and randomized algorithms


• Analysis of recursive algorithms


• Amortized analysis


• Graph traversals and dynamic programming


• Fundamentals of NP-completeness

Mandatory literature

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

Complementary Bibliography

Skiena Steven S.; The algorithm design manual. ISBN: 978-1-84800-069-8
Steven Halim and Felix Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (https://sites.google.com/site/stevenhalim/)
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/)
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))
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; intermediate test (mandatory) and final test  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	70,00
Teste	30,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo	120,00
Frequência das aulas	42,00
Total:	162,00

Eligibility for exams

All students will be admitted to the exams.

Calculation formula of final grade

• (Ti) mid-term test (mandatory) 30%


• (E) Final Exam: 70% of your final grade (can be replaced by Tf)


• (Tf) a final test that replace the final exam. Required Tf >= 8.

1st Exam ("Normal") classification: C = max(E,Tf)*0.7+ Ti*0.3 >= 9.5

2nd Exam ("Recurso") classification: C = max(E*0.7+Ti*0.3, E) >= 9.5

Required E >=8.

Examinations or Special Assignments

• Date for the mid-term test: 10 Nov (during the 1st lesson).

Special assessment (TE, DA, ...)

Equivalent to the evaluation of regular students.

Classification improvement

By final exam, only in the 2nd Exam ("Recurso"), which can take the mid-term test into account when available, as described in the formula used to calculate the final mark.