Algorithms

Code:

CC4010

Acronym:

CC4010

Level:

400

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/alg1819/
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	20	Study plan since 2014/2015	1	-	6	42	162
MI:ERS	8	Plano Oficial desde ano letivo 2014	4	-	6	42	162

Teaching language

English

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

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/)
Steven Halim and Felix Halim; Competitive Programming 3: The New Lower Bound of Programming Contests, 2013 (https://sites.google.com/site/stevenhalim/)

Teaching methods and learning activities

Lectures; individual written homework; group oral homeworks; 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 written homework focus is on practical application of algorithmic concepts, consolidating the learned material. The oral homework complements the written one and allow the introduction of more open problems, with non-trivial answers, allowing for a more interactive discussion of the intelectual tools used, resorting to a white board when explaining the main ideas used.

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

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	70,00
Prova oral	15,00
Trabalho escrito	15,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Apresentação/discussão de um trabalho científico
Estudo autónomo
Frequência das aulas
Trabalho escrito
Total:	0,00

Eligibility for exams

Deliver at least one written homework and at present at least one oral homework.

Calculation formula of final grade

- (H) Written + Oral Homework: 2 written assignments to be solved individually and submitted electronically + 2 assignments to be presented orally. H weight in your final grade: 30%
- (E) Final Exam: 70% 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

1st Exam ("Normal") classification: C = max(E,T)*0.7 + H*0.3 >= 9.5
2nd Exam ("Recurso") classification: C = E*0.7 + H*0.3 >= 9.5